def test_cmty_graph():
    # Test cmty_graph:
    g = networkx.complete_graph(7)
    g.remove_edge(3, 5)
    g.remove_edge(1, 2)
    cmtys = cmty.Communities({0:set((0,1,2)), 1:set((3,4)), 'a':set((5,6))})
    cmty_graph = cmtys.cmty_graph(g)
    assert cmty_graph.node[0]['size'] == 3           # number of nodes
    assert cmty_graph.node[0]['weight'] == 2  # edges within cmty
    assert cmty_graph.node['a']['size'] == 2
    assert cmty_graph.node['a']['weight'] == 1
    assert cmty_graph[0][1]['weight'] == 6    # edges between
    assert cmty_graph[1]['a']['weight'] == 3
    assert cmty_graph['a'][0]['weight'] == 6

    # Test cmty_graph on directed graph:
    g = networkx.complete_graph(7, create_using=networkx.DiGraph())
    g.remove_edge(3, 5)
    g.remove_edge(1, 2)
    cmtys = cmty.Communities({0:set((0,1,2)), 1:set((3,4)), 'a':set((5,6))})
    cmty_graph = cmtys.cmty_graph(g)
    assert cmty_graph.node[0]['size'] == 3       # number of nodes
    assert cmty_graph.node[0]['weight'] == 5     # edges within cmty
    assert cmty_graph.node['a']['size'] == 2
    assert cmty_graph.node['a']['weight'] == 2
    assert cmty_graph[0][1]['weight'] == 6     # edges between
    assert cmty_graph[1][0]['weight'] == 6
    assert cmty_graph[1]['a']['weight'] == 3
    assert cmty_graph['a'][1]['weight'] == 4
    assert cmty_graph['a'][0]['weight'] == 6
    assert cmty_graph[0]['a']['weight'] == 6

    def test_sld(self):
        assert_equal(cb.cmty_scaledlinkdensities(gb),
                     {0:4,  1:3})

        g = networkx.complete_graph(5)
        c = cmty.Communities({0:set(range(5))})
        assert_equal(c.cmty_scaledlinkdensities(g)[0],   5)

        g = networkx.path_graph(5)
        c = cmty.Communities({0:set(range(5))})
        assert_equal(c.cmty_scaledlinkdensities(g)[0],   2)

        # Singleton comm
        g = networkx.complete_graph(1)
        c = cmty.Communities({0:set(range(1))})
        assert_equal(c.cmty_scaledlinkdensities(g)[0],   0.0)

        # Empty comm
        g = networkx.complete_graph(0)
        c = cmty.Communities({0:set(range(0))})
        assert_equal(c.cmty_scaledlinkdensities(g)[0],   0.0)

        # Total SLD
        ce = (4 * 4 + 3 * 3) / float(4+3)
        assert_equal(cb.tot_scaledlinkdensity(gb), ce)

 def test_complete_subgraph(self):
     # Subgraph of a complete graph is a complete graph
     K1 = nx.complete_graph(1)
     K3 = nx.complete_graph(3)
     K5 = nx.complete_graph(5)
     H = K5.subgraph([1, 2, 3])
     assert_true(nx.is_isomorphic(H, K3))

def Type2AlmostCompleteGraph(n, m):
    if (BinomialCoefficient(n - 2, 2) + 4 <= m) and (m <= BinomialCoefficient(n - 1, 2) + 1):
        first_candidate = nx.complete_graph(n - 2)
        remaining_edges = m - BinomialCoefficient(n - 2, 2)
        first_candidate.add_edge(n - 2, 0)
        first_candidate.add_edge(n - 2, 1)
        for vertex_index in range(remaining_edges - 2):
            first_candidate.add_edge(n - 1, vertex_index)
        first_coefficient = nx.average_clustering(first_candidate)

        second_candidate = nx.complete_graph(n - 2)
        second_candidate.add_edge(n - 2, n - 1)
        remaining_edges = m - BinomialCoefficient(n - 2, 2) - 1
        number_of_common_neighbors = remaining_edges / 2
        for vertex_index in range(number_of_common_neighbors):
            second_candidate.add_edge(vertex_index, n - 2)
            second_candidate.add_edge(vertex_index, n - 1)
        if (remaining_edges - 2 * number_of_common_neighbors) == 1:
            second_candidate.add_edge(vertex_index + 1, n - 2)
        second_coefficient = nx.average_clustering(second_candidate)

        if first_coefficient > second_coefficient:
            G = first_candidate.copy()
        else:
            G = second_candidate.copy()
        return G

def test_white_harary_paper():
    # Figure 1b white and harary (2001)
    # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF
    # A graph with high adhesion (edge connectivity) and low cohesion
    # (node connectivity)
    G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
    G.remove_node(7)
    for i in range(4, 7):
        G.add_edge(0, i)
    G = nx.disjoint_union(G, nx.complete_graph(4))
    G.remove_node(G.order() - 1)
    for i in range(7, 10):
        G.add_edge(0, i)
    for flow_func in flow_funcs:
        kwargs = dict(flow_func=flow_func)
        # edge cuts
        edge_cut = nx.minimum_edge_cut(G, **kwargs)
        assert_equal(3, len(edge_cut), msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_edges_from(edge_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
        # node cuts
        node_cut = nx.minimum_node_cut(G, **kwargs)
        assert_equal(set([0]), node_cut, msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_nodes_from(node_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))

def test_merge_graphs_adding_special_attributes():
    mother_dag = nx.complete_graph(4)
    new_dag = add_subgraph_specific_attributes_to_graph(
        mother_graph=mother_dag,
        children_graphs_with_attrs=[(nx.complete_graph(2), {'pair': True}),
                                    (nx.complete_graph(3), {'triple': True})]
    )
    for n in new_dag.nodes():
        print(n, new_dag.node[n])
    for s, t in new_dag.edges():
        print(s, t, new_dag[s][t])

    assert_true(new_dag.node[0]['pair'])
    assert_true(new_dag.node[0]['triple'])
    assert_true(new_dag.node[1]['pair'])
    assert_true(new_dag.node[1]['triple'])

    assert_true(new_dag[0][1]['pair'])
    assert_true(new_dag[0][1]['triple'])
    
    assert_true('triple' in new_dag[0][1])
    assert_false('pair' in new_dag[1][2])

    assert_false('pair' in new_dag[3])
    assert_false('triple' in new_dag[3])

def test_cartesian_product_null():
    null=nx.null_graph()
    empty10=nx.empty_graph(10)
    K3=nx.complete_graph(3)
    K10=nx.complete_graph(10)
    P3=nx.path_graph(3)
    P10=nx.path_graph(10)
    # null graph
    G=cartesian_product(null,null)
    assert_true(nx.is_isomorphic(G,null))
    # null_graph X anything = null_graph and v.v.
    G=cartesian_product(null,empty10)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(null,K3)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(null,K10)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(null,P3)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(null,P10)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(empty10,null)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(K3,null)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(K10,null)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(P3,null)
    assert_true(nx.is_isomorphic(G,null))
    G=cartesian_product(P10,null)
    assert_true(nx.is_isomorphic(G,null))

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 test_embeddedness(self):
        assert_equal(cb.cmty_embeddedness(gb),
                     {0:(3*4/float(3*4+1)),  1:2*3/float(2*3+1)})

        g = networkx.complete_graph(5)
        c = cmty.Communities({0:set(range(5))})
        assert_equal(c.cmty_embeddedness(g)[0],
                     1.0)

        g = networkx.path_graph(5)
        c = cmty.Communities({0:set(range(5))})
        assert_equal(c.cmty_embeddedness(g)[0],
                     1.0)

        # Singleton comm
        g = networkx.complete_graph(1)
        c = cmty.Communities({0:set(range(1))})
        assert_equal(c.cmty_embeddedness(g)[0],
                     0.0)

        # Empty comm
        g = networkx.complete_graph(0)
        c = cmty.Communities({0:set(range(0))})
        assert_equal(c.cmty_embeddedness(g)[0],
                     0.0)

        # Total embeddednesses
        ce = (4*3/(4*3+1.) * 4 + 3*2/(3*2+1.) * 3) / (4+3)
        assert_equal(cb.tot_embeddedness(gb), ce)

def torrents_and_ferraro_graph():
    G = nx.convert_node_labels_to_integers(nx.grid_graph([5, 5]),
                                           label_attribute='labels')
    rlabels = nx.get_node_attributes(G, 'labels')
    labels = {v: k for k, v in rlabels.items()}

    for nodes in [(labels[(0, 4)], labels[(1, 4)]),
                  (labels[(3, 4)], labels[(4, 4)])]:
        new_node = G.order() + 1
        # Petersen graph is triconnected
        P = nx.petersen_graph()
        G = nx.disjoint_union(G, P)
        # Add two edges between the grid and P
        G.add_edge(new_node + 1, nodes[0])
        G.add_edge(new_node, nodes[1])
        # K5 is 4-connected
        K = nx.complete_graph(5)
        G = nx.disjoint_union(G, K)
        # Add three edges between P and K5
        G.add_edge(new_node + 2, new_node + 11)
        G.add_edge(new_node + 3, new_node + 12)
        G.add_edge(new_node + 4, new_node + 13)
        # Add another K5 sharing a node
        G = nx.disjoint_union(G, K)
        nbrs = G[new_node + 10]
        G.remove_node(new_node + 10)
        for nbr in nbrs:
            G.add_edge(new_node + 17, nbr)
        # Commenting this makes the graph not biconnected !!
        # This stupid mistake make one reviewer very angry :P
        G.add_edge(new_node + 16, new_node + 8)

    for nodes in [(labels[(0, 0)], labels[(1, 0)]),
                  (labels[(3, 0)], labels[(4, 0)])]:
        new_node = G.order() + 1
        # Petersen graph is triconnected
        P = nx.petersen_graph()
        G = nx.disjoint_union(G, P)
        # Add two edges between the grid and P
        G.add_edge(new_node + 1, nodes[0])
        G.add_edge(new_node, nodes[1])
        # K5 is 4-connected
        K = nx.complete_graph(5)
        G = nx.disjoint_union(G, K)
        # Add three edges between P and K5
        G.add_edge(new_node + 2, new_node + 11)
        G.add_edge(new_node + 3, new_node + 12)
        G.add_edge(new_node + 4, new_node + 13)
        # Add another K5 sharing two nodes
        G = nx.disjoint_union(G, K)
        nbrs = G[new_node + 10]
        G.remove_node(new_node + 10)
        for nbr in nbrs:
            G.add_edge(new_node + 17, nbr)
        nbrs2 = G[new_node + 9]
        G.remove_node(new_node + 9)
        for nbr in nbrs2:
            G.add_edge(new_node + 18, nbr)
    return G

    def test_bellman_ford(self):
        # single node graph
        G = nx.DiGraph()
        G.add_node(0)
        assert_equal(nx.bellman_ford(G, 0), ({0: None}, {0: 0}))
        assert_raises(KeyError, nx.bellman_ford, G, 1)

        # negative weight cycle
        G = nx.cycle_graph(5, create_using=nx.DiGraph())
        G.add_edge(1, 2, weight=-7)
        for i in range(5):
            assert_raises(nx.NetworkXUnbounded, nx.bellman_ford, G, i)
        G = nx.cycle_graph(5)  # undirected Graph
        G.add_edge(1, 2, weight=-3)
        for i in range(5):
            assert_raises(nx.NetworkXUnbounded, nx.bellman_ford, G, i)
        # no negative cycle but negative weight
        G = nx.cycle_graph(5, create_using=nx.DiGraph())
        G.add_edge(1, 2, weight=-3)
        assert_equal(nx.bellman_ford(G, 0), ({0: None, 1: 0, 2: 1, 3: 2, 4: 3}, {0: 0, 1: 1, 2: -2, 3: -1, 4: 0}))

        # not connected
        G = nx.complete_graph(6)
        G.add_edge(10, 11)
        G.add_edge(10, 12)
        assert_equal(
            nx.bellman_ford(G, 0), ({0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}, {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1})
        )

        # not connected, with a component not containing the source that
        # contains a negative cost cycle.
        G = nx.complete_graph(6)
        G.add_edges_from([("A", "B", {"load": 3}), ("B", "C", {"load": -10}), ("C", "A", {"load": 2})])
        assert_equal(
            nx.bellman_ford(G, 0, weight="load"),
            ({0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}, {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1}),
        )

        # multigraph
        P, D = nx.bellman_ford(self.MXG, "s")
        assert_equal(P["v"], "u")
        assert_equal(D["v"], 9)
        P, D = nx.bellman_ford(self.MXG4, 0)
        assert_equal(P[2], 1)
        assert_equal(D[2], 4)

        # other tests
        (P, D) = nx.bellman_ford(self.XG, "s")
        assert_equal(P["v"], "u")
        assert_equal(D["v"], 9)

        G = nx.path_graph(4)
        assert_equal(nx.bellman_ford(G, 0), ({0: None, 1: 0, 2: 1, 3: 2}, {0: 0, 1: 1, 2: 2, 3: 3}))
        assert_equal(nx.bellman_ford(G, 3), ({0: 1, 1: 2, 2: 3, 3: None}, {0: 3, 1: 2, 2: 1, 3: 0}))

        G = nx.grid_2d_graph(2, 2)
        pred, dist = nx.bellman_ford(G, (0, 0))
        assert_equal(sorted(pred.items()), [((0, 0), None), ((0, 1), (0, 0)), ((1, 0), (0, 0)), ((1, 1), (0, 1))])
        assert_equal(sorted(dist.items()), [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2)])

def original_graph():
    romeos_family = nx.complete_graph(5)
    julias_family = nx.complete_graph(5)
    # The families clash <- aw, not good!
    family_fight = nx.disjoint_union(romeos_family, julias_family)
    # ... but Romeo and Julia make love nevertheless
    family_fight.add_edge(0, 9)
    return family_fight

def test_strong_product_size():
    K5=nx.complete_graph(5)
    P5=nx.path_graph(5)
    K3 = nx.complete_graph(3)
    G=strong_product(P5,K3)
    assert_equal(nx.number_of_nodes(G),5*3)
    G=strong_product(K3,K5)
    assert_equal(nx.number_of_nodes(G),3*5)

def test_complete():
    """ In complete graphs each node is a dominating set.
        Thus the dominating set has to be of cardinality 1.
    """
    K4 = nx.complete_graph(4)
    assert_equal(len(nx.dominating_set(K4)), 1)
    K5 = nx.complete_graph(5)
    assert_equal(len(nx.dominating_set(K5)), 1)

def test_spanner_unweighted_disconnected_graph():
    """Test spanner construction on a disconnected graph."""
    G = nx.disjoint_union(nx.complete_graph(10), nx.complete_graph(10))

    spanner = nx.spanner(G, 4, seed=_seed)
    _test_spanner(G, spanner, 4)

    spanner = nx.spanner(G, 10, seed=_seed)
    _test_spanner(G, spanner, 10)

    def build_cnf(args):
        """Build a formula to check that a graph is a ramsey number lower bound

        Arguments:
        - `args`: command line options
        """
        G=_SimpleGraphHelper.obtain_graph(args)
        return SubgraphFormula(G,[networkx.complete_graph(args.k),
                                  networkx.complete_graph(args.s)])

def test_tensor_product_size():
    P5 = nx.path_graph(5)
    K3 = nx.complete_graph(3)
    K5 = nx.complete_graph(5)

    G = nx.tensor_product(P5, K3)
    assert_equal(nx.number_of_nodes(G), 5 * 3)
    G = nx.tensor_product(K3, K5)
    assert_equal(nx.number_of_nodes(G), 3 * 5)

    def test_subgraph_centrality_big_graph(self):
        g199 = nx.complete_graph(199)
        g200 = nx.complete_graph(200)

        comm199 = nx.subgraph_centrality(g199)
        comm199_exp = nx.subgraph_centrality_exp(g199)

        comm200 = nx.subgraph_centrality(g200)
        comm200_exp = nx.subgraph_centrality_exp(g200)

def test_white_harary_2():
    # Figure 8 white and harary (2001)
    # # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF
    G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
    G.add_edge(0,4)
    # kappa <= lambda <= delta
    assert_equal(3, min(nx.core_number(G).values()))
    assert_equal(1, nx.node_connectivity(G))
    assert_equal(1, nx.edge_connectivity(G))

def test_strong_product():
    null=nx.null_graph()
    empty1=nx.empty_graph(1)
    empty10=nx.empty_graph(10)
    K2=nx.complete_graph(2)
    K3=nx.complete_graph(3)
    K5=nx.complete_graph(5)
    K10=nx.complete_graph(10)
    P2=nx.path_graph(2)
    P3=nx.path_graph(3)
    P5=nx.path_graph(5)
    P10=nx.path_graph(10)
    # null graph
    G=strong_product(null,null)
    assert_true(nx.is_isomorphic(G,null))
    # null_graph X anything = null_graph and v.v.
    G=strong_product(null,empty10)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(null,K3)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(null,K10)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(null,P3)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(null,P10)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(empty10,null)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(K3,null)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(K10,null)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(P3,null)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(P10,null)
    assert_true(nx.is_isomorphic(G,null))

    G=strong_product(P5,K3)
    assert_equal(nx.number_of_nodes(G),5*3)
    G=strong_product(K3,K5)
    assert_equal(nx.number_of_nodes(G),3*5)

    #No classic easily found classic results for strong product

    G = nx.erdos_renyi_graph(10,2/10.)
    H = nx.erdos_renyi_graph(10,2/10.)
    GH = strong_product(G,H)

    for (u_G,u_H) in GH.nodes_iter():
        for (v_G,v_H) in GH.nodes_iter():
            if (u_G==v_G and H.has_edge(u_H,v_H)) or \
               (u_H==v_H and G.has_edge(u_G,v_G)) or \
               (G.has_edge(u_G,v_G) and H.has_edge(u_H,v_H)):
                assert_true(GH.has_edge((u_G,u_H),(v_G,v_H)))
            else:
                assert_true(not GH.has_edge((u_G,u_H),(v_G,v_H)))