import networkx as nx
import matplotlib.pyplot as plt
import time
import numpy as np
import pdb
import os
import math

import time
import datetime


class Graphlet:
    # class variables
    # 3-nodes triangles
    open_triangle_dict = {}
    close_triangle_dict = {}

    total_close_triangle = []
    total_open_triangle = []
    # 4-nodes
    four_path_dict = {}
    four_chordal_cycle_dict = {}
    four_tailed_triangle_dict = {}
    four_clique_dict = {}
    four_cycle_dict = {}
    three_star_dict = {}

    total_four_path = []
    total_three_star = []
    total_four_cycle = []
    total_four_tailed_triangle = []
    total_four_chordal_cycle = []
    total_four_clique = []

    # 5-nodes, totally 21 of them
    total_five_graphlet = []
    for _ in  range(21):
        total_five_graphlet.append({})

    # 6-nodes, totally 112 of them
    total_six_graphlet = []
    for _ in range(112):
        total_six_graphlet.append({})

    # 7-nodes, totally 853 of them
    total_seven_graphlet = []
    for _ in range(853):
        total_seven_graphlet.append({})

    # initializer
    def __init__(self, init_graph):
        self.G = init_graph
        self._init_all_data()
        self._count_triangles()
        self._count_4_nodes_global()
        self._count_total_5_nodes()

    def show_graph(self):
        nx.draw(self.G, with_labels=True)
        plt.show()

    # print triangles
    def print_triangles(self):
        # print("close triangle dict:")
        # print(self.close_triangle_dict)
        # print("open triangle dict:")
        # print(self.open_triangle_dict)

        print("total close triangles:")
        print(self.total_close_triangle)
        print("total open triangles:")
        print(self.total_open_triangle)
        print("number of total close triangle: %d" % len(self.total_close_triangle))
        print("number of total open triangle: %d" % len(self.total_open_triangle))

    def print_4_nodes(self):
        '''
        print("4 path dict:")
        print(self.four_path_dict)
        print("3 star dict:")
        print(self.three_star_dict)
        print("four cycle dict")
        print(self.four_cycle_dict)
        print("4 tailed triangle:")
        print(self.four_tailed_triangle_dict)
        print("4 chordal cycle:")
        print(self.four_chordal_cycle_dict)
        print("4 clique:")
        print(self.four_clique_dict)
        '''

        print("total four path:")
        print(len(self.total_four_path))
        print("total three star: ")
        print(len(self.total_three_star))
        print("total four cycle: ")
        print(len(self.total_four_cycle))
        print("total four tailed triangle:")
        print(len(self.total_four_tailed_triangle))
        print("total four chordal cycle:")
        print(len(self.total_four_chordal_cycle))
        print("total four clique:")
        print(len(self.total_four_clique))

    def print_5_nodes(self):
        print("total five node graphlets")
        print(self.total_five_graphlet)

    def print_6_nodes(self):
        print("total six node graphlets")
        print(self.total_six_graphlet)


    # add one node and count 3-node graphlets
    def add_one_node(self, added_node, connected_nodes):
        # add_node
        self.G.add_node(added_node)

        # add_edge
        for i in connected_nodes:
            self.G.add_edge(added_node, i)

        k = added_node

        for i in self.G.neighbors(k):
            for j in self.G.neighbors(i):
                if self.G.has_edge(j, k):
                    if i in self.close_triangle_dict:
                        self.close_triangle_dict[i].append((j, k))
                    else:
                        self.close_triangle_dict[i] = []
                        self.close_triangle_dict[i].append((j, k))
                    if i < j:
                        self.total_close_triangle.append((i, j, k))

                else:
                    if i in self.open_triangle_dict:
                        self.open_triangle_dict[i].append((j, k))
                    else:
                        self.open_triangle_dict[i] = []
                        self.open_triangle_dict[i].append((j, k))

                    self.total_open_triangle.append((i, j, k))

        for i in self.G.neighbors(k):
            for j in self.G.neighbors(k):
                if i < j and not self.G.has_edge(i, j):
                    if k in self.open_triangle_dict:
                        self.open_triangle_dict[k].append((i, j))
                    else:
                        self.open_triangle_dict[k] = []
                        self.open_triangle_dict[k].append((i, j))

                    self.total_open_triangle.append((k, i, j))
                if i < j and self.G.has_edge(i, j):
                    if k in self.close_triangle_dict:
                        self.close_triangle_dict[k].append((i, j))
                    else:
                        self.close_triangle_dict[k] = []
                        self.close_triangle_dict[k].append((i, j))


    # helper methods

    def _init_all_data(self):
        # class variables
        # 3-nodes triangles
        self.open_triangle_dict = {}
        self.close_triangle_dict = {}

        self.total_close_triangle = []
        self.total_open_triangle = []
        # 4-nodes
        self.four_path_dict = {}
        self.four_chordal_cycle_dict = {}
        self.four_tailed_triangle_dict = {}
        self.four_clique_dict = {}
        self.four_cycle_dict = {}
        self.three_star_dict = {}

        self.total_four_path = []
        self.total_three_star = []
        self.total_four_cycle = []
        self.total_four_tailed_triangle = []
        self.total_four_chordal_cycle = []
        self.total_four_clique = []

        # 5-nodes, totally 21 of them
        self.total_five_graphlet = []
        for _ in range(21):
            self.total_five_graphlet.append({})

        # 6-nodes, totally 112 of them
        total_six_graphlet = []
        for _ in range(112):
            total_six_graphlet.append({})

        # 7-nodes, totally 853 of them
        total_seven_graphlet = []
        for _ in range(853):
            total_seven_graphlet.append({})

    def _add_2_dict(self, dictionary, index, content):
        if index not in dictionary:
            dictionary[index] = [content]
        else:
            dictionary[index].append(content)

    # count five total nodes from four total node
    def _count_total_5_nodes(self):

        # derive from 3-star
        for node_pair in self.total_three_star:
            node, node1, node2, node3 = node_pair
            for i in self.G.neighbors(node):
                # No.1 5 node graphlet
                if (i != node1 and i != node2 and i != node3 and i > node3 and not self.G.has_edge(i, node1)
                   and not self.G.has_edge(i, node2)
                   and not self.G.has_edge(i, node3)):
                    # outside nodes from small to large
                    sorted_list = sorted((node1, node2, node3, i))
                    index = (node, sorted_list[0], sorted_list[1], sorted_list[2], sorted_list[3])
                    self.total_five_graphlet[0][index] = None
            for i in self.G.neighbors(node1):
                # No.2
                if (i != node and not self.G.has_edge(i, node) and not self.G.has_edge(i, node2)
                    and not self.G.has_edge(i, node3)):
                    index = (node, node2, node3, node1, i)
                    self.total_five_graphlet[1][index] = None
                    
            for i in self.G.neighbors(node2):
                # No.2
                if (i != node and not self.G.has_edge(i, node) and not self.G.has_edge(i, node1)
                    and not self.G.has_edge(i, node3)):
                    index = (node, node1, node3, node2, i)
                    self.total_five_graphlet[1][index] = None
                    
            for i in self.G.neighbors(node3):
                # No.2
                if (i != node and not self.G.has_edge(i, node) and not self.G.has_edge(i, node1)
                    and not self.G.has_edge(i, node2)):
                    index = (node, node1, node2, node3, i)
                    self.total_five_graphlet[1][index] = None

        # derive from 3 path
        for node_pair in self.total_four_path:
            node, node1, node2, node3 = node_pair
            for i in self.G.neighbors(node):
                pass
            for i in self.G.neighbors(node1):
                # No.3
                if (i != node and node1 < node2 and not self.G.has_edge(node, i) and not self.G.has_edge(i, node2)
                    and not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[2][(node, node1, i, node2, node3)] = None
                # No.8
                if (i != node and self.G.has_edge(i, node1) and self.G.has_edge(i, node3)
                    and not self.G.has_edge(i, node) and not self.G.has_edge(i, node2)):
                    if i == sorted((i, node1, node, node3, node2))[0]:
                        self.total_five_graphlet[7][(i, node1, node, node3, node2)] = None

            for i in self.G.neighbors(node2):
                pass
            for i in self.G.neighbors(node3):
                # No.3
                if (i != node2 and node < node3 and not self.G.has_edge(node, i) and not self.G.has_edge(i, node2)
                    and not self.G.has_edge(i, node1)):
                    self.total_five_graphlet[2][(node2, node, node1, node3, i)] = None
                # No.8
                if (i != node2 and self.G.has_edge(i, node1) and self.G.has_edge(i, node3)
                    and not self.G.has_edge(i, node) and not self.G.has_edge(i, node2)):
                    if i == sorted((i, node1, node, node3, node2)):
                        self.total_five_graphlet[7][(i, node1, node, node3, node2)] = None

        # derive from 4-cycle
        for node_pair in self.total_four_cycle:
            node, node1, node2, node3 = node_pair
            for i in self.G.neighbors(node):
                # No.7
                if (i != node1 and i != node2 and not self.G.has_edge(i, node1) and not self.G.has_edge(i, node2) and
                    not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[6][(i, node, node1, node2, node3)] = None
                # No.12
                if (i != node1 and i != node2 and self.G.has_edge(i, node1) and not self.G.has_edge(i, node2) and
                    not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[11][(i, node, node1, node2, node3)] = None
                if (i != node1 and i != node2 and not self.G.has_edge(i, node1) and self.G.has_edge(i, node2) and
                    not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[11][(i, node, node1, node2, node3)] = None
                # No.13
                if (i != node1 and i != node2 and not self.G.has_edge(i, node1) and not self.G.has_edge(i, node2) and
                    self.G.has_edge(node3, i)):
                    if i == sorted((node1, node2, i))[0]:
                        self.total_five_graphlet[12][(i, node, node1, node2, node3)] = None
                # No.18
                if (i != node1 and i != node2 and self.G.has_edge(i, node1) and self.G.has_edge(i, node2) and
                    self.G.has_edge(i, node3)):
                    self.total_five_graphlet[17][(i, node, node1, node2, node3)] = None

            for i in self.G.neighbors(node1):
                # No.7
                if (i != node and i != node3 and not self.G.has_edge(i, node) and not self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[6][(i, node1, node, node3, node2)] = None
                # No.13
                if (i != node and i != node3 and not self.G.has_edge(i, node) and self.G.has_edge(i, node2)
                    and not self.G.has_edge(i, node3)):
                    if i == sorted((i, node, node3))[0]:
                        self.total_five_graphlet[12][(i, node1, node, node3, node2)] = None

            for i in  self.G.neighbors(node2):
                # No.7
                if (i != node and i != node3 and not self.G.has_edge(i, node) and not self.G.has_edge(i, node1) and
                        not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[6][(i, node2, node, node3, node1)] = None

            for i in self.G.neighbors(node3):
                # No.7
                if (i != node1 and i != node2 and not self.G.has_edge(i, node1) and not self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node)):
                    self.total_five_graphlet[6][(i, node3, node1, node2, node)] = None
                # No.12
                if (i != node1 and i != node2 and self.G.has_edge(i, node1) and not self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node)):
                    self.total_five_graphlet[11][(i, node3, node1, node2, node)] = None
                if (i != node1 and i != node2 and not self.G.has_edge(i, node1) and self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node)):
                    self.total_five_graphlet[11][(i, node3, node1, node2, node)] = None

        # derive from chord triangle
        for node_pair in self.total_four_chordal_cycle:
            node, node1, node2, node3 = node_pair
            for i in self.G.neighbors(node):
                # No.10
                if (i != node1 and i != node2 and not self.G.has_edge(i, node1) and not self.G.has_edge(i, node2)
                    and not self.G.has_edge(node3, i)):
                    self.total_five_graphlet[9][(i, node, node1, node2, node3)] = None
                # No.16
                if (i != node1 and i != node2 and i < node3 and self.G.has_edge(i, node1) and not self.G.has_edge(i, node2) and
                    not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[15][(i, node, node1, node2, node3)] = None
                if (i != node1 and i != node2 and i < node3 and  not self.G.has_edge(i, node1) and self.G.has_edge(i, node2) and
                    not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[15][(i, node, node1, node2, node3)] = None
                # No.17
                if (i != node1 and i != node2 and not self.G.has_edge(i, node1) and not self.G.has_edge(i, node2) and
                    self.G.has_edge(node3, i)):
                    self.total_five_graphlet[16][(i, node, node1, node2, node3)] = None
                # No.20
                if (i != node1 and i != node2  and self.G.has_edge(i, node1) and self.G.has_edge(i, node2) and
                    self.G.has_edge(i, node3)):
                    if i == sorted((i, node1, node2))[0]:
                        self.total_five_graphlet[19][(i, node, node1, node2, node3)] = None
            for i in self.G.neighbors(node1):
                # No.11
                if (i != node and i != node3 and i != node2 and not self.G.has_edge(i, node) and not self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[10][(i, node1, node, node3, node2)] = None
                # No.14
                if (i != node and i != node3 and i != node2 and not self.G.has_edge(i, node) and self.G.has_edge(i, node2)
                    and not self.G.has_edge(i, node3)):
                    if i == sorted((node, node3, i))[0]:
                        self.total_five_graphlet[13][(i, node, node1, node2, node3)] = None
            for i in self.G.neighbors(node2):
                # No.11
                if (i != node and i != node3 and i != node1 and not self.G.has_edge(i, node) and not self.G.has_edge(i, node1) and
                        not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[10][(i, node2, node, node3, node1)] = None
            for i in self.G.neighbors(node3):
                # No.10
                if (i != node1 and i != node2 and not self.G.has_edge(i, node1) and not self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node)):
                    self.total_five_graphlet[9][(i, node3, node1, node2, node)] = None
                # No.16
                if (i != node1 and i != node2 and i < node and self.G.has_edge(i, node1) and not self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node)):
                    self.total_five_graphlet[15][(i, node3, node1, node2, node)] = None
                if (i != node1 and i != node2 and i < node and not self.G.has_edge(i, node1) and self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node)):
                    self.total_five_graphlet[15][(i, node3, node1, node2, node)] = None

        # derive from 4 clique:
        for node_pair in self.total_four_clique:
            node, node1, node2, node3 = node_pair
            for i in self.G.neighbors(node):

                # No.15, almost same as No.7
                if (i != node1 and i != node2 and i != node3 and not self.G.has_edge(i, node1) and not self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[14][(i, node, node1, node2, node3)] = None
                # No.19, almost same as No.12
                if (i != node1 and i != node2 and i != node3 and self.G.has_edge(i, node1) and not self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[18][(i, node, node1, node2, node3)] = None
                if (i != node1 and i != node2 and i != node3 and not self.G.has_edge(i, node1) and self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[18][(i, node, node1, node2, node3)] = None

                # No.21
                if (i != node1 and i != node2 and i != node3 and self.G.has_edge(i, node1) and self.G.has_edge(i, node2)
                    and self.G.has_edge(i, node3)):
                    if i == sorted((i, node, node1, node2, node3))[0]:
                        self.total_five_graphlet[20][(i, node, node1, node2, node3)] = None


            for i in self.G.neighbors(node1):
                # No.15, almost same as No.7
                if (i != node and i != node3 and i != node2 and not self.G.has_edge(i, node) and not self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[14][(i, node1, node, node3, node2)] = None


            for i in self.G.neighbors(node2):
                # No.15, almost same as No.7
                if (i != node and i != node3 and i != node2 and not self.G.has_edge(i, node) and not self.G.has_edge(i, node1) and
                        not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[14][(i, node2, node, node3, node1)] = None

            for i in self.G.neighbors(node3):
                # No.15, almost same as No.7
                if (i != node1 and i != node2 and i != node and not self.G.has_edge(i, node1) and not self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node)):
                    self.total_five_graphlet[14][(i, node3, node1, node2, node)] = None
                # No.19 almost same as No.12
                if (i != node1 and i != node2 and i != node and self.G.has_edge(i, node1) and not self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node)):
                    self.total_five_graphlet[18][(i, node3, node1, node2, node)] = None
                if (i != node1 and i != node2 and i != node and not self.G.has_edge(i, node1) and self.G.has_edge(i, node2) and
                        not self.G.has_edge(i, node)):
                    self.total_five_graphlet[18][(i, node3, node1, node2, node)] = None

        # derive from tailed triangle
        for node_pair in self.total_four_tailed_triangle:
            node, node1, node2, node3 = node_pair
            # No.4
            for i in self.G.neighbors(node):
                # No.6
                if (i != node1 and i != node2 and i < node3 and not self.G.has_edge(i, node1) and not self.G.has_edge(i, node2)
                    and not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[5][(node1, node, i, node2, node3)] = None
            for i in self.G.neighbors(node1):
                # No.6
                if (i != node and i != node2 and i < node3 and not self.G.has_edge(i, node) and not self.G.has_edge(i, node2)
                    and not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[5][(node, node1, i, node2, node3)] = None
            for i in self.G.neighbors(node2):
                # No.6
                if (i != node and i != node1 and i > node3 and not self.G.has_edge(i, node)
                    and not self.G.has_edge(i, node1) and not self.G.has_edge(i, node3)):
                    self.total_five_graphlet[3][(node, node1, node2, node3, i)] = None
                # No.9
                if (i != node and i != node1 and i > node3 and node3 > node and not self.G.has_edge(i, node)
                    and not self.G.has_edge(i, node1) and self.G.has_edge(i, node3)):
                    self.total_five_graphlet[8][(node, node1, node2, node3, i)] = None
            for i in self.G.neighbors(node3):
                # No.5
                if (i != node2 and not self.G.has_edge(node, i) and not self.G.has_edge(node1, i)
                    and not self.G.has_edge(node2, i)):
                    self.total_five_graphlet[4][(node, node1, node2, node3, i)] = None

    # this function only generate global counting
    def _count_4_nodes_global(self):
        # derive  from close triangles dict
        for node_pairs in self.total_close_triangle:
            (node, node1, node2) = node_pairs

            for i in self.G.neighbors(node1):
                # 4 tailed triangle
                if i != node2 and i != node and not self.G.has_edge(i, node2) and not self.G.has_edge(i, node):
                    self.total_four_tailed_triangle.append((node, node2, node1, i))
                # 4-chordal cycle
                if i != node and self.G.has_edge(i, node2) and not self.G.has_edge(i, node):
                    if node < i:
                        self.total_four_chordal_cycle.append((node, node1, node2, i))
            for i in self.G.neighbors(node2):
                # 4 tailed triangle
                if i != node1 and i != node and  not self.G.has_edge(i, node1) and not self.G.has_edge(i, node):
                    self.total_four_tailed_triangle.append((node, node1, node2, i))
                # 4 chordal cycle
                if i != node and i != node1 and self.G.has_edge(i, node) and not self.G.has_edge(i, node1):
                    if node1 < i:
                        self.total_four_chordal_cycle.append((node1, node, node2, i))

            for i in self.G.neighbors(node):

                # 4 tailed triangle
                if i != node1 and i != node2 and not self.G.has_edge(i, node1) and not self.G.has_edge(i, node2):
                    self.total_four_tailed_triangle.append((node1, node2, node, i))

                # 4 clique
                if self.G.has_edge(i, node1) and self.G.has_edge(i, node2):
                    if node < node1 < node2 < i:
                        self.total_four_clique.append((node, node1, node2, i))

                # 4 chordal cycle
                if i != node1 and i != node2 and self.G.has_edge(i, node1) and not self.G.has_edge(i, node2):
                    if node2 < i:
                        self.total_four_chordal_cycle.append((node2, node, node1, i))



        # derive from open triangles
        for node_pairs in self.total_open_triangle:
            (node, node1, node2) = node_pairs
            for i in self.G.neighbors(node1):
                # 4-path, small node first
                if not self.G.has_edge(node2, i) and not self.G.has_edge(node, i):
                    # eliminate duplication
                    if node < node1:
                        self.total_four_path.append((node, node2, node1, i))
                # 4-cycle, small node first
                if i != node and self.G.has_edge(node2, i) and not self.G.has_edge(node, i):
                    if node < i and node < node1 and node < node2:
                        self.total_four_cycle.append((node, node1, node2, i))

            for i in self.G.neighbors(node2):
                # 4-path, small node first
                if not self.G.has_edge(node1, i) and not self.G.has_edge(node, i):
                    # eliminate duplication
                    if node < node2:
                        self.total_four_path.append((node, node1, node2, i))
            for i in self.G.neighbors(node):
                # 3-star
                if node1 < node2 < i and not self.G.has_edge(node1, i) and not self.G.has_edge(node2, i):
                    # eliminate duplication: from small to big index
                    self.total_three_star.append((node, node1, node2, i))

    # this function must be after _count_trianlges function
    def _count_4_nodes(self):
        # derive  from close triangles dict
        for node in self.close_triangle_dict:
            for node_pairs in self.close_triangle_dict[node]:
                (node1, node2) = node_pairs
                for i in self.G.neighbors(node1):
                    # 4 tailed triangle
                    if i != node2 and not self.G.has_edge(i, node2) and not self.G.has_edge(i, node):
                        self._add_2_dict(self.four_tailed_triangle_dict, node, (node2, node1, i))
                        if node < node2:
                            self.total_four_tailed_triangle.append((node, node2, node1, i))
                    # 4-chordal cycle
                    if i != node and self.G.has_edge(i, node2) and not self.G.has_edge(i, node):
                        self._add_2_dict(self.four_chordal_cycle_dict, node, (node1, node2, i))
                        if node < i:
                            self.total_four_chordal_cycle.append((node, node1, node2, i))
                for i in self.G.neighbors(node2):
                    # 4 tailed triangle
                    if i != node1 and not self.G.has_edge(i, node1) and not self.G.has_edge(i, node):
                        self._add_2_dict(self.four_tailed_triangle_dict, node, (node1, node2, i))
                        if node < node1:
                            self.total_four_tailed_triangle.append((node, node1, node2, i))
                for i in self.G.neighbors(node):
                    # 4-clique
                    if self.G.has_edge(i, node1) and self.G.has_edge(i, node2):
                        if node1 < node2 < i:
                            self._add_2_dict(self.four_clique_dict, node, (node1, node2, i))
                        if node < node1 < node2 < i:
                            self.total_four_clique.append((node, node1, node2, i))

        # derive from open triangles
        for node in self.open_triangle_dict:
            for node_pairs in self.open_triangle_dict[node]:
                (node1, node2) = node_pairs
                for i in self.G.neighbors(node1):
                    # 4-path, small node first
                    if not self.G.has_edge(node2, i) and not self.G.has_edge(node, i):
                        self._add_2_dict(self.four_path_dict, node, (node2, node1, i))
                        # eliminate duplication
                        if node < node1:
                            self.total_four_path.append((node, node2, node1, i))
                    # 4-cycle, small node first
                    if i != node and self.G.has_edge(node2, i) and not self.G.has_edge(node, i):
                        self._add_2_dict(self.four_cycle_dict, node, (node1, node2, i))
                        if node < i and node < node1 and node < node2:
                            self.total_four_cycle.append((node, node1, node2, i))

                for i in self.G.neighbors(node2):
                    # 4-path, small node first
                    if not self.G.has_edge(node1, i) and not self.G.has_edge(node, i):
                        self._add_2_dict(self.four_path_dict, node, (node1, node2, i))
                        # eliminate duplication
                        if node < node2:
                            self.total_four_path.append((node, node1, node2, i))
                for i in self.G.neighbors(node):
                    # 3-star
                    if node1 < node2 < i and not self.G.has_edge(node1, i) and not self.G.has_edge(node2, i):
                        # eliminate duplication: from small to big index
                        self._add_2_dict(self.three_star_dict, node, (node1, node2, i))
                        self.total_three_star.append((node, node1, node2, i))

    def _count_triangles(self):
        num_node = nx.number_of_nodes(self.G)
        for k in self.G.nodes:
            for i in self.G.neighbors(k):
                for j in self.G.neighbors(k):
                    if i < j:
                        # There is a close triangle
                        if self.G.has_edge(i, j):
                            if k in self.close_triangle_dict:
                                self.close_triangle_dict[k].append((i, j))
                            else:
                                self.close_triangle_dict[k] = []
                                self.close_triangle_dict[k].append((i, j))

                            if k < i:
                                self.total_close_triangle.append((k, i, j))

                        # There is an open triangle
                        else:
                            if k in self.open_triangle_dict:
                                self.open_triangle_dict[k].append((i, j))
                            else:
                                self.open_triangle_dict[k] = []
                                self.open_triangle_dict[k].append((i, j))

                            self.total_open_triangle.append((k, i, j))


def get_file_name(dir):
    filenames = []
    for root, dirs, files in os.walk(dir):
        for file in files:
            filenames.append(os.path.join(root, file))
    return filenames

def get_dist(l1, l2):
    r = 0.
    for i in range(len(l1)):
        k = (l1[i] - l2[i]) * (l1[i] - l2[i])
        r += k
    r = math.sqrt(r)
    return r

# main function
if __name__ == "__main__":

    filename_x = './graph_samples/00sheep0.txt'
    filename_y = './graph_samples/1crime.txt'
    t1 = time.time()
    start = int(round(t1 * 1000))

    G = nx.Graph()
    G = nx.read_edgelist(filename_x)
    
    G2 = nx.read_edgelist(filename_y)

    graphlet = Graphlet(G)
    graphlet2 = Graphlet(G2)

    t2 = time.time()
    end = int(round(t2 * 1000))

    g1 = []
    g2 = []

    g1.append(len(graphlet.total_close_triangle)+1)
    g1.append(len(graphlet.total_open_triangle)+1)

    g2.append(len(graphlet2.total_close_triangle)+1)
    g2.append(len(graphlet2.total_open_triangle)+1)


    g1.append(len(graphlet.total_four_path)+1)
    g1.append(len(graphlet.total_three_star)+1)
    g1.append(len(graphlet.total_four_cycle)+1)
    g1.append(len(graphlet.total_four_tailed_triangle)+1)
    g1.append(len(graphlet.total_four_chordal_cycle)+1)
    g1.append(len(graphlet.total_four_clique)+1)

    g2.append(len(graphlet2.total_four_path)+1)
    g2.append(len(graphlet2.total_three_star)+1)
    g2.append(len(graphlet2.total_four_cycle)+1)
    g2.append(len(graphlet2.total_four_tailed_triangle)+1)
    g2.append(len(graphlet2.total_four_chordal_cycle)+1)
    g2.append(len(graphlet2.total_four_clique)+1)

    print("label calculating using time : ", end - start)

    for i in graphlet.total_five_graphlet:
        g1.append(len(i)+1)
    for i in graphlet2.total_five_graphlet:
        g2.append(len(i)+1)
    
    g1_log = []
    g2_log = []
    for i in g1:
        i = math.log(i)
        g1_log.append(i)
    for i in g2:
        i = math.log(i)
        g2_log.append(i)
    g1_log = np.asarray(g1_log)
    g2_log = np.asarray(g2_log)
    
    def get_dist(l1, l2):
        r = 0.
        for i in range(len(l1)):
            k = (l1[i]-l2[i])* (l1[i]-l2[i])
            r += k
        r = math.sqrt(r)
        return r

    label_distance = get_dist(g1_log, g2_log)
    print('the label distance of GFD between' + filename_x + ' and ' + filename_y + ' is : ', label_distance)

    

