def test_global_parameters(self):
     b,c=nx.intersection_array(nx.cycle_graph(5))
     g=nx.global_parameters(b,c)
     assert_equal(list(g),[(0, 0, 2), (1, 0, 1), (1, 1, 0)])
     b,c=nx.intersection_array(nx.cycle_graph(3))
     g=nx.global_parameters(b,c)
     assert_equal(list(g),[(0, 0, 2), (1, 1, 0)])

 def test_is_chordal(self):
     assert_false(nx.is_chordal(self.non_chordal_G))
     assert_true(nx.is_chordal(self.chordal_G))
     assert_true(nx.is_chordal(self.connected_chordal_G))
     assert_true(nx.is_chordal(nx.complete_graph(3)))
     assert_true(nx.is_chordal(nx.cycle_graph(3)))
     assert_false(nx.is_chordal(nx.cycle_graph(5)))

def test_directed_node_connectivity():
    G = nx.cycle_graph(10, create_using=nx.DiGraph()) # only one direction
    D = nx.cycle_graph(10).to_directed() # 2 reciprocal edges
    assert_equal(1, approx.node_connectivity(G))
    assert_equal(1, approx.node_connectivity(G, 1, 4))
    assert_equal(2,  approx.node_connectivity(D))
    assert_equal(2,  approx.node_connectivity(D, 1, 4))

    def setUp(self):

        G=nx.Graph()
        G.add_edge(0,1,weight=3)
        G.add_edge(0,2,weight=2)
        G.add_edge(0,3,weight=6)
        G.add_edge(0,4,weight=4)
        G.add_edge(1,3,weight=5)
        G.add_edge(1,5,weight=5)
        G.add_edge(2,4,weight=1)
        G.add_edge(3,4,weight=2)
        G.add_edge(3,5,weight=1)
        G.add_edge(4,5,weight=4)
        self.G=G
        self.exact_weighted={0: 4.0, 1: 0.0, 2: 8.0, 3: 6.0, 4: 8.0, 5: 0.0}
        self.K = nx.krackhardt_kite_graph()
        self.P3 = nx.path_graph(3)
        self.P4 = nx.path_graph(4)
        self.K5 = nx.complete_graph(5)

        self.C4=nx.cycle_graph(4)
        self.T=nx.balanced_tree(r=2, h=2)
        self.Gb = nx.Graph()
        self.Gb.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3),
                                (2, 4), (4, 5), (3, 5)])
        self.F = nx.florentine_families_graph()
        self.D = nx.cycle_graph(3, create_using=nx.DiGraph())
        self.D.add_edges_from([(3, 0), (4, 3)])

    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 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}))

        # negative weight cycle
        G = nx.cycle_graph(5, create_using = nx.DiGraph())
        G.add_edge(1, 2, weight = -7)
        assert_raises(nx.NetworkXUnbounded, nx.bellman_ford, G, 0)
        G = nx.cycle_graph(5)
        G.add_edge(1, 2, weight = -7)
        assert_raises(nx.NetworkXUnbounded, nx.bellman_ford, G, 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}))
        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 setUp(self):
     from networkx import convert_node_labels_to_integers as cnlti
     self.grid = cnlti(nx.grid_2d_graph(4, 4), first_label=1,
                       ordering="sorted")
     self.cycle = nx.cycle_graph(7)
     self.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
     self.neg_weights = nx.DiGraph()
     self.neg_weights.add_edge(0, 1, weight=1)
     self.neg_weights.add_edge(0, 2, weight=3)
     self.neg_weights.add_edge(1, 3, weight=1)
     self.neg_weights.add_edge(2, 3, weight=-2)

    def test_periodic(self):
        G = nx.grid_2d_graph(0, 0, periodic=True)
        assert_equal(dict(G.degree()), {})

        for m, n, H in [(2, 2, nx.cycle_graph(4)), (1, 7, nx.cycle_graph(7)),
                        (7, 1, nx.cycle_graph(7)),
                        (2, 5, nx.circular_ladder_graph(5)),
                        (5, 2, nx.circular_ladder_graph(5)),
                        (2, 4, nx.cubical_graph()),
                        (4, 2, nx.cubical_graph())]:
            G = nx.grid_2d_graph(m, n, periodic=True)
            assert_true(nx.could_be_isomorphic(G, H))

    def setUp(self):
        from networkx import convert_node_labels_to_integers as cnlti

        self.grid = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted")
        self.cycle = nx.cycle_graph(7)
        self.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
        self.XG = nx.DiGraph()
        self.XG.add_weighted_edges_from(
            [
                ("s", "u", 10),
                ("s", "x", 5),
                ("u", "v", 1),
                ("u", "x", 2),
                ("v", "y", 1),
                ("x", "u", 3),
                ("x", "v", 5),
                ("x", "y", 2),
                ("y", "s", 7),
                ("y", "v", 6),
            ]
        )
        self.MXG = nx.MultiDiGraph(self.XG)
        self.MXG.add_edge("s", "u", weight=15)
        self.XG2 = nx.DiGraph()
        self.XG2.add_weighted_edges_from(
            [[1, 4, 1], [4, 5, 1], [5, 6, 1], [6, 3, 1], [1, 3, 50], [1, 2, 100], [2, 3, 100]]
        )

        self.XG3 = nx.Graph()
        self.XG3.add_weighted_edges_from([[0, 1, 2], [1, 2, 12], [2, 3, 1], [3, 4, 5], [4, 5, 1], [5, 0, 10]])

        self.XG4 = nx.Graph()
        self.XG4.add_weighted_edges_from(
            [[0, 1, 2], [1, 2, 2], [2, 3, 1], [3, 4, 1], [4, 5, 1], [5, 6, 1], [6, 7, 1], [7, 0, 1]]
        )
        self.MXG4 = nx.MultiGraph(self.XG4)
        self.MXG4.add_edge(0, 1, weight=3)
        self.G = nx.DiGraph()  # no weights
        self.G.add_edges_from(
            [
                ("s", "u"),
                ("s", "x"),
                ("u", "v"),
                ("u", "x"),
                ("v", "y"),
                ("x", "u"),
                ("x", "v"),
                ("x", "y"),
                ("y", "s"),
                ("y", "v"),
            ]
        )

    def setUp(self):
        self.P3 = nx.path_graph(3)
        self.P4 = nx.path_graph(4)
        self.K5 = nx.complete_graph(5)

        self.C4 = nx.cycle_graph(4)
        self.C5 = nx.cycle_graph(5)

        self.T = nx.balanced_tree(r=2, h=2)

        self.Gb = nx.DiGraph()
        self.Gb.add_edges_from([(0, 1), (0, 2), (0, 4), (2, 1),
                                (2, 3), (4, 3)])

