def test_all_simple_paths_multigraph():
    G = nx.MultiGraph([(1, 2), (1, 2)])
    paths = nx.all_simple_paths(G, 1, 1)
    assert_equal(paths, [])
    nx.add_path(G, [3, 1, 10, 2])
    paths = nx.all_simple_paths(G, 1, 2)
    assert_equal(set(tuple(p) for p in paths), {(1, 2), (1, 2), (1, 10, 2)})

def test_bidirectional_dijkstra_ignore():
    G = nx.Graph()
    nx.add_path(G, [1, 2, 10])
    nx.add_path(G, [1, 3, 10])
    assert_raises(
        nx.NetworkXNoPath,
        _bidirectional_dijkstra,
        G,
        1, 2,
        ignore_nodes=[1],
    )
    assert_raises(
        nx.NetworkXNoPath,
        _bidirectional_dijkstra,
        G,
        1, 2,
        ignore_nodes=[2],
    )
    assert_raises(
        nx.NetworkXNoPath,
        _bidirectional_dijkstra,
        G,
        1, 2,
        ignore_nodes=[1, 2],
    )

def test_preflow_push_makes_enough_space():
    #From ticket #1542
    G = nx.DiGraph()
    nx.add_path(G, [0, 1, 3], capacity=1)
    nx.add_path(G, [1, 2, 3], capacity=1)
    R = preflow_push(G, 0, 3, value_only=False)
    assert_equal(R.graph['flow_value'], 1)

 def test_edges_with_data_not_equal(self):
     G = nx.MultiGraph()
     nx.add_path(G, [0, 1, 2], weight=1)
     H = nx.MultiGraph()
     nx.add_path(H, [0, 1, 2], weight=2)
     self._test_not_equal(G.edges(data=True, keys=True),
                          H.edges(data=True, keys=True))

 def setUp(self):
     #
     #       -- s1 --
     #     /     |    \
     #   c1-----c2----c3
     #  /  \   / | \    \
     # r1  r2 r3 r4 r5  r6
     #
     topo = fnss.Topology()
     icr_candidates = ["c1", "c2", "c3"]
     nx.add_path(topo, icr_candidates)
     topo.add_edge("c1", "s1")
     topo.add_edge("c2", "s1")
     topo.add_edge("c3", "s1")
     topo.add_edge("c1", "r1")
     topo.add_edge("c1", "r2")
     topo.add_edge("c2", "r3")
     topo.add_edge("c2", "r4")
     topo.add_edge("c2", "r5")
     topo.add_edge("c3", "r6")
     topo.graph['icr_candidates'] = set(icr_candidates)
     for router in icr_candidates:
         fnss.add_stack(topo, router, 'router')
     for src in ['s1']:
         fnss.add_stack(topo, src, 'source')
     for rcv in ['r1', 'r2', 'r3', 'r4', 'r5', 'r6']:
         fnss.add_stack(topo, rcv, 'receiver')
     self.topo = cacheplacement.IcnTopology(topo)

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 nrr_topology(cls):
     """Return topology for testing NRR caching strategies
     """
     # Topology sketch
     #
     # 0 ---- 2----- 4
     #        |       \
     #        |        s
     #        |       /
     # 1 ---- 3 ---- 5
     #
     topology = IcnTopology(fnss.Topology())
     nx.add_path(topology, [0, 2, 4, "s", 5, 3, 1])
     topology.add_edge(2, 3)
     receivers = (0, 1)
     source = "s"
     caches = (2, 3, 4, 5)
     contents = (1, 2, 3, 4)
     fnss.add_stack(topology, source, 'source', {'contents': contents})
     for v in caches:
         fnss.add_stack(topology, v, 'router', {'cache_size': 1})
     for v in receivers:
         fnss.add_stack(topology, v, 'receiver', {})
     fnss.set_delays_constant(topology, 1, 'ms')
     return topology

def test_notarborescence2():
    # Not an arborescence due to in-degree violation.
    G = nx.MultiDiGraph()
    nx.add_path(G, range(5))
    G.add_edge(6, 4)
    assert_false(nx.is_branching(G))
    assert_false(nx.is_arborescence(G))

