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):
     G = nx.MultiGraph()
     G.add_edge(1, 2, key="first")
     G.add_edge(1, 2, key="second", color="blue")
     H = adjacency_graph(adjacency_data(G))
     nx.is_isomorphic(G, H)
     assert_equal(H[1][2]["second"]["color"], "blue")

 def test_multigraph(self):
     G = nx.MultiGraph()
     G.add_edge(1, 2, key='first')
     G.add_edge(1, 2, key='second', color='blue')
     H = node_link_graph(node_link_data(G))
     nx.is_isomorphic(G, H)
     assert_equal(H[1][2]['second']['color'], 'blue')

 def test_graph(self):
     G = nx.DiGraph()
     G.add_nodes_from([1, 2, 3], color='red')
     G.add_edge(1, 2, foo=7)
     G.add_edge(1, 3, foo=10)
     G.add_edge(3, 4, foo=10)
     H = tree_graph(tree_data(G, 1))
     nx.is_isomorphic(G, H)

 def test_node_input(self):
     G = nx.grid_2d_graph(4, 2, periodic=True)
     H = nx.grid_2d_graph(range(4), range(2), periodic=True)
     assert_true(nx.is_isomorphic(H, G))
     H = nx.grid_2d_graph("abcd", "ef", periodic=True)
     assert_true(nx.is_isomorphic(H, G))
     G = nx.grid_2d_graph(5, 6)
     H = nx.grid_2d_graph(range(5), range(6))
     assert_edges_equal(H, G)

 def test_empty_subgraph(self):
     # Subgraph of an empty graph is an empty graph. test 1
     nullgraph = nx.null_graph()
     E5 = nx.empty_graph(5)
     E10 = nx.empty_graph(10)
     H = E10.subgraph([])
     assert_true(nx.is_isomorphic(H, nullgraph))
     H = E10.subgraph([1, 2, 3, 4, 5])
     assert_true(nx.is_isomorphic(H, E5))

 def test_triangle_graph(self):
     G = nx.complete_graph(3)
     H = nx.inverse_line_graph(G)
     alternative_solution = nx.Graph()
     alternative_solution.add_edges_from([[0, 1], [0, 2], [0, 3]])
     # there are two alternative inverse line graphs for this case
     # so long as we get one of them the test should pass
     assert_true(nx.is_isomorphic(H, G) or
                 nx.is_isomorphic(H, alternative_solution))

def test_expected_degree_graph():
    # test that fixed seed delivers the same graph
    deg_seq = [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
    G1 = nx.expected_degree_graph(deg_seq, seed=1000)
    G2 = nx.expected_degree_graph(deg_seq, seed=1000)
    assert_true(nx.is_isomorphic(G1, G2))

    G1 = nx.expected_degree_graph(deg_seq, seed=10)
    G2 = nx.expected_degree_graph(deg_seq, seed=10)
    assert_true(nx.is_isomorphic(G1, G2))

 def test_remove_one_contig(self):
     my_graph = nx.Graph()
     my_graph.add_edges_from([('Contig1', 'Contig2'), ('Contig1', 'Contig3'), ('Contig1', 'Contig4')])
     remove_contigs = RemoveContigs(my_graph)
     expected_graph = nx.Graph()
     expected_graph.add_nodes_from(['Contig2', 'Contig3', 'Contig4'])
     remove_contigs.remove_contigs_high_degree()
     self.assertTrue(nx.is_isomorphic(expected_graph, remove_contigs.graph))
     remove_contigs.remove_extra_contigs()
     self.assertTrue(nx.is_isomorphic(nx.Graph(), remove_contigs.graph))

    def test_random_seed(self):
        """Tests that each call with the same random seed generates the
        same graph.

        """
        deg_seq = [3] * 12
        G1 = nx.configuration_model(deg_seq, seed=1000)
        G2 = nx.configuration_model(deg_seq, seed=1000)
        assert_true(nx.is_isomorphic(G1, G2))
        G1 = nx.configuration_model(deg_seq, seed=10)
        G2 = nx.configuration_model(deg_seq, seed=10)
        assert_true(nx.is_isomorphic(G1, G2))

    def test_navigable_small_world(self):
        G = nx.navigable_small_world_graph(5, p=1, q=0)
        gg = nx.grid_2d_graph(5, 5).to_directed()
        assert_true(nx.is_isomorphic(G, gg))

        G = nx.navigable_small_world_graph(5, p=1, q=0, dim=3)
        gg = nx.grid_graph([5, 5, 5]).to_directed()
        assert_true(nx.is_isomorphic(G, gg))

        G = nx.navigable_small_world_graph(5, p=1, q=0, dim=1)
        gg = nx.grid_graph([5]).to_directed()
        assert_true(nx.is_isomorphic(G, gg))

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_ego(self):
     G=nx.star_graph(3)
     H=nx.ego_graph(G,0)
     assert_true(nx.is_isomorphic(G,H))
     G.add_edge(1,11)
     G.add_edge(2,22)
     G.add_edge(3,33)
     H=nx.ego_graph(G,0)
     assert_true(nx.is_isomorphic(nx.star_graph(3),H))
     G=nx.path_graph(3)
     H=nx.ego_graph(G,0)
     assert_equal(H.edges(), [(0, 1)])

def test_cartesian_product_classic():
    # test some classic product graphs
    P2 = nx.path_graph(2)
    P3 = nx.path_graph(3)
    # cube = 2-path X 2-path
    G=cartesian_product(P2,P2)
    G=cartesian_product(P2,G)
    assert_true(nx.is_isomorphic(G,nx.cubical_graph()))

    # 3x3 grid
    G=cartesian_product(P3,P3)
    assert_true(nx.is_isomorphic(G,nx.grid_2d_graph(3,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 check_counterexample(G, sub_graph):
    """Raises an exception if the counterexample is wrong.

    Parameters
    ----------
    G : NetworkX graph
    subdivision_nodes : set
        A set of nodes inducing a subgraph as a counterexample
    """
    # 1. Create the sub graph
    sub_graph = nx.Graph(sub_graph)

    # 2. Remove self loops
    for u in sub_graph:
        if sub_graph.has_edge(u, u):
            sub_graph.remove_edge(u, u)

    # keep track of nodes we might need to contract
    contract = list(sub_graph)

    # 3. Contract Edges
    while len(contract) > 0:
        contract_node = contract.pop()
        if contract_node not in sub_graph:
            # Node was already contracted
            continue
        degree = sub_graph.degree[contract_node]
        # Check if we can remove the node
        if degree == 2:
            # Get the two neighbors
            neighbors = iter(sub_graph[contract_node])
            u = next(neighbors)
            v = next(neighbors)
            # Save nodes for later
            contract.append(u)
            contract.append(v)
            # Contract edge
            sub_graph.remove_node(contract_node)
            sub_graph.add_edge(u, v)

    # 4. Check for isomorphism with K5 or K3_3 graphs
    if len(sub_graph) == 5:
        if not nx.is_isomorphic(nx.complete_graph(5), sub_graph):
            raise nx.NetworkXException("Bad counter example.")
    elif len(sub_graph) == 6:
        if not nx.is_isomorphic(nx.complete_bipartite_graph(3, 3), sub_graph):
            raise nx.NetworkXException("Bad counter example.")
    else:
        raise nx.NetworkXException("Bad counter example.")

def test_simple():
    # 16 simple tests
    w = True
    rtol = 1e-6
    atol = 1e-9
    edges = [(0,0,1),(0,0,1.5),(0,1,2),(1,0,3)]
    for g1 in [nx.Graph(weighted=w), 
               nx.DiGraph(weighted=w),
               nx.MultiGraph(weighted=w),
               nx.MultiDiGraph(weighted=w)
               ]:

        print g1.__class__
        g1.add_weighted_edges_from(edges)
        g2 = g1.subgraph(g1.nodes())
        assert_true( nx.is_isomorphic(g1,g2,True,rtol,atol) )

        for mod1, mod2 in [(False, True), (True, False), (True, True)]:
            # mod1 tests a regular edge
            # mod2 tests a selfloop
            print "Modification:", mod1, mod2
            if g2.is_multigraph():
                if mod1:
                    data1 = {0:{'weight':10}}
                if mod2:
                    data2 = {0:{'weight':1},1:{'weight':2.5}}
            else:
                if mod1:
                    data1 = {'weight':10}
                if mod2:
                    data2 = {'weight':2.5}

            g2 = g1.subgraph(g1.nodes())
            if mod1:
                if not g1.is_directed():
                    g2.adj[1][0] = data1
                    g2.adj[0][1] = data1
                else:
                    g2.succ[1][0] = data1
                    g2.pred[0][1] = data1
            if mod2:
                if not g1.is_directed():
                    g2.adj[0][0] = data2
                else:
                    g2.succ[0][0] = data2
                    g2.pred[0][0] = data2

            assert_false(nx.is_isomorphic(g1,g2,True,rtol,atol))

def test_spectral_graph_forge():
    numpy = 1  # nosetests attribute, use nosetests -a 'not numpy' to skip test
    scipy = 1

    try:
        import numpy
    except ImportError:
        raise SkipTest('NumPy not available.')
    try:
        import scipy
    except ImportError:
        raise SkipTest("SciPy not available")

    G = karate_club_graph()

    seed = 54321

    # common cases, just checking node number preserving and difference
    # between identity and modularity cases
    H = spectral_graph_forge(G, 0.1, transformation='identity', seed=seed)
    assert_nodes_equal(G, H)

    I = spectral_graph_forge(G, 0.1, transformation='identity', seed=seed)
    assert_nodes_equal(G, H)
    assert_true(is_isomorphic(I, H))

    I = spectral_graph_forge(G, 0.1, transformation='modularity', seed=seed)
    assert_nodes_equal(G, I)

    assert_false(is_isomorphic(I, H))

    # with all the eigenvectors, output graph is identical to the input one
    H = spectral_graph_forge(G, 1, transformation='modularity', seed=seed)
    assert_nodes_equal(G, H)
    assert_true(is_isomorphic(G, H))

    # invalid alpha input value, it is silently truncated in [0,1]
    H = spectral_graph_forge(G, -1, transformation='identity', seed=seed)
    assert_nodes_equal(G, H)

    H = spectral_graph_forge(G, 10, transformation='identity', seed=seed)
    assert_nodes_equal(G, H)
    assert_true(is_isomorphic(G, H))

    # invalid transformation mode, checking the error raising
    assert_raises(NetworkXError,
                  spectral_graph_forge, G, 0.1, transformation='unknown',
                  seed=seed)

def test_simple():
    # 16 simple tests
    w = 'weight'
    edges = [(0, 0, 1), (0, 0, 1.5), (0, 1, 2), (1, 0, 3)]
    for g1 in [nx.Graph(),
               nx.DiGraph(),
               nx.MultiGraph(),
               nx.MultiDiGraph(),
               ]:

        g1.add_weighted_edges_from(edges)
        g2 = g1.subgraph(g1.nodes())
        if g1.is_multigraph():
            em = iso.numerical_multiedge_match('weight', 1)
        else:
            em = iso.numerical_edge_match('weight', 1)
        assert_true( nx.is_isomorphic(g1, g2, edge_match=em) )

        for mod1, mod2 in [(False, True), (True, False), (True, True)]:
            # mod1 tests a regular edge
            # mod2 tests a selfloop
            if g2.is_multigraph():
                if mod1:
                    data1 = {0: {'weight': 10}}
                if mod2:
                    data2 = {0: {'weight': 1}, 1: {'weight': 2.5}}
            else:
                if mod1:
                    data1 = {'weight': 10}
                if mod2:
                    data2 = {'weight': 2.5}

            g2 = g1.subgraph(g1.nodes()).copy()
            if mod1:
                if not g1.is_directed():
                    g2._adj[1][0] = data1
                    g2._adj[0][1] = data1
                else:
                    g2._succ[1][0] = data1
                    g2._pred[0][1] = data1
            if mod2:
                if not g1.is_directed():
                    g2._adj[0][0] = data2
                else:
                    g2._succ[0][0] = data2
                    g2._pred[0][0] = data2

            assert_false(nx.is_isomorphic(g1, g2, edge_match=em))

def test_stochastic():
    G = nx.DiGraph()
    G.add_edge(0, 1)
    G.add_edge(0, 2)
    S = nx.stochastic_graph(G)
    assert_true(nx.is_isomorphic(G, S))
    assert_equal(sorted(S.edges(data=True)), [(0, 1, {"weight": 0.5}), (0, 2, {"weight": 0.5})])