| #!/usr/bin/env python |
| """Original NetworkX graph tests""" |
| from nose.tools import * |
| import networkx |
| import networkx as nx |
| from networkx import convert_node_labels_to_integers as cnlti |
| from networkx.testing import * |
| |
| class HistoricalTests(object): |
| |
| 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_name(self): |
| G=self.G(name="test") |
| assert_equal(str(G),'test') |
| assert_equal(G.name,'test') |
| H=self.G() |
| assert_equal(H.name,'') |
| |
| # Nodes |
| |
| def test_add_remove_node(self): |
| G=self.G() |
| G.add_node('A') |
| assert_true(G.has_node('A')) |
| G.remove_node('A') |
| assert_false(G.has_node('A')) |
| |
| def test_nonhashable_node(self): |
| # Test if a non-hashable object is in the Graph. A python dict will |
| # raise a TypeError, but for a Graph class a simple False should be |
| # returned (see Graph __contains__). If it cannot be a node then it is |
| # not a node. |
| G=self.G() |
| assert_false(G.has_node(['A'])) |
| assert_false(G.has_node({'A':1})) |
| |
| def test_add_nodes_from(self): |
| G=self.G() |
| G.add_nodes_from(list("ABCDEFGHIJKL")) |
| assert_true(G.has_node("L")) |
| G.remove_nodes_from(['H','I','J','K','L']) |
| G.add_nodes_from([1,2,3,4]) |
| assert_equal(sorted(G.nodes(),key=str), |
| [1, 2, 3, 4, 'A', 'B', 'C', 'D', 'E', 'F', 'G']) |
| # test __iter__ |
| assert_equal(sorted(G,key=str), |
| [1, 2, 3, 4, 'A', 'B', 'C', 'D', 'E', 'F', 'G']) |
| |
| |
| def test_contains(self): |
| G=self.G() |
| G.add_node('A') |
| assert_true('A' in G) |
| assert_false([] in G) # never raise a Key or TypeError in this test |
| assert_false({1:1} in G) |
| |
| def test_add_remove(self): |
| # Test add_node and remove_node acting for various nbunch |
| G=self.G() |
| G.add_node('m') |
| assert_true(G.has_node('m')) |
| G.add_node('m') # no complaints |
| assert_raises(nx.NetworkXError,G.remove_node,'j') |
| G.remove_node('m') |
| assert_equal(G.nodes(),[]) |
| |
| def test_nbunch_is_list(self): |
| G=self.G() |
| G.add_nodes_from(list("ABCD")) |
| G.add_nodes_from(self.P3) # add nbunch of nodes (nbunch=Graph) |
| assert_equal(sorted(G.nodes(),key=str), |
| [1, 2, 3, 'A', 'B', 'C', 'D']) |
| G.remove_nodes_from(self.P3) # remove nbunch of nodes (nbunch=Graph) |
| assert_equal(sorted(G.nodes(),key=str), |
| ['A', 'B', 'C', 'D']) |
| |
| def test_nbunch_is_set(self): |
| G=self.G() |
| nbunch=set("ABCDEFGHIJKL") |
| G.add_nodes_from(nbunch) |
| assert_true(G.has_node("L")) |
| |
| def test_nbunch_dict(self): |
| # nbunch is a dict with nodes as keys |
| G=self.G() |
| nbunch=set("ABCDEFGHIJKL") |
| G.add_nodes_from(nbunch) |
| nbunch={'I':"foo",'J':2,'K':True,'L':"spam"} |
| G.remove_nodes_from(nbunch) |
| assert_true(sorted(G.nodes(),key=str), |
| ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) |
| |
| def test_nbunch_iterator(self): |
| G=self.G() |
| G.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) |
| n_iter=self.P3.nodes_iter() |
| G.add_nodes_from(n_iter) |
| assert_equal(sorted(G.nodes(),key=str), |
| [1, 2, 3, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) |
| n_iter=self.P3.nodes_iter() # rebuild same iterator |
| G.remove_nodes_from(n_iter) # remove nbunch of nodes (nbunch=iterator) |
| assert_equal(sorted(G.nodes(),key=str), |
| ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) |
| |
| def test_nbunch_graph(self): |
| G=self.G() |
| G.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) |
| nbunch=self.K3 |
| G.add_nodes_from(nbunch) |
| assert_true(sorted(G.nodes(),key=str), |
| [1, 2, 3, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) |
| |
| |
| |
| # Edges |
| |
| def test_add_edge(self): |
| G=self.G() |
| assert_raises(TypeError,G.add_edge,'A') |
| |
| G.add_edge('A','B') # testing add_edge() |
| G.add_edge('A','B') # should fail silently |
| assert_true(G.has_edge('A','B')) |
| assert_false(G.has_edge('A','C')) |
| assert_true(G.has_edge( *('A','B') )) |
| if G.is_directed(): |
| assert_false(G.has_edge('B','A')) |
| else: |
| # G is undirected, so B->A is an edge |
| assert_true(G.has_edge('B','A')) |
| |
| |
| G.add_edge('A','C') # test directedness |
| G.add_edge('C','A') |
| G.remove_edge('C','A') |
| if G.is_directed(): |
| assert_true(G.has_edge('A','C')) |
| else: |
| assert_false(G.has_edge('A','C')) |
| assert_false(G.has_edge('C','A')) |
| |
| |
| def test_self_loop(self): |
| G=self.G() |
| G.add_edge('A','A') # test self loops |
| assert_true(G.has_edge('A','A')) |
| G.remove_edge('A','A') |
| G.add_edge('X','X') |
| assert_true(G.has_node('X')) |
| G.remove_node('X') |
| G.add_edge('A','Z') # should add the node silently |
| assert_true(G.has_node('Z')) |
| |
| def test_add_edges_from(self): |
| G=self.G() |
| G.add_edges_from([('B','C')]) # test add_edges_from() |
| assert_true(G.has_edge('B','C')) |
| if G.is_directed(): |
| assert_false(G.has_edge('C','B')) |
| else: |
| assert_true(G.has_edge('C','B')) # undirected |
| |
| G.add_edges_from([('D','F'),('B','D')]) |
| assert_true(G.has_edge('D','F')) |
| assert_true(G.has_edge('B','D')) |
| |
| if G.is_directed(): |
| assert_false(G.has_edge('D','B')) |
| else: |
| assert_true(G.has_edge('D','B')) # undirected |
| |
| def test_add_edges_from2(self): |
| G=self.G() |
| # after failing silently, should add 2nd edge |
| G.add_edges_from([tuple('IJ'),list('KK'),tuple('JK')]) |
| assert_true(G.has_edge(*('I','J'))) |
| assert_true(G.has_edge(*('K','K'))) |
| assert_true(G.has_edge(*('J','K'))) |
| if G.is_directed(): |
| assert_false(G.has_edge(*('K','J'))) |
| else: |
| assert_true(G.has_edge(*('K','J'))) |
| |
| def test_add_edges_from3(self): |
| G=self.G() |
| G.add_edges_from(zip(list('ACD'),list('CDE'))) |
| assert_true(G.has_edge('D','E')) |
| assert_false(G.has_edge('E','C')) |
| |
| def test_remove_edge(self): |
| G=self.G() |
| G.add_nodes_from([1, 2, 3, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) |
| |
| G.add_edges_from(zip(list('MNOP'),list('NOPM'))) |
| assert_true(G.has_edge('O','P')) |
| assert_true( G.has_edge('P','M')) |
| G.remove_node('P') # tests remove_node()'s handling of edges. |
| assert_false(G.has_edge('P','M')) |
| assert_raises(TypeError,G.remove_edge,'M') |
| |
| G.add_edge('N','M') |
| assert_true(G.has_edge('M','N')) |
| G.remove_edge('M','N') |
| assert_false(G.has_edge('M','N')) |
| |
| # self loop fails silently |
| G.remove_edges_from([list('HI'),list('DF'), |
| tuple('KK'),tuple('JK')]) |
| assert_false(G.has_edge('H','I')) |
| assert_false(G.has_edge('J','K')) |
| G.remove_edges_from([list('IJ'),list('KK'),list('JK')]) |
| assert_false(G.has_edge('I','J')) |
| G.remove_nodes_from(set('ZEFHIMNO')) |
| G.add_edge('J','K') |
| |
| |
| def test_edges_nbunch(self): |
| # Test G.edges(nbunch) with various forms of nbunch |
| G=self.G() |
| G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), |
| ('C', 'B'), ('C', 'D')]) |
| # node not in nbunch should be quietly ignored |
| assert_raises(nx.NetworkXError,G.edges,6) |
| assert_equals(G.edges('Z'),[]) # iterable non-node |
| # nbunch can be an empty list |
| assert_equals(G.edges([]),[]) |
| if G.is_directed(): |
| elist=[('A', 'B'), ('A', 'C'), ('B', 'D')] |
| else: |
| elist=[('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D')] |
| # nbunch can be a list |
| assert_edges_equal(G.edges(['A','B']),elist) |
| # nbunch can be a set |
| assert_edges_equal(G.edges(set(['A','B'])),elist) |
| # nbunch can be a graph |
| G1=self.G() |
| G1.add_nodes_from('AB') |
| assert_edges_equal(G.edges(G1),elist) |
| # nbunch can be a dict with nodes as keys |
| ndict={'A': "thing1", 'B': "thing2"} |
| assert_edges_equal(G.edges(ndict),elist) |
| # nbunch can be a single node |
| assert_edges_equal(G.edges('A'), [('A', 'B'), ('A', 'C')]) |
| |
| assert_edges_equal(G.nodes_iter(), ['A', 'B', 'C', 'D']) |
| |
| def test_edges_iter_nbunch(self): |
| G=self.G() |
| G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), |
| ('C', 'B'), ('C', 'D')]) |
| # Test G.edges_iter(nbunch) with various forms of nbunch |
| # node not in nbunch should be quietly ignored |
| assert_equals(list(G.edges_iter('Z')),[]) |
| # nbunch can be an empty list |
| assert_equals(sorted(G.edges_iter([])),[]) |
| if G.is_directed(): |
| elist=[('A', 'B'), ('A', 'C'), ('B', 'D')] |
| else: |
| elist=[('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D')] |
| # nbunch can be a list |
| assert_edges_equal(G.edges_iter(['A','B']),elist) |
| # nbunch can be a set |
| assert_edges_equal(G.edges_iter(set(['A','B'])),elist) |
| # nbunch can be a graph |
| G1=self.G() |
| G1.add_nodes_from(['A','B']) |
| assert_edges_equal(G.edges_iter(G1),elist) |
| # nbunch can be a dict with nodes as keys |
| ndict={'A': "thing1", 'B': "thing2"} |
| assert_edges_equal(G.edges_iter(ndict),elist) |
| # nbunch can be a single node |
| assert_edges_equal(G.edges_iter('A'), [('A', 'B'), ('A', 'C')]) |
| |
| # nbunch can be nothing (whole graph) |
| assert_edges_equal(G.edges_iter(), [('A', 'B'), ('A', 'C'), ('B', 'D'), |
| ('C', 'B'), ('C', 'D')]) |
| |
| |
| def test_degree(self): |
| G=self.G() |
| G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), |
| ('C', 'B'), ('C', 'D')]) |
| assert_equal(G.degree('A'),2) |
| |
| # degree of single node in iterable container must return dict |
| assert_equal(list(G.degree(['A']).values()),[2]) |
| assert_equal(G.degree(['A']),{'A': 2}) |
| assert_equal(sorted(G.degree(['A','B']).values()),[2, 3]) |
| assert_equal(G.degree(['A','B']),{'A': 2, 'B': 3}) |
| assert_equal(sorted(G.degree().values()),[2, 2, 3, 3]) |
| assert_equal(sorted([v for k,v in G.degree_iter()]), |
| [2, 2, 3, 3]) |
| |
| def test_degree2(self): |
| H=self.G() |
| H.add_edges_from([(1,24),(1,2)]) |
| assert_equal(sorted(H.degree([1,24]).values()),[1, 2]) |
| |
| def test_degree_graph(self): |
| P3=nx.path_graph(3) |
| P5=nx.path_graph(5) |
| # silently ignore nodes not in P3 |
| assert_equal(P3.degree(['A','B']),{}) |
| # nbunch can be a graph |
| assert_equal(sorted(P5.degree(P3).values()),[1, 2, 2]) |
| # nbunch can be a graph thats way to big |
| assert_equal(sorted(P3.degree(P5).values()),[1, 1, 2]) |
| assert_equal(P5.degree([]),{}) |
| assert_equal(list(P5.degree_iter([])),[]) |
| assert_equal(dict(P5.degree_iter([])),{}) |
| |
| def test_null(self): |
| null=nx.null_graph() |
| assert_equal(null.degree(),{}) |
| assert_equal(list(null.degree_iter()),[]) |
| assert_equal(dict(null.degree_iter()),{}) |
| |
| def test_order_size(self): |
| G=self.G() |
| G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), |
| ('C', 'B'), ('C', 'D')]) |
| assert_equal(G.order(),4) |
| assert_equal(G.size(),5) |
| assert_equal(G.number_of_edges(),5) |
| assert_equal(G.number_of_edges('A','B'),1) |
| assert_equal(G.number_of_edges('A','D'),0) |
| |
| def test_copy(self): |
| G=self.G() |
| H=G.copy() # copy |
| assert_equal(H.adj,G.adj) |
| assert_equal(H.name,G.name) |
| assert_not_equal(H,G) |
| |
| def test_subgraph(self): |
| G=self.G() |
| G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), |
| ('C', 'B'), ('C', 'D')]) |
| SG=G.subgraph(['A','B','D']) |
| assert_nodes_equal(SG.nodes(),['A', 'B', 'D']) |
| assert_edges_equal(SG.edges(),[('A', 'B'), ('B', 'D')]) |
| |
| def test_to_directed(self): |
| G=self.G() |
| if not G.is_directed(): |
| G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), |
| ('C', 'B'), ('C', 'D')]) |
| |
| DG=G.to_directed() |
| assert_not_equal(DG,G) # directed copy or copy |
| |
| assert_true(DG.is_directed()) |
| assert_equal(DG.name,G.name) |
| assert_equal(DG.adj,G.adj) |
| assert_equal(sorted(DG.out_edges(list('AB'))), |
| [('A', 'B'), ('A', 'C'), ('B', 'A'), |
| ('B', 'C'), ('B', 'D')]) |
| DG.remove_edge('A','B') |
| assert_true(DG.has_edge('B','A')) # this removes B-A but not A-B |
| assert_false(DG.has_edge('A','B')) |
| |
| def test_to_undirected(self): |
| G=self.G() |
| if G.is_directed(): |
| G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), |
| ('C', 'B'), ('C', 'D')]) |
| UG=G.to_undirected() # to_undirected |
| assert_not_equal(UG,G) |
| assert_false(UG.is_directed()) |
| assert_true(G.is_directed()) |
| assert_equal(UG.name,G.name) |
| assert_not_equal(UG.adj,G.adj) |
| assert_equal(sorted(UG.edges(list('AB'))), |
| [('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D')]) |
| assert_equal(sorted(UG.edges(['A','B'])), |
| [('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D')]) |
| UG.remove_edge('A','B') |
| assert_false(UG.has_edge('B','A')) |
| assert_false( UG.has_edge('A','B')) |
| |
| |
| |
| def test_neighbors(self): |
| G=self.G() |
| G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), |
| ('C', 'B'), ('C', 'D')]) |
| G.add_nodes_from('GJK') |
| assert_equal(sorted(G['A']),['B', 'C']) |
| assert_equal(sorted(G.neighbors('A')),['B', 'C']) |
| assert_equal(sorted(G.neighbors_iter('A')),['B', 'C']) |
| assert_equal(sorted(G.neighbors('G')),[]) |
| assert_raises(nx.NetworkXError,G.neighbors,'j') |
| |
| def test_iterators(self): |
| G=self.G() |
| G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), |
| ('C', 'B'), ('C', 'D')]) |
| G.add_nodes_from('GJK') |
| assert_equal(sorted(G.nodes_iter()), |
| ['A', 'B', 'C', 'D', 'G', 'J', 'K']) |
| assert_edges_equal(G.edges_iter(), |
| [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'B'), ('C', 'D')]) |
| |
| assert_equal(sorted([v for k,v in G.degree_iter()]), |
| [0, 0, 0, 2, 2, 3, 3]) |
| assert_equal(sorted(G.degree_iter(),key=str), |
| [('A', 2), ('B', 3), ('C', 3), ('D', 2), |
| ('G', 0), ('J', 0), ('K', 0)]) |
| assert_equal(sorted(G.neighbors_iter('A')),['B', 'C']) |
| assert_raises(nx.NetworkXError,G.neighbors_iter,'X') |
| G.clear() |
| assert_equal(nx.number_of_nodes(G),0) |
| assert_equal(nx.number_of_edges(G),0) |
| |
| |
| def test_null_subgraph(self): |
| # Subgraph of a null graph is a null graph |
| nullgraph=nx.null_graph() |
| G=nx.null_graph() |
| H=G.subgraph([]) |
| assert_true(nx.is_isomorphic(H,nullgraph)) |
| |
| 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_complete_subgraph(self): |
| # Subgraph of a complete graph is a complete graph |
| K1=nx.complete_graph(1) |
| K3=nx.complete_graph(3) |
| K5=nx.complete_graph(5) |
| H=K5.subgraph([1,2,3]) |
| assert_true(nx.is_isomorphic(H,K3)) |
| |
| def test_subgraph_nbunch(self): |
| nullgraph=nx.null_graph() |
| K1=nx.complete_graph(1) |
| K3=nx.complete_graph(3) |
| K5=nx.complete_graph(5) |
| # Test G.subgraph(nbunch), where nbunch is a single node |
| H=K5.subgraph(1) |
| assert_true(nx.is_isomorphic(H,K1)) |
| # Test G.subgraph(nbunch), where nbunch is a set |
| H=K5.subgraph(set([1])) |
| assert_true(nx.is_isomorphic(H,K1)) |
| # Test G.subgraph(nbunch), where nbunch is an iterator |
| H=K5.subgraph(iter(K3)) |
| assert_true(nx.is_isomorphic(H,K3)) |
| # Test G.subgraph(nbunch), where nbunch is another graph |
| H=K5.subgraph(K3) |
| assert_true(nx.is_isomorphic(H,K3)) |
| H=K5.subgraph([9]) |
| assert_true(nx.is_isomorphic(H,nullgraph)) |
| |
| def test_node_tuple_error(self): |
| H=self.G() |
| # Test error handling of tuple as a node |
| assert_raises(nx.NetworkXError,H.remove_node,(1,2)) |
| H.remove_nodes_from([(1,2)]) # no error |
| assert_raises(nx.NetworkXError,H.neighbors,(1,2)) |