def test_not_connected():
    G = nx.Graph()
    nx.add_path(G, [1, 2, 3])
    nx.add_path(G, [4, 5])
    for interface_func in [nx.minimum_edge_cut, nx.minimum_node_cut]:
        for flow_func in flow_funcs:
            assert_raises(nx.NetworkXError, interface_func, G, flow_func=flow_func)

 def test_path(self):
     path = list(range(10))
     shuffle(path)
     G = nx.Graph()
     nx.add_path(G, path)
     for method in self._methods:
         order = nx.spectral_ordering(G, method=method)
         ok_(order in [path, list(reversed(path))])

 def compare_graph_paths_names(g, paths, names):
     expected = nx.DiGraph()
     for p in paths:
         nx.add_path(expected, p)
     assert_equal(sorted(expected.nodes), sorted(g.nodes))
     assert_equal(sorted(expected.edges()), sorted(g.edges()))
     g_names = [g.get_edge_data(s, e)['Name'] for s, e in g.edges()]
     assert_equal(names, sorted(g_names))

 def test_P5_multiple_target(self):
     """Betweenness centrality: P5 multiple target"""
     G = nx.Graph()
     nx.add_path(G, range(5))
     b_answer = {0: 0, 1: 1, 2: 1, 3: 0.5, 4: 0, 5: 0}
     b = nx.betweenness_centrality_subset(G, sources=[0], targets=[3, 4],
                                          weight=None)
     for n in sorted(G):
         assert_almost_equal(b[n], b_answer[n])

 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_P5(self):
     """Betweenness Centrality Subset: P5"""
     G = nx.Graph()
     nx.add_path(G, range(5))
     b_answer = {0: 0, 1: 0.5, 2: 0.5, 3: 0, 4: 0, 5: 0}
     b = nx.betweenness_centrality_subset(G, sources=[0], targets=[3],
                                          weight=None)
     for n in sorted(G):
         assert_almost_equal(b[n], b_answer[n])

 def setUp(self):
     deg=[3,2,2,1,0]
     self.G=havel_hakimi_graph(deg)
     self.P=nx.path_graph(3)
     self.WG=nx.Graph( (u,v,{'weight':0.5,'other':0.3})
             for (u,v) in self.G.edges() )
     self.WG.add_node(4)
     self.DG=nx.DiGraph()
     nx.add_path(self.DG, [0,1,2])

 def setUp(self):
     self.P4=nx.path_graph(4)
     self.D=nx.DiGraph()
     self.D.add_edges_from([(0, 2), (0, 3), (1, 3), (2, 3)])
     self.M=nx.MultiGraph()
     nx.add_path(self.M, range(4))
     self.M.add_edge(0,1)
     self.S=nx.Graph()
     self.S.add_edges_from([(0,0),(1,1)])

def test_not_connected():
    G = nx.Graph()
    nx.add_path(G, [1, 2, 3])
    nx.add_path(G, [4, 5])
    for flow_func in flow_funcs:
        assert_equal(nx.node_connectivity(G), 0,
                     msg=msg.format(flow_func.__name__))
        assert_equal(nx.edge_connectivity(G), 0,
                     msg=msg.format(flow_func.__name__))

 def test_directed_path_normalized(self):
     """Betweenness centrality: directed path normalized"""
     G=nx.DiGraph()
     nx.add_path(G, [0, 1, 2])
     b=nx.betweenness_centrality(G,
                                       weight=None,
                                       normalized=True)
     b_answer={0: 0.0, 1: 0.5, 2: 0.0}
     for n in sorted(G):
         assert_almost_equal(b[n],b_answer[n])

 def test_path(self):
     # based on setupClass numpy is installed if we get here
     from numpy.random import shuffle
     path = list(range(10))
     shuffle(path)
     G = nx.Graph()
     nx.add_path(G, path)
     for method in self._methods:
         order = nx.spectral_ordering(G, method=method)
         ok_(order in [path, list(reversed(path))])

 def test_all_pairs_connectivity_directed(self):
     G = nx.DiGraph()
     nodes = [0, 1, 2, 3]
     nx.add_path(G, nodes)
     A = {n: {} for n in G}
     for u, v in itertools.permutations(nodes, 2):
         A[u][v] = nx.node_connectivity(G, u, v)
     C = nx.all_pairs_node_connectivity(G)
     assert_equal(sorted((k, sorted(v)) for k, v in A.items()),
                  sorted((k, sorted(v)) for k, v in C.items()))