def test_single_nodes(self):
     G = nx.path_graph(1)
     vpos = nx.shell_layout(G)
     assert(vpos[0].any() == False)
     G = nx.path_graph(3)
     vpos = nx.shell_layout(G, [[0], [1,2]])
     assert(vpos[0].any() == False)

def test_set_node_attributes():
    graphs = [nx.Graph(), nx.DiGraph(), nx.MultiGraph(), nx.MultiDiGraph()]
    for G in graphs:
        # Test single value
        G = nx.path_graph(3, create_using=G)
        vals = 100
        attr = 'hello'
        nx.set_node_attributes(G, vals, attr)
        assert_equal(G.nodes[0][attr], vals)
        assert_equal(G.nodes[1][attr], vals)
        assert_equal(G.nodes[2][attr], vals)

        # Test dictionary
        G = nx.path_graph(3, create_using=G)
        vals = dict(zip(sorted(G.nodes()), range(len(G))))
        attr = 'hi'
        nx.set_node_attributes(G, vals, attr)
        assert_equal(G.nodes[0][attr], 0)
        assert_equal(G.nodes[1][attr], 1)
        assert_equal(G.nodes[2][attr], 2)

        # Test dictionary of dictionaries
        G = nx.path_graph(3, create_using=G)
        d = {'hi': 0, 'hello': 200}
        vals = dict.fromkeys(G.nodes(), d)
        vals.pop(0)
        nx.set_node_attributes(G, vals)
        assert_equal(G.nodes[0], {})
        assert_equal(G.nodes[1]["hi"], 0)
        assert_equal(G.nodes[2]["hello"], 200)

    def test_generate_sparse6(self):
        # Checked against sage encoder
        assert_equal(nx.generate_sparse6(nx.empty_graph(0)), '>>sparse6<<:?')
        assert_equal(nx.generate_sparse6(nx.empty_graph(1)), '>>sparse6<<:@')
        assert_equal(nx.generate_sparse6(nx.empty_graph(5)), '>>sparse6<<:D')
        assert_equal(nx.generate_sparse6(nx.empty_graph(68)),
                     '>>sparse6<<:[email protected]')
        assert_equal(nx.generate_sparse6(nx.empty_graph(258049)),
                     '>>sparse6<<:[email protected]')

        G1 = nx.complete_graph(4)
        assert_equal(nx.generate_sparse6(G1, header=True),
                     '>>sparse6<<:CcKI')
        assert_equal(nx.generate_sparse6(G1, header=False), ':CcKI')

        # Padding testing
        assert_equal(nx.generate_sparse6(nx.path_graph(4), header=False),
                     ':Cdv')
        assert_equal(nx.generate_sparse6(nx.path_graph(5), header=False),
                     ':DaYn')
        assert_equal(nx.generate_sparse6(nx.path_graph(6), header=False),
                     ':EaYnN')
        assert_equal(nx.generate_sparse6(nx.path_graph(7), header=False),
                     ':FaYnL')
        assert_equal(nx.generate_sparse6(nx.path_graph(8), header=False),
                     ':GaYnLz')

def test_set_edge_attributes_multi():
    graphs = [nx.MultiGraph(), nx.MultiDiGraph()]
    for G in graphs:
        # Test single value
        G = nx.path_graph(3, create_using=G)
        attr = 'hello'
        vals = 3
        nx.set_edge_attributes(G, vals, attr)
        assert_equal(G[0][1][0][attr], vals)
        assert_equal(G[1][2][0][attr], vals)

        # Test multiple values
        G = nx.path_graph(3, create_using=G)
        attr = 'hi'
        edges = [(0, 1, 0), (1, 2, 0)]
        vals = dict(zip(edges, range(len(edges))))
        nx.set_edge_attributes(G, vals, attr)
        assert_equal(G[0][1][0][attr], 0)
        assert_equal(G[1][2][0][attr], 1)

        # Test dictionary of dictionaries
        G = nx.path_graph(3, create_using=G)
        d = {'hi': 0, 'hello': 200}
        edges = [(0, 1, 0)]
        vals = dict.fromkeys(edges, d)
        nx.set_edge_attributes(G, vals)
        assert_equal(G[0][1][0]['hi'], 0)
        assert_equal(G[0][1][0]['hello'], 200)
        assert_equal(G[1][2][0], {})

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


        F = nx.florentine_families_graph()
        self.F = F

    def setup(self):
        self.G = nx.path_graph(9)
        self.DG = nx.path_graph(9, create_using=nx.DiGraph())
        self.eview = nx.EdgeView

        def modify_edge(G, e, **kwds):
            G._adj[e[0]][e[1]].update(kwds)
        self.modify_edge = modify_edge

 def test_average_shortest_path(self):
     l=nx.average_shortest_path_length(self.cycle)
     assert_almost_equal(l,2)
     l=nx.average_shortest_path_length(self.cycle,weighted=True)
     assert_almost_equal(l,2)
     l=nx.average_shortest_path_length(nx.path_graph(5))
     assert_almost_equal(l,2)
     l=nx.average_shortest_path_length(nx.path_graph(5),weighted=True)
     assert_almost_equal(l,2)

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