def test_tensor_product_classic_result():
    K2 = nx.complete_graph(2)
    G = nx.petersen_graph()
    G = tensor_product(G,K2)
    assert_true(nx.is_isomorphic(G,nx.desargues_graph()))

    G = nx.cycle_graph(5)
    G = tensor_product(G,K2)
    assert_true(nx.is_isomorphic(G,nx.cycle_graph(10)))

    G = nx.tetrahedral_graph()
    G = tensor_product(G,K2)
    assert_true(nx.is_isomorphic(G,nx.cubical_graph()))

 def setUp(self):
     self.path = nx.path_graph(7)
     self.directed_path = nx.path_graph(7, create_using=nx.DiGraph())
     self.cycle = nx.cycle_graph(7)
     self.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
     self.gnp = nx.gnp_random_graph(30, 0.1)
     self.directed_gnp = nx.gnp_random_graph(30, 0.1, directed=True)
     self.K20 = nx.complete_graph(20)
     self.K10 = nx.complete_graph(10)
     self.K5 = nx.complete_graph(5)
     self.G_list = [self.path, self.directed_path, self.cycle,
         self.directed_cycle, self.gnp, self.directed_gnp, self.K10, 
         self.K5, self.K20]

    def test_from_numpy_matrix_type(self):
        A = np.matrix([[1]])
        G = nx.from_numpy_matrix(A)
        assert_equal(type(G[0][0]['weight']), int)

        A = np.matrix([[1]]).astype(np.float)
        G = nx.from_numpy_matrix(A)
        assert_equal(type(G[0][0]['weight']), float)

        A = np.matrix([[1]]).astype(np.str)
        G = nx.from_numpy_matrix(A)
        assert_equal(type(G[0][0]['weight']), str)

        A = np.matrix([[1]]).astype(np.bool)
        G = nx.from_numpy_matrix(A)
        assert_equal(type(G[0][0]['weight']), bool)

        A = np.matrix([[1]]).astype(np.complex)
        G = nx.from_numpy_matrix(A)
        assert_equal(type(G[0][0]['weight']), complex)

        A = np.matrix([[1]]).astype(np.object)
        assert_raises(TypeError, nx.from_numpy_matrix, A)

        G = nx.cycle_graph(3)
        A = nx.adj_matrix(G).todense()
        H = nx.from_numpy_matrix(A)
        assert_true(all(type(m) == int and type(n) == int for m, n in H.edges()))
        H = nx.from_numpy_array(A)
        assert_true(all(type(m) == int and type(n) == int for m, n in H.edges()))

def test_directed_edge_connectivity():
    G = nx.cycle_graph(10, create_using=nx.DiGraph()) # only one direction
    D = nx.cycle_graph(10).to_directed() # 2 reciprocal edges
    for flow_func in flow_funcs:
        assert_equal(1, nx.edge_connectivity(G, flow_func=flow_func),
                     msg=msg.format(flow_func.__name__))
        assert_equal(1, local_edge_connectivity(G, 1, 4, flow_func=flow_func),
                     msg=msg.format(flow_func.__name__))
        assert_equal(1, nx.edge_connectivity(G, 1, 4, flow_func=flow_func),
                     msg=msg.format(flow_func.__name__))
        assert_equal(2, nx.edge_connectivity(D, flow_func=flow_func),
                     msg=msg.format(flow_func.__name__))
        assert_equal(2, local_edge_connectivity(D, 1, 4, flow_func=flow_func),
                     msg=msg.format(flow_func.__name__))
        assert_equal(2, nx.edge_connectivity(D, 1, 4, flow_func=flow_func),
                     msg=msg.format(flow_func.__name__))

    def test_graph(self):
        g = nx.cycle_graph(10)
        G = nx.Graph()
        G.add_nodes_from(g)
        G.add_weighted_edges_from((u, v, u) for u, v in g.edges())

        # Dict of dicts
        dod = to_dict_of_dicts(G)
        GG = from_dict_of_dicts(dod, create_using=nx.Graph())
        assert_nodes_equal(sorted(G.nodes()), sorted(GG.nodes()))
        assert_edges_equal(sorted(G.edges()), sorted(GG.edges()))
        GW = to_networkx_graph(dod, create_using=nx.Graph())
        assert_nodes_equal(sorted(G.nodes()), sorted(GW.nodes()))
        assert_edges_equal(sorted(G.edges()), sorted(GW.edges()))
        GI = nx.Graph(dod)
        assert_equal(sorted(G.nodes()), sorted(GI.nodes()))
        assert_equal(sorted(G.edges()), sorted(GI.edges()))

        # Dict of lists
        dol = to_dict_of_lists(G)
        GG = from_dict_of_lists(dol, create_using=nx.Graph())
        # dict of lists throws away edge data so set it to none
        enone = [(u, v, {}) for (u, v, d) in G.edges(data=True)]
        assert_nodes_equal(sorted(G.nodes()), sorted(GG.nodes()))
        assert_edges_equal(enone, sorted(GG.edges(data=True)))
        GW = to_networkx_graph(dol, create_using=nx.Graph())
        assert_nodes_equal(sorted(G.nodes()), sorted(GW.nodes()))
        assert_edges_equal(enone, sorted(GW.edges(data=True)))
        GI = nx.Graph(dol)
        assert_nodes_equal(sorted(G.nodes()), sorted(GI.nodes()))
        assert_edges_equal(enone, sorted(GI.edges(data=True)))

 def test_C4(self):
     """Edge betweenness centrality: C4"""
     G=nx.cycle_graph(4)
     b=nx.edge_betweenness_centrality(G, weight='weight', normalized=False)
     b_answer={(0, 1):2,(0, 3):2, (1, 2):2, (2, 3): 2}
     for n in sorted(G.edges()):
         assert_almost_equal(b[n],b_answer[n])

    def test_cycle_graph(self):
        """Tests that the cycle graph on five vertices is strongly
        regular.

        """
        G = nx.cycle_graph(5)
        assert_true(is_strongly_regular(G))

    def test_valid_not_path(self):
        G = nx.cycle_graph(4)
        G.add_edge(0, 4)
        G.add_edge(1, 4)
        G.add_edge(5, 2)

        assert_true(nx.is_perfect_matching(G, {(1, 4), (0, 3), (5, 2)}))

def test_biconnected_component_subgraphs_cycle():
    G=nx.cycle_graph(3)
    G.add_cycle([1,3,4,5])
    G.add_edge(1,3,eattr='red')  # test copying of edge data
    G.node[1]['nattr']='blue'
    G.graph['gattr']='green'
    Gc = set(biconnected.biconnected_component_subgraphs(G))
    assert_equal(len(Gc),2)
    g1,g2=Gc
    if 0 in g1:
        assert_true(nx.is_isomorphic(g1,nx.Graph([(0,1),(0,2),(1,2)])))
        assert_true(nx.is_isomorphic(g2,nx.Graph([(1,3),(1,5),(3,4),(4,5)])))
        assert_equal(g2[1][3]['eattr'],'red')
        assert_equal(g2.node[1]['nattr'],'blue')
        assert_equal(g2.graph['gattr'],'green')
        g2[1][3]['eattr']='blue'
        assert_equal(g2[1][3]['eattr'],'blue')
        assert_equal(G[1][3]['eattr'],'red')
    else:
        assert_true(nx.is_isomorphic(g1,nx.Graph([(1,3),(1,5),(3,4),(4,5)])))
        assert_true(nx.is_isomorphic(g2,nx.Graph([(0,1),(0,2),(1,2)])))
        assert_equal(g1[1][3]['eattr'],'red')
        assert_equal(g1.node[1]['nattr'],'blue')
        assert_equal(g1.graph['gattr'],'green')
        g1[1][3]['eattr']='blue'
        assert_equal(g1[1][3]['eattr'],'blue')
        assert_equal(G[1][3]['eattr'],'red')

 def test_multigraph(self):
     """Tests the edge boundary of a multigraph."""
     G = nx.MultiGraph(list(nx.cycle_graph(5).edges()) * 2)
     S = {0, 1}
     boundary = list(nx.edge_boundary(G, S))
     expected = [(0, 4), (0, 4), (1, 2), (1, 2)]
     assert_equal(boundary, expected)