def test_barbell():
    G = nx.barbell_graph(8, 4)
    nx.add_path(G, [7, 20, 21, 22])
    nx.add_cycle(G, [22, 23, 24, 25])
    pts = set(nx.articulation_points(G))
    assert_equal(pts, {7, 8, 9, 10, 11, 12, 20, 21, 22})

    answer = [
        {12, 13, 14, 15, 16, 17, 18, 19},
        {0, 1, 2, 3, 4, 5, 6, 7},
        {22, 23, 24, 25},
        {11, 12},
        {10, 11},
        {9, 10},
        {8, 9},
        {7, 8},
        {21, 22},
        {20, 21},
        {7, 20},
    ]
    assert_components_equal(list(nx.biconnected_components(G)), answer)

    G.add_edge(2,17)
    pts = set(nx.articulation_points(G))
    assert_equal(pts, {7, 20, 21, 22})

def test_is_aperiodic_disconnected():
    # disconnected graph
    G = nx.DiGraph()
    nx.add_cycle(G, [1, 2, 3, 4])
    nx.add_cycle(G, [5, 6, 7, 8])
    assert_false(nx.is_aperiodic(G))
    G.add_edge(1, 3)
    G.add_edge(5, 7)
    assert_true(nx.is_aperiodic(G))

 def test_eulerian_circuit_multigraph(self):
     G=nx.MultiGraph()
     nx.add_cycle(G, [0, 1, 2, 3])
     G.add_edge(1,2)
     G.add_edge(1,2)
     edges=list(eulerian_circuit(G,source=0))
     nodes=[u for u,v in edges]
     assert_equal(nodes,[0,3,2,1,2,1])
     assert_equal(edges,[(0,3),(3,2),(2,1),(1,2),(2,1),(1,0)])

 def test_weighted(self):
     G = nx.Graph()
     nx.add_cycle(G, range(7), weight=2)
     ans = nx.average_shortest_path_length(G, weight='weight')
     assert_almost_equal(ans, 4)
     G = nx.Graph()
     nx.add_path(G, range(5), weight=2)
     ans = nx.average_shortest_path_length(G, weight='weight')
     assert_almost_equal(ans, 4)

 def test_simple_cycles_small(self):
     G = nx.DiGraph()
     nx.add_cycle(G, [1, 2, 3])
     c = sorted(nx.simple_cycles(G))
     assert_equal(len(c), 1)
     assert_true(self.is_cyclic_permutation(c[0], [1, 2, 3]))
     nx.add_cycle(G, [10, 20, 30])
     cc = sorted(nx.simple_cycles(G))
     ca = [[1, 2, 3], [10, 20, 30]]
     for c in cc:
         assert_true(any(self.is_cyclic_permutation(c, rc) for rc in ca))

 def test_multigraph_with_keys(self):
     G = nx.MultiGraph()
     nx.add_cycle(G, [0, 1, 2, 3])
     G.add_edge(1, 2)
     G.add_edge(1, 2)
     edges = list(eulerian_circuit(G, source=0, keys=True))
     nodes = [u for u, v, k in edges]
     assert_equal(nodes, [0, 3, 2, 1, 2, 1])
     assert_equal(edges[:2], [(0, 3, 0), (3, 2, 0)])
     assert_count_equal(edges[2:5], [(2, 1, 0), (1, 2, 1), (2, 1, 2)])
     assert_equal(edges[5:], [(1, 0, 0)])

def test_large_clique_size():
    G = nx.complete_graph(9)
    nx.add_cycle(G, [9, 10, 11])
    G.add_edge(8, 9)
    G.add_edge(1, 12)
    G.add_node(13)

    assert_equal(large_clique_size(G), 9)
    G.remove_node(5)
    assert_equal(large_clique_size(G), 8)
    G.remove_edge(2, 3)
    assert_equal(large_clique_size(G), 7)

def test_biconnected_component_subgraphs_cycle():
    G=nx.cycle_graph(3)
    nx.add_cycle(G, [1, 3, 4, 5])
    Gc = set(nx.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)])))
    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)])))

    def test_eulerian_circuit_digraph(self):
        G=nx.DiGraph()
        nx.add_cycle(G, [0, 1, 2, 3])

        edges=list(eulerian_circuit(G,source=0))
        nodes=[u for u,v in edges]
        assert_equal(nodes,[0,1,2,3])
        assert_equal(edges,[(0,1),(1,2),(2,3),(3,0)])

        edges=list(eulerian_circuit(G,source=1))
        nodes=[u for u,v in edges]
        assert_equal(nodes,[1,2,3,0])
        assert_equal(edges,[(1,2),(2,3),(3,0),(0,1)])

    def test_add_cycle(self):
        G = self.G.copy()
        nlist = [12, 13, 14, 15]
        oklists = [[(12, 13), (12, 15), (13, 14), (14, 15)],
                   [(12, 13), (13, 14), (14, 15), (15, 12)]]
        nx.add_cycle(G, nlist)
        assert_true(sorted(G.edges(nlist)) in oklists)
        G = self.G.copy()
        oklists = [[(12, 13, {'weight': 1.}),
                    (12, 15, {'weight': 1.}),
                    (13, 14, {'weight': 1.}),
                    (14, 15, {'weight': 1.})],
                   [(12, 13, {'weight': 1.}),
                    (13, 14, {'weight': 1.}),
                    (14, 15, {'weight': 1.}),
                    (15, 12, {'weight': 1.})]]
        nx.add_cycle(G, nlist, weight=1.0)
        assert_true(sorted(G.edges(nlist, data=True)) in oklists)

        G = self.G.copy()
        nlist = [12]
        nx.add_cycle(G, nlist)
        assert_nodes_equal(G, list(self.G) + nlist)

        G = self.G.copy()
        nlist = []
        nx.add_cycle(G, nlist)
        assert_nodes_equal(G.nodes, self.Gnodes)
        assert_edges_equal(G.edges, self.G.edges)

 def test_cycle_basis(self):
     G=self.G
     cy=networkx.cycle_basis(G,0)
     sort_cy= sorted( sorted(c) for c in cy )
     assert_equal(sort_cy, [[0,1,2,3],[0,1,6,7,8],[0,3,4,5]])
     cy=networkx.cycle_basis(G,1)
     sort_cy= sorted( sorted(c) for c in cy )
     assert_equal(sort_cy, [[0,1,2,3],[0,1,6,7,8],[0,3,4,5]])
     cy=networkx.cycle_basis(G,9)
     sort_cy= sorted( sorted(c) for c in cy )
     assert_equal(sort_cy, [[0,1,2,3],[0,1,6,7,8],[0,3,4,5]])
     # test disconnected graphs
     nx.add_cycle(G, "ABC")
     cy=networkx.cycle_basis(G,9)
     sort_cy= sorted(sorted(c) for c in cy[:-1]) + [sorted(cy[-1])]
     assert_equal(sort_cy, [[0,1,2,3],[0,1,6,7,8],[0,3,4,5],['A','B','C']])

 def test_specified_methods(self):
     G = nx.Graph()
     nx.add_cycle(G, range(7), weight=2)
     ans = nx.average_shortest_path_length(G,
                                           weight='weight',
                                           method='dijkstra')
     assert_almost_equal(ans, 4)
     ans = nx.average_shortest_path_length(G,
                                           weight='weight',
                                           method='bellman-ford')
     assert_almost_equal(ans, 4)
     G = nx.Graph()
     nx.add_path(G, range(5), weight=2)
     ans = nx.average_shortest_path_length(G,
                                           weight='weight',
                                           method='dijkstra')
     assert_almost_equal(ans, 4)
     ans = nx.average_shortest_path_length(G,
                                           weight='weight',
                                           method='bellman-ford')
     assert_almost_equal(ans, 4)

 def setUp(self):
     G = networkx.Graph()
     nx.add_cycle(G, [0, 1, 2, 3])
     nx.add_cycle(G, [0, 3, 4, 5])
     nx.add_cycle(G, [0, 1, 6, 7, 8])
     G.add_edge(8, 9)
     self.G = G

def test_biconnected_components2():
    G=nx.Graph()
    nx.add_cycle(G, 'ABC')
    nx.add_cycle(G, 'CDE')
    nx.add_cycle(G, 'FIJHG')
    nx.add_cycle(G, 'GIJ')
    G.add_edge('E','G')
    comps = list(nx.biconnected_component_edges(G))
    answer = [
        [tuple('GF'), tuple('FI'), tuple('IG'), tuple('IJ'),
         tuple('JG'), tuple('JH'), tuple('HG')],
        [tuple('EG')],
        [tuple('CD'), tuple('DE'), tuple('CE')],
        [tuple('AB'), tuple('BC'), tuple('AC')]
        ]
    assert_components_edges_equal(comps, answer)

 def test_weighted(self):
     G = nx.Graph()
     nx.add_cycle(G, [0, 1, 2], weight=2)
     vitality = nx.closeness_vitality(G, weight='weight')
     assert_equal(vitality, {0: 4, 1: 4, 2: 4})

 def test_directed_cycle_numpy(self):
     G = nx.DiGraph()
     nx.add_cycle(G, [0, 1, 2, 3])
     pred, dist = nx.floyd_warshall_predecessor_and_distance(G)
     D = nx.utils.dict_to_numpy_array(dist)
     assert_equal(nx.floyd_warshall_numpy(G), D)

def test_is_aperiodic_disconnected2():
    G = nx.DiGraph()
    nx.add_cycle(G, [0, 1, 2])
    G.add_edge(3, 3)
    assert_false(nx.is_aperiodic(G))

 def test_not_connected(self):
     G = nx.cycle_graph(4)
     nx.add_cycle(G, [5, 6, 7])
     assert_false(nx.is_distance_regular(G))

def test_is_aperiodic_selfloop():
    G = nx.DiGraph()
    nx.add_cycle(G, [1, 2, 3, 4])
    G.add_edge(1, 1)
    assert_true(nx.is_aperiodic(G))

def test_is_aperiodic_cycle3():
    G = nx.DiGraph()
    nx.add_cycle(G, [1, 2, 3, 4])
    nx.add_cycle(G, [3, 4, 5, 6])
    assert_false(nx.is_aperiodic(G))