def fast_graph_could_be_isomorphic(G1,G2):
    """Returns False if graphs G1 and G2 are definitely not isomorphic.

    True does NOT garantee isomorphism.
  
    Checks for matching degree and triangle sequences.
    """
  
    # Check global properties
    if G1.order() != G2.order(): return False
    
    # Check local properties
    d1=G1.degree(with_labels=True)
    t1=networkx.triangles(G1,with_labels=True)
    props1=[ [d1[v], t1[v]] for v in d1 ]
    props1.sort()
    
    d2=G2.degree(with_labels=True)
    t2=networkx.triangles(G2,with_labels=True)
    props2=[ [d2[v], t2[v]] for v in d2 ]
    props2.sort()

    if props1 != props2: return False

    # OK...
    return True

 def test_path(self):
     G = nx.path_graph(10)
     assert_equal(list(nx.triangles(G).values()),
                  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
     assert_equal(nx.triangles(G),
                  {0: 0, 1: 0, 2: 0, 3: 0, 4: 0,
                   5: 0, 6: 0, 7: 0, 8: 0, 9: 0})

def node_wcc(x, S, V):
    tS, tV = nx.triangles(S, x), nx.triangles(V, x)
    vtS, vtV = number_of_triangle_nodes(S, x), number_of_triangle_nodes(V, x)
    vtV_S = vtV - vtS
    result = 0.0 if tV == 0 else tS / tV * vtV / (S.number_of_nodes() - 1 + vtV_S)
    print("node: {}, tS: {}, tV: {}, vtS: {}, vtV: {}, vtV_S: {} wcc: {}".format(x, tS, tV, vtS, vtV, vtV_S, result))
    return result

def test_holme():

    for N in (5, 10, 15):
        for m in (1, 2, 3, 4):
            m0 = max(3, m+1)    # must reproduce logic of the model.
            g = HolmeGraph.get(N=N, m=m, Pt=1, m0=m0)
            assert_equal(g.number_of_edges(),   (N-m0)*m)

    for N in (5, 10, 15):
        for m in (1, 2, 3, 4):
            m0 = max(3, m+1)    # must reproduce logic of the model.
            g = HolmeGraph.get(N=N, m=m, Pt=.5, m0=m0)
            assert_equal(g.number_of_edges(),   (N-m0)*m)


    # Should return itself
    g0 = networkx.complete_graph(5)
    g = HolmeGraph.get(N=5, m=3, Pt=1, g0=g0)
    assert_equal(networkx.triangles(g), dict((i,4*3/2) for i in range(5)))

    # Test number of triangles created for new nodes.
    g0 = networkx.complete_graph(5)
    g = HolmeGraph.get(N=6, m=3, Pt=1, g0=g0)
    assert_equal(networkx.triangles(g)[5], 3)

    g0 = networkx.complete_graph(6)
    g = HolmeGraph.get(N=7, m=3, Pt=1, g0=g0)
    assert_equal(networkx.triangles(g)[6], 3)

    # Test number of triangles created for new nodes.
    def _make():
        g = HolmeGraph.get(N=6, m=3, m0=5, Pt=0)
        return networkx.triangles(g)
    sizes = [_make() for _ in range(10)]
    assert_true(any(_[5]==0 for _ in sizes))

def fast_could_be_isomorphic(G1, G2):
    """Returns False if graphs are definitely not isomorphic.

    True does NOT guarantee isomorphism.

    Parameters
    ----------
    G1, G2 : graphs
       The two graphs G1 and G2 must be the same type.

    Notes
    -----
    Checks for matching degree and triangle sequences.
    """
    # Check global properties
    if G1.order() != G2.order():
        return False

    # Check local properties
    d1 = G1.degree()
    t1 = nx.triangles(G1)
    props1 = [[d1[v], t1[v]] for v in d1]
    props1.sort()

    d2 = G2.degree()
    t2 = nx.triangles(G2)
    props2 = [[d2[v], t2[v]] for v in d2]
    props2.sort()

    if props1 != props2:
        return False

    # OK...
    return True

 def test_cubical(self):
     G = nx.cubical_graph()
     assert_equal(list(nx.triangles(G).values()),
                  [0, 0, 0, 0, 0, 0, 0, 0])
     assert_equal(nx.triangles(G,1),0)
     assert_equal(list(nx.triangles(G,[1,2]).values()),[0, 0])
     assert_equal(nx.triangles(G,1),0)
     assert_equal(nx.triangles(G,[1,2]),{1: 0, 2: 0})

 def test_k5(self):
     G = nx.complete_graph(5)
     assert_equal(list(nx.triangles(G).values()),[6, 6, 6, 6, 6])
     assert_equal(sum(nx.triangles(G).values())/3.0,10)
     assert_equal(nx.triangles(G,1),6)
     G.remove_edge(1,2)
     assert_equal(list(nx.triangles(G).values()),[5, 3, 3, 5, 5])
     assert_equal(nx.triangles(G,1),3)

def triangles_distribution(G, return_dictionary=False):
    """This returns a distribution of the number of triangles each
    vertex in G is involved in, amenable to applications similar to
    Borges, Coppersmith, Meyer, and Priebe 2011.
    If return_dictionary is specified, we return a dictionary indexed by
    vertex name, rather than just the values (as returned by default).
    """
    if return_dictionary:
        return nx.triangles(G)
    else:
        return nx.triangles(G).values()

def compare(f1, f2):
	g1 = read_data(f1)
	g2 = read_data(f2)
	avg1, avg2 = 0, 0
	for node in g1.nodes():
		avg1 += g1.degree(node)
	for node in g2.nodes():
		avg2 += g2.degree(node)
	print "Average degree......:       ", avg1*1.0/(len(g1.nodes())), avg2*1.0/(len(g2.nodes()))

	trg1, trg2 = 0, 0
	tr_list1 = list(nx.triangles(g1).values())
	tr_list2 = list(nx.triangles(g2).values())
	print "Triangles......:       ", sum(tr_list1)/3, sum(tr_list2)/3

def clust(Graph):
    """
    Returns the graph that merges artificial loops into a
    single node. Detects the nodes included to the triangles
    and merges them. Uses the extern function merge_nodes.
    
    Parameters
    --------
    Graph : input graph with artificial loops
    
    Returns
    -------
    G : a graph without loops; triangles of neighboring nodes
    are replaced by a single node


    """
    G = Graph.copy()
    size = G.number_of_nodes()           
    for i in G.nodes():
        neigh = nx.get_node_attributes(G, 'neig')
        index = nx.get_node_attributes(G, 'index')
        if (i in G.nodes() and nx.triangles(G, i))>0:
            n = nx.all_neighbors(G,i)
            l = [i]
            for k in n:
                if ((neigh[k]>2) and 
                    (nx.get_edge_attributes(G, 'length')[min(i,k), max(i,k)]<2)):
                    l = np.append(l, k)
            merge_nodes(G,l,size+1,index = index[i], neig = neigh[i])
            size+=1
        if (i==G.number_of_nodes()):
            break
    G = nx.convert_node_labels_to_integers(G, first_label=1)
    return G

def calculate_num_triangles(graph):
	########## need to see this ###########
	count = 0
	triang = nx.triangles(graph)
	for itr in graph.nodes():
		count += triang[itr]
	return count

    def basic_stats(self):
        #not decided on what level to deal with this yet:
        #either return error un not dealing with unconnected files,
        #or making it deal with unconnected files: the latter.
        #How about with dealing with each independently.
        #    if not nx.is_connected(g):
        #        conl= nx.connected_components(g)
        #        for n in conl:
        #            turn n into graph if it isnt
        #            calculate ec, per, cnt
        #            how and when to visualise the subgraphs?
        #            iterate to next n

        if nx.is_connected(self.nx_graph):
            ec = nx.eccentricity(self.nx_graph) 
        else:
            ec = 'NA - graph is not connected'

        per = nx.periphery(self.nx_graph)
        cnt = nx.center(self.nx_graph)
        result = { #"""fast betweenness algorithm"""  
            'bbc': nx.brandes_betweenness_centrality(self.nx_graph),
            'tn': nx.triangles(self.nx_graph), # number of triangles
            'ec': ec,
            'per': per,
            'cnt': cnt,
            'Per': self.nx_graph.subgraph(per),
            'Cnt': self.nx_graph.subgraph(cnt)
            }
        return result

def get_network_property(graph):
    """Returns various property of the graph.

    It calculates the richness coefficient, triangles and transitivity
    coefficient. To do so, it removes self-loops *in-place*. So, there
    is a possibility that the graph passed as parameter has been
    changed.
    """

    remove_self_loop(graph)

    # If number of nodes is less than three
    # no point in calculating these property.
    if len(graph.nodes()) < 3:
        return ({0: 0.0}, 0, 0)

    try:
        richness = nx.rich_club_coefficient(graph)
    except nx.NetworkXAlgorithmError:
        # NetworkXAlgorithmError is raised when
        # it fails achieve desired swaps after
        # maximum number of attempts. It happened
        # for a really small graph. But, just to
        # guard against those cases.
        richness = nx.rich_club_coefficient(graph, False)

    triangle = nx.triangles(graph)
    transitivity = nx.transitivity(graph)

    return (richness, triangle, transitivity)

def get_motifs(filename):
  import networkx as nx
  from math import factorial
  threshold = 0
  f = open(filename[:-4]+'_motifs.dat','w')
  for i in range(0,101):
    threshold = float(i)/100
    G = get_threshold_matrix(filename, threshold)
    tri_dict = nx.triangles(G)
    summe = 0
    for node in tri_dict:
      summe += tri_dict[node]
    
    N = nx.number_of_nodes(G)
    ratio = summe / (3. * binomialCoefficient(N,3))
    
    transi = nx.transitivity(G)
    if transi > 0:
      triads = summe / transi 
      ratio_triads = triads / (3 * binomialCoefficient(N,3))
    else:
      triads = 0.
      ratio_triads = 0.
    
    print 'threshold: %f, number of triangles: %f, ratio: %f, triads: %f, ratio: %f' %(threshold, summe/3, ratio, triads, ratio_triads)
    f.write("%f\t%d\t%f\t%f\t%f\n" % (threshold, summe/3, ratio, triads, ratio_triads))
  f.close()
  print "1:threshold 2:#triangles 3:ratio-to-potential-triangles 4:triads 5:ratio-to-potential-triads"

    def test_fast_versions_properties_threshold_graphs(self):
        cs='ddiiddid'
        G=nxt.threshold_graph(cs)
        assert_equal(nxt.density('ddiiddid'), nx.density(G))
        assert_equal(sorted(nxt.degree_sequence(cs)),
                     sorted(G.degree().values()))

        ts=nxt.triangle_sequence(cs)
        assert_equal(ts, list(nx.triangles(G).values()))
        assert_equal(sum(ts) // 3, nxt.triangles(cs))

        c1=nxt.cluster_sequence(cs)
        c2=list(nx.clustering(G).values())
        assert_almost_equal(sum([abs(c-d) for c,d in zip(c1,c2)]), 0)

        b1=nx.betweenness_centrality(G).values()
        b2=nxt.betweenness_sequence(cs)
        assert_true(sum([abs(c-d) for c,d in zip(b1,b2)]) < 1e-14)

        assert_equal(nxt.eigenvalues(cs), [0, 1, 3, 3, 5, 7, 7, 8])

        # Degree Correlation
        assert_true(abs(nxt.degree_correlation(cs)+0.593038821954) < 1e-12)
        assert_equal(nxt.degree_correlation('diiiddi'), -0.8)
        assert_equal(nxt.degree_correlation('did'), -1.0)
        assert_equal(nxt.degree_correlation('ddd'), 1.0)
        assert_equal(nxt.eigenvalues('dddiii'), [0, 0, 0, 0, 3, 3])
        assert_equal(nxt.eigenvalues('dddiiid'), [0, 1, 1, 1, 4, 4, 7])

def wcc1(g, G):
    q = 0
    nodes = g.node.keys()
    nodes_len = len(nodes)

    for n in nodes:
        tG = nx.triangles(G, n)

        if tG != 0:
            tS = float(nx.triangles(g, n))
            vtG = count_trinodes(n, G)
            vtGS = count_trinodes(n, G, g)

            q += tS / tG * vtG / (nodes_len - 1 + vtGS)

    return q / nodes_len

def tpr_metric(num_nodes_s, comm_subgraph):

    #Dictionary where nodes are the keys and values are the number of triangles that include the node as a vertex
    triangles = nx.triangles(comm_subgraph)

    tri_count = sum(x > 0 for x in triangles.values())
    tpr = tri_count / num_nodes_s
    return tpr

def analyze_graph(G):
	print nx.info(G)
	degree_freq = nx.degree_histogram(G)
	diameter = nx.diameter(G)
	print "Diameter: {0}".format(diameter)
	triangles = nx.triangles(G)
	triangles_values = sorted(triangles.values(), reverse=True)
	print "Triangles: {0}".format(triangles_values)

 def init(self, graph, initPart):
     """Initialize the SCDMetaData of a graph with every node in one community"""
     self.T = nx.triangles(graph)
     self.com2nodes = dict()
     self.node2coms = dict()
     for comm, nodes in initPart.items():
         self.com2nodes[comm] = nodes
         for node in nodes:
             self.node2coms[node] = set([comm])

def triangleRatio(g, center):

	triangleCoef = nx.triangles(g, nodes=[center])[center]

	deg = len(g.neighbors(center))

	maxTriangles = float(deg*(deg-1))/2.0

	return float(triangleCoef)/maxTriangles