XGraph
======

Unit tests for XGraph Class in xbase.py
---------------------------------------

>>> from networkx import *
>>> from networkx.isomorph import graph_could_be_isomorphic
>>> is_isomorphic=graph_could_be_isomorphic
>>> from networkx.operators import convert_node_labels_to_integers as cnlti

Some small graphs
-----------------

>>> null=null_graph()
>>> P1=cnlti(path_graph(1),first_label=1)
>>> P3=cnlti(path_graph(3),first_label=1)
>>> P10=cnlti(path_graph(10),first_label=1)
>>> K1=cnlti(complete_graph(1),first_label=1)
>>> K3=cnlti(complete_graph(3),first_label=1)
>>> K4=cnlti(complete_graph(4),first_label=1)
>>> K5=cnlti(complete_graph(5),first_label=1)
>>> K10=cnlti(complete_graph(10),first_label=1)

Same small graphs but as XGraphs
--------------------------------

>>> nullX=XGraph()
>>> P1X=XGraph()
>>> P1X.add_nodes_from(P1)
>>> P1X.add_edges_from(P1.edges())
>>> P3X=XGraph()
>>> P3X.add_edges_from(P3.edges())
>>> P10X=XGraph()
>>> P10X.add_edges_from(P10.edges())
>>> K1X=XGraph()
>>> K1X.add_nodes_from(K1)
>>> K1X.add_edges_from(K1.edges())
>>> K3X=XGraph()
>>> K3X.add_edges_from(K3.edges())
>>> K4X=XGraph()
>>> K4X.add_edges_from(K4.edges())
>>> K5X=XGraph()
>>> K5X.add_edges_from(K5.edges())

Name
----

>>> G = XGraph(name="test")
>>> print G    # test of __str__
test
>>> print G.name
test

>>> H=XGraph()
>>> print H.name
<BLANKLINE>

>>> G2=XGraph(data={1:[2],2:[1]}, name="test")
>>> print G2.edges()
[(1, 2, None)]
>>> print G2.name
test

Nodes
-----

>>> G.add_node('A')
>>> G.has_node('A')
True


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.has_node(['A'])
False
>>> G.has_node({'A':1})
False

>>> G.delete_node('A')
>>> G.has_node('A')
False
>>> G.add_nodes_from(list("ABCDEFGHIJKL"))
>>> G.has_node("L")
True
>>> G.delete_nodes_from(['H','I','J','K','L'])
>>> G.add_nodes_from([1,2,3,4])
>>> sorted(G.nodes())
[1, 2, 3, 4, 'A', 'B', 'C', 'D', 'E', 'F', 'G']
>>> sorted(G)   # test __iter__
[1, 2, 3, 4, 'A', 'B', 'C', 'D', 'E', 'F', 'G']



test __contains__

>>> 'A' in G   
True
>>> [] in G  # never raise a Key or TypeError in this test
False
>>> {1:1} in G
False

test __len__

>>> len(G) 
11

test node portion of clear()

>>> G.clear()    
>>> G.nodes()
[]


Test add_node and delete_node acting for various nbunch

>>> G.add_node('m')
>>> G.has_node('m')
True
>>> G.add_node('m')   # no complaints
>>> G.delete_node('j') # NetworkXError
Traceback (most recent call last):
...
NetworkXError: node j not in graph
>>> G.delete_node('m')
>>> G.nodes()
[]

nbunch is a list.

>>> G.add_nodes_from(list("ABCD")) 
>>> G.add_nodes_from(P3) # add nbunch of nodes (nbunch=Graph)
>>> sorted(G.nodes())
[1, 2, 3, 'A', 'B', 'C', 'D']
>>> G.delete_nodes_from(P3) # delete nbunch of nodes (nbunch=Graph)
>>> sorted(G.nodes())
['A', 'B', 'C', 'D']

nbunch is a set

>>> nbunch=set("ABCDEFGHIJKL")
>>> G.add_nodes_from(nbunch)
>>> G.has_node("L")
True

nbunch is a dict with nodes as keys

>>> nbunch={'I':"foo",'J':2,'K':True,'L':"spam"}
>>> G.delete_nodes_from(nbunch)
>>> sorted(G.nodes())
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']

nbunch is an iterator

>>> n_iter=P3.nodes_iter()
>>> G.add_nodes_from(n_iter)
>>> sorted(G.nodes())
[1, 2, 3, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
>>> n_iter=P3.nodes_iter() # rebuild same iterator
>>> G.delete_nodes_from(n_iter) # delete nbunch of nodes (nbunch=iterator)
>>> sorted(G.nodes())
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']

nbunch is a graph

>>> nbunch=K3
>>> G.add_nodes_from(nbunch)
>>> sorted(G.nodes())
[1, 2, 3, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']

nbunch is an XGraph

>>> nbunch=K3X
>>> G.add_nodes_from(nbunch)
>>> sorted(G.nodes())
[1, 2, 3, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']



Edges
-----

>>> G.add_edge('A')
Traceback (most recent call last):
...
ValueError: need more than 1 value to unpack

>>> G.add_edge('A','B')     # testing add_edge()
>>> G.add_edge('A','B') # should fail silently
>>> G.has_edge('A','B')     # testing has_edge()
True
>>> G.has_edge('A','C')
False
>>> G.has_edge( ('A','B') )
True
>>> G.has_edge('B','A') # G is undirected, so B->A is an edge
True
>>> G.has_neighbor('A','C')  # same as has_edge
False
>>> G.has_neighbor('A','B')  
True

>>> G.add_edge('A','C')  # test directedness
>>> G.add_edge('C','A')
>>> G.delete_edge('C','A')
>>> G.has_edge('A','C') # G is undirected
False
>>> G.has_edge('C','A') 
False

>>> G.add_edge('A','A') # test self loops
>>> G.has_edge('A','A')
False

>>> G.add_edge('X','X')
>>> G.has_node('X')  # added node but not self loop
True
>>> G.delete_node('X')


>>> G.add_edge('A','Z') # test that missing node 'Z' is added silently
>>> G.has_node('Z')
True

>>> G.add_edges_from([('B','C')])   # test add_edges_from()
>>> G.has_edge('B','C')
True
>>> G.has_edge('C','B')  # undirected
True
>>> G.add_edges_from([('D','F'),('B','D')])
>>> G.has_edge('D','F')
True
>>> G.has_edge('B','D')
True
>>> G.has_edge('D','B')  # undirected
True
>>> G.add_edges_from([tuple('IJ'),list('KK'),tuple('JK')])  # after failing silently, should add 2nd edge
>>> G.has_edge(('I','J'))
True
>>> G.has_edge(('K','K'))
False
>>> G.has_edge(('J','K'))
True
>>> G.has_edge(('K','J'))  # undirected
True

>>> G.add_path(list('ACDE'))      # test add_path() and add_cycle()
>>> G.has_edge('D','E')
True
>>> G.has_edge('E','C')
False
>>> G.add_cycle(list('MNOP'))
>>> G.has_edge('O','P')
True
>>> G.has_edge('P','M')
True
>>> G.delete_node('P')    # tests delete_node()'s handling of edges.
>>> G.has_edge('P','M')
False


>>> G.delete_edge('M')       # test delete_edge()
Traceback (most recent call last):
...
ValueError: need more than 1 value to unpack

>>> G.add_edge('N','M')  
>>> G.has_edge('M','N')
True
>>> G.delete_edge('M','N')
>>> G.has_edge('M','N')
False
>>> G.has_edge('N','M')  # undirected
False
>>> G.delete_edges_from([list('HI'),list('DF'),tuple('KK'),tuple('JK')]) # self loop fails silently
>>> G.has_edge('H','I')
False
>>> G.has_edge('J','K')
False
>>> G.delete_edges_from([list('IJ'),list('KK'),list('JK')])
>>> G.has_edge('I','J')
False
>>> G.delete_nodes_from(set('ZEFHIMNO'))
>>> sorted(G.nodes())
[1, 2, 3, 'A', 'B', 'C', 'D', 'G', 'J', 'K']
>>> G.delete_nodes_from([1,2,3])
>>> sorted(G.nodes())
['A', 'B', 'C', 'D', 'G', 'J', 'K']
>>> sorted(G.edges())
[('A', 'B', None), ('A', 'C', None), ('B', 'D', None), ('C', 'B', None), ('C', 'D', None)]

Test G.edges(nbunch) with various forms of nbunch

node not in nbunch should be quietly ignored

>>> sorted(G.edges(6))    # non-iterable non-node
[]

>>> sorted(G.edges('Z'))  # iterable non-node
[]

nbunch can be an empty list

>>> sorted(G.edges([])) 
[]

nbunch can be a list

>>> sorted(G.edges(['A','B']))
[('A', 'B', None), ('A', 'C', None), ('B', 'C', None), ('B', 'D', None)]

nbunch can be a set

>>> sorted(G.edges(set(['A','B'])))
[('A', 'B', None), ('A', 'C', None), ('B', 'C', None), ('B', 'D', None)]

nbunch can be a graph

>>> G1=Graph()
>>> G1.add_nodes_from('AB')
>>> sorted(G.edges(G1)) # nbunch is a graph
[('A', 'B', None), ('A', 'C', None), ('B', 'C', None), ('B', 'D', None)]

nbunch can be an XGraph

>>> G1=XGraph()
>>> G1.add_nodes_from('AB')
>>> sorted(G.edges(G1)) # nbunch is an XGraph
[('A', 'B', None), ('A', 'C', None), ('B', 'C', None), ('B', 'D', None)]


nbunch can be a dict with nodes as keys

>>> ndict={'A': "thing1", 'B': "thing2"}
>>> sorted(G.edges(ndict))
[('A', 'B', None), ('A', 'C', None), ('B', 'C', None), ('B', 'D', None)]

nbunch can be a single node

>>> sorted(G.edges('A'))
[('A', 'B', None), ('A', 'C', None)]


Test G.edges_iter(nbunch) with various forms of nbunch

node not in nbunch should be quietly ignored

>>> sorted(G.edges_iter('Z'))
[]

nbunch can be an empty list

>>> sorted(G.edges_iter([])) 
[]

nbunch can be a list

>>> sorted(G.edges_iter(['A','B']))
[('A', 'B', None), ('A', 'C', None), ('B', 'C', None), ('B', 'D', None)]

nbunch can be a set

>>> sorted(G.edges_iter(set(['A','B'])))
[('A', 'B', None), ('A', 'C', None), ('B', 'C', None), ('B', 'D', None)]

nbunch can be a graph

>>> G1=Graph()
>>> G1.add_nodes_from(['A','B'])
>>> sorted(G.edges_iter(G1)) # nbunch is a graph
[('A', 'B', None), ('A', 'C', None), ('B', 'C', None), ('B', 'D', None)]

nbunch can be an XGraph

>>> G1=XGraph()
>>> G1.add_nodes_from(['A','B'])
>>> sorted(G.edges_iter(G1)) # nbunch is a graph
[('A', 'B', None), ('A', 'C', None), ('B', 'C', None), ('B', 'D', None)]


nbunch can be a dict with nodes as keys

>>> ndict={'A': "thing1", 'B': "thing2"}
>>> sorted(G.edges_iter(ndict))
[('A', 'B', None), ('A', 'C', None), ('B', 'C', None), ('B', 'D', None)]

nbunch can be a single node

>>> sorted(G.edges_iter('A'))
[('A', 'B', None), ('A', 'C', None)]

nbunch can be nothing (whole graph)

>>> sorted(G.edges_iter())
[('A', 'B', None), ('A', 'C', None), ('B', 'D', None), ('C', 'B', None), ('C', 'D', None)]
>>> sorted(G.nodes_iter())
['A', 'B', 'C', 'D', 'G', 'J', 'K']


Properties
----------
degree() of an empty graph must return []

>>> nullX.degree()
[]
>>> nullX.degree(with_labels=True)
{}
>>> list(nullX.degree_iter())
[]
>>> dict(nullX.degree_iter(with_labels=True))
{}


degree of single node must return single int

>>> G.degree('A')
2

degree of single node in iterable container must return list

>>> G.degree(['A'])
[2]

with_labels=True always return a dict

>>> G.degree('A',with_labels=True)
{'A': 2}

>>> G.degree(['A','B'])
[2, 3]
>>> G.degree(['A','B'],with_labels=True)
{'A': 2, 'B': 3}

>>> sorted(G.degree())
[0, 0, 0, 2, 2, 3, 3]
>>> sorted(list(G.degree_iter()))
[0, 0, 0, 2, 2, 3, 3]

>>> H=XGraph()
>>> H.add_edges_from([(1,24),(1,2)])
>>> H.degree([1,24])
[2, 1]

>>> P3X.degree(['A','B']) # silently ignore nodes not in P3
[]
>>> sorted(P10X.degree(P3X)) # nbunch can be a graph
[1, 2, 2]
>>> sorted(P3X.degree(P10X)) # nbunch can be a graph thats way to big
[1, 1, 2]
>>> P10X.degree([])
[]
>>> list(P10X.degree_iter([]))
[]
>>> dict( P10X.degree_iter([],with_labels=True) )
{}
>>> dict(P10X.degree_iter([],with_labels=True))
{}

>>> nullX.degree(with_labels=True)
{}
>>> list(nullX.degree_iter())
[]
>>> dict(nullX.degree_iter(with_labels=True))
{}

>>> G.order()
7
>>> G.size()
5


Operations
-----------

copy
~~~~

>>> H=G.copy()      # copy
>>> H.adj==G.adj
True
>>> H.name==G.name
True
>>> H==G
False

>>> SG=G.subgraph(['A','B','D'])     # subgraph
>>> sorted(SG.nodes())
['A', 'B', 'D']
>>> sorted(SG.edges())
[('A', 'B', None), ('B', 'D', None)]

>>> DG=G.to_directed()
>>> DG.is_directed()
True
>>> G.is_directed()
False
>>> DG.name==G.name
True
>>> DG.adj==G.adj
True
>>> sorted(DG.out_edges(list('A')))
[('A', 'B', None), ('A', 'C', None)]
>>> sorted(DG.in_edges(list('A')))
[('B', 'A', None), ('C', 'A', None)]
>>> DG.delete_edge('A','B')
>>> DG.has_edge('B','A') # this deletes B-A but not  A-B
True
>>> DG.has_edge('A','B')
False

  # to_undirected


Neighbors
---------

>>> sorted(G['A'])
['B', 'C']
>>> sorted(G.neighbors('A'))
['B', 'C']
>>> sorted(G.neighbors_iter('A'))
['B', 'C']

>>> sorted(G.neighbors('G'))
[]
>>> sorted(G.neighbors('j'))
Traceback (most recent call last):
...
NetworkXError: node j not in graph


Functional interface
--------------------

>>> sorted(nodes(G))
['A', 'B', 'C', 'D', 'G', 'J', 'K']
>>> sorted(nodes_iter(G))
['A', 'B', 'C', 'D', 'G', 'J', 'K']
>>> sorted(edges(G))
[('A', 'B', None), ('A', 'C', None), ('B', 'D', None), ('C', 'B', None), ('C', 'D', None)]
>>> sorted(edges_iter(G))
[('A', 'B', None), ('A', 'C', None), ('B', 'D', None), ('C', 'B', None), ('C', 'D', None)]
>>> sorted(degree(G))
[0, 0, 0, 2, 2, 3, 3]
>>> sorted(neighbors(G,'A'))
['B', 'C']
>>> number_of_nodes(G)
7
>>> number_of_edges(G)
5
>>> density(G)==5/(7*(7-1)*0.5)
True
>>> degree_histogram(G)
[3, 0, 2, 2]

Iterators
---------

>>> sorted(G.nodes_iter())
['A', 'B', 'C', 'D', 'G', 'J', 'K']
>>> sorted(G.edges_iter())
[('A', 'B', None), ('A', 'C', None), ('B', 'D', None), ('C', 'B', None), ('C', 'D', None)]
>>> sorted(G.degree_iter())
[0, 0, 0, 2, 2, 3, 3]
>>> sorted(G.degree_iter(with_labels=True))
[('A', 2), ('B', 3), ('C', 3), ('D', 2), ('G', 0), ('J', 0), ('K', 0)]
>>> sorted(G.neighbors_iter('A'))
['B', 'C']
>>> sorted(G.neighbors_iter('X'))
Traceback (most recent call last):
...
NetworkXError: node X not in graph

>>> G.clear()
>>> number_of_nodes(G)
0
>>> number_of_edges(G)
0


Subgraph
--------

Subgraph of a null graph is a null graph

>>> G=nullX
>>> H=G.subgraph([])
>>> is_isomorphic(H,nullX)
True

Subgraph of an empty graph is an empty graph. test 1 

>>> E5X=empty_graph(5,create_using=XGraph())
>>> E10X=empty_graph(10,create_using=XGraph())
>>> H=E10X.subgraph([])
>>> is_isomorphic(H,nullX)
True

Subgraph of an  empty graph is an empty graph. test 2

>>> H=E10X.subgraph([1,2,3,4,5])
>>> is_isomorphic(H,E5X)
True

Subgraph of a complete graph is a complete graph

>>> H=K5X.subgraph([1,2,3])
>>> is_isomorphic(H,K3X)
True

Test G.subgraph(nbunch), where nbunch is a single node

>>> H=K5X.subgraph(1)
>>> is_isomorphic(H,K1X)
True
>>> J5=K5X.copy()
>>> H=J5.subgraph(1,inplace=True)
>>> is_isomorphic(H,K1X)
True
>>> is_isomorphic(J5,K1X)
True

Test G.subgraph(nbunch), where nbunch is a set

>>> H=K5X.subgraph(set([1]))
>>> is_isomorphic(H,K1X)
True
>>> J5=K5X.copy()
>>> H=J5.subgraph(set([1]),inplace=True)
>>> is_isomorphic(H,K1X)
True
>>> is_isomorphic(J5,K1X)
True

Test G.subgraph(nbunch), where nbunch is an iterator

>>> H=K5X.subgraph(iter(K3X))
>>> is_isomorphic(H,K3X)
True
>>> J5=K5X.copy()
>>> H=J5.subgraph(iter(K3X),inplace=True)
>>> is_isomorphic(H,K3X)
True
>>> is_isomorphic(J5,K3X)
True

Test G.subgraph(nbunch), where nbunch is another graph

>>> H=K5X.subgraph(K3X)
>>> is_isomorphic(H,K3X)
True
>>> J5=K5X.copy()
>>> H=J5.subgraph(K3X,inplace=True)
>>> is_isomorphic(H,K3X)
True
>>> is_isomorphic(J5,K3X)
True


Test for no error when nbunch has node not in G.nodes()

>>> H=K5X.subgraph([9])
>>> is_isomorphic(H,nullX)
True


number_of_edges
---------------

>>> X=XDiGraph()
>>> X.add_edge(1,2,'a')
>>> X.add_edge(1,3,'a')
>>> X.number_of_edges()
2
>>> X.number_of_edges(1,2)
1
>>> X.number_of_edges((1,2))
1
>>> X.number_of_edges(1,2,'a')
1
>>> X.number_of_edges((1,2,'a'))
1
>>> X.number_of_edges(1,2,'b')
0
>>> X.number_of_edges(1,4)
0