def CreateGraph(data):
    n = len(data)
    G = nx.Graph()
    nx.path_graph(n, G)

    for row in range(n):
        for column in range(n):
            weight = data[row][column]
            if(weight != 0):
                G.add_edge(row, column, weight= weight)
    return G

 def test_degree_graph(self):
     P3 = nx.path_graph(3)
     P5 = nx.path_graph(5)
     # silently ignore nodes not in P3
     assert_equal(dict(d for n, d in P3.degree(['A', 'B'])), {})
     # nbunch can be a graph
     assert_equal(sorted(d for n, d in P5.degree(P3)), [1, 2, 2])
     # nbunch can be a graph thats way to big
     assert_equal(sorted(d for n, d in P3.degree(P5)), [1, 1, 2])
     assert_equal(list(P5.degree([])), [])
     assert_equal(dict(P5.degree([])), {})

 def setUp(self):
     self.null = nx.null_graph()
     self.P1 = cnlti(nx.path_graph(1), first_label=1)
     self.P3 = cnlti(nx.path_graph(3), first_label=1)
     self.P10 = cnlti(nx.path_graph(10), first_label=1)
     self.K1 = cnlti(nx.complete_graph(1), first_label=1)
     self.K3 = cnlti(nx.complete_graph(3), first_label=1)
     self.K4 = cnlti(nx.complete_graph(4), first_label=1)
     self.K5 = cnlti(nx.complete_graph(5), first_label=1)
     self.K10 = cnlti(nx.complete_graph(10), first_label=1)
     self.G = nx.Graph

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_average_connectivity():
    # figure 1 from:
    # Beineke, L., O. Oellermann, and R. Pippert (2002). The average 
    # connectivity of a graph. Discrete mathematics 252(1-3), 31-45
    # http://www.sciencedirect.com/science/article/pii/S0012365X01001807
    G1 = nx.path_graph(3)
    G1.add_edges_from([(1,3),(1,4)])
    assert_equal(nx.average_node_connectivity(G1),1)
    G2 = nx.path_graph(3)
    G2.add_edges_from([(1,3),(1,4),(0,3),(0,4),(3,4)])
    assert_equal(nx.average_node_connectivity(G2),2.2)
    G3 = nx.Graph()
    assert_equal(nx.average_node_connectivity(G3),0)

    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 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 setUp(self):

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

        F = nx.florentine_families_graph()
        self.F = F

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


        F = nx.Graph() # Florentine families
        F.add_edge('Acciaiuoli','Medici')
        F.add_edge('Castellani','Peruzzi')
        F.add_edge('Castellani','Strozzi')
        F.add_edge('Castellani','Barbadori')
        F.add_edge('Medici','Barbadori')
        F.add_edge('Medici','Ridolfi')
        F.add_edge('Medici','Tornabuoni')
        F.add_edge('Medici','Albizzi')
        F.add_edge('Medici','Salviati')
        F.add_edge('Salviati','Pazzi')
        F.add_edge('Peruzzi','Strozzi')
        F.add_edge('Peruzzi','Bischeri')
        F.add_edge('Strozzi','Ridolfi')
        F.add_edge('Strozzi','Bischeri')
        F.add_edge('Ridolfi','Tornabuoni')
        F.add_edge('Tornabuoni','Guadagni')
        F.add_edge('Albizzi','Ginori')
        F.add_edge('Albizzi','Guadagni')
        F.add_edge('Bischeri','Guadagni')
        F.add_edge('Guadagni','Lamberteschi')    
        self.F = F

def test_sample_step():
    from score import SimpleDistanceEstimator as SDE
    import networkx as nx
    import choose
    import graphlearn3.test.transformutil as transformutil

    lsgg = util.test_get_grammar()
    graph = util._edenize_for_testing(nx.path_graph(4))
    graph.node[3]['label'] = '5'
    score_estimator = SDE().fit(util._edenize_for_testing(nx.path_graph(4)))
    graph,score= sample(graph, transformutil.no_transform(), lsgg, score_estimator, choose.Chooser(), n_steps=2, return_score=True)

    assert (0.000001 > abs(0.319274373045 - score)), score
    print("sambledestdone")

 def test_shortest_path_target(self):
     answer = {0: [0, 1], 1: [1], 2: [2, 1]}
     sp = nx.shortest_path(nx.path_graph(3), target=1)
     assert_equal(sp, answer)
     # with weights
     sp = nx.shortest_path(nx.path_graph(3), target=1, weight='weight')
     assert_equal(sp, answer)
     # weights and method specified
     sp = nx.shortest_path(nx.path_graph(3), target=1, weight='weight',
                           method='dijkstra')
     assert_equal(sp, answer)
     sp = nx.shortest_path(nx.path_graph(3), target=1, weight='weight',
                           method='bellman-ford')
     assert_equal(sp, answer)