DiGraph
=======

>>> from networkx import *
>>> from networkx.isomorph import graph_could_be_isomorphic
>>> is_isomorphic=graph_could_be_isomorphic


Unit tests for DiGraph Class in base.py
---------------------------------------


In addition to the usual suspects (P1, P2, P3, K1, K2, null, etc.)
we use: P1di, P2di, etc. where Xdi=to_directed(X)
 
     G -- named "test"
       -- grown and deleted, with nodes A,B,C,...
 
     H -- copy of G with extra int nodes from P3 and K3
 

>>> 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)
>>> K5=cnlti(complete_graph(5),first_label=1)




Some small digraphs

>>> nulldi=null.to_directed()
>>> P1di=P1.to_directed()
>>> P3di=P3.to_directed()
>>> P10di=P10.to_directed()
>>> K1di=K1.to_directed()
>>> K3di=K3.to_directed()
>>> K5di=K5.to_directed()




Name
----

>>> G = DiGraph(name="test")
>>> print G    # test of __str__
test
>>> print G.name
test
>>> H= DiGraph()
>>> print H.name
<BLANKLINE>


Nodes
-----

>>> G.add_node('A')
>>> G.has_node('A')
True
>>> 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']
>>> 'A' in G    # test __contains__
True
>>> len(G)      # test __len__
11

>>> G.clear()     # test node portion of 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']

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 directed, so B->A is not an edge
False
>>> 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 directed
True
>>> 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') # should add the node 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')  # directed
False
>>> G.add_edges_from([('D','F'),('B','D')])   # test add_edges_from()
>>> G.has_edge('D','F')
True
>>> G.has_edge('B','D')
True
>>> G.has_edge('D','B')  # directed
False
>>> G.add_edges_from([tuple('IJ'),list('KK'),tuple('JK')])  # after failing silently, should add 3rd edge
>>> G.has_edge(('I','J'))
True
>>> G.has_edge(('K','K'))
False
>>> G.has_edge(('J','K'))
True
>>> G.has_edge(('K','J'))  # directed
False

>>> 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')  # directed
True
>>> 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_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'), ('A', 'C'), ('B', 'C'), ('B', 'D'), ('C', 'D')]

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
Traceback (most recent call last):
...
NetworkXError: nbunch is not a node or a sequence of nodes.

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

nbunch can be an empty list

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

nbunch can be a list

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

nbunch can be a set

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

nbunch can be a graph

>>> G1=Graph()
>>> G1.add_nodes_from('AB')
>>> sorted(G.out_edges(G1)) 
[('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D')]

nbunch can be a dict with nodes as keys

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

nbunch can be a single node

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


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.out_edges_iter(['A','B']))
[('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D')]

nbunch can be a set

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

nbunch can be a graph

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

nbunch can be a dict with nodes as keys

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

nbunch can be a single node

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

nbunch can be nothing (whole graph)

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


Properties
----------

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.in_degree())
[0, 0, 0, 0, 1, 2, 2]
>>> G.in_degree(with_labels=True)
{'A': 0, 'C': 2, 'B': 1, 'D': 2, 'G': 0, 'K': 0, 'J': 0}
>>> sorted(G.out_degree())
[0, 0, 0, 0, 1, 2, 2]
>>> G.out_degree(with_labels=True)
{'A': 2, 'C': 1, 'B': 2, 'D': 0, 'G': 0, 'K': 0, 'J': 0}
>>> sorted(G.degree())
[0, 0, 0, 2, 2, 3, 3]
>>> sorted(list(G.in_degree_iter()))
[0, 0, 0, 0, 1, 2, 2]
>>> dict(G.in_degree_iter(with_labels=True))
{'A': 0, 'C': 2, 'B': 1, 'D': 2, 'G': 0, 'K': 0, 'J': 0}
>>> sorted(list(G.out_degree_iter()))
[0, 0, 0, 0, 1, 2, 2]
>>> dict(G.out_degree_iter(with_labels=True))
{'A': 2, 'C': 1, 'B': 2, 'D': 0, 'G': 0, 'K': 0, 'J': 0}
>>> sorted(list(G.degree_iter()))
[0, 0, 0, 2, 2, 3, 3]

>>> H=DiGraph()
>>> H.add_edges_from([(1,24),(1,2)])
>>> H.in_degree([1,24])
[0, 1]
>>> H.out_degree([1,24])
[2, 0]
>>> H.degree([1,24])
[2, 1]

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

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

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


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

>>> 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'), ('B', 'D')]
>>> sorted(SG.predecessors('B'))
['A']

>>> UG=G.to_undirected()       # to_undirected
>>> UG==G
False
>>> UG.is_directed()
False
>>> G.is_directed()
True
>>> UG.name==G.name
True
>>> UG.adj==G.adj
False
>>> sorted(UG.edges(list('AB')))
[('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D')]
>>> sorted(UG.edges(['A','B']))
[('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D')]
>>> UG.delete_edge('A','B')
>>> UG.has_edge('B','A')
False
>>> UG.has_edge('A','B')
False

  # to_directed
  # to_weightedgraph
  # to_pseudograph


Neighbors, Predecessors and Successors
--------------------------------------

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

>>> sorted(G.successors('A'))
['B', 'C']
>>> sorted(G.out_neighbors('A'))
['B', 'C']
>>> sorted(G.successors_iter('A'))
['B', 'C']
>>> sorted(G.predecessors('C'))
['A', 'B']
>>> sorted(G.in_neighbors('C'))
['A', 'B']
>>> sorted(G.predecessors_iter('C'))
['A', 'B']

>>> sorted(G.successors('G'))   # no edges
[]
>>> sorted(G.predecessors('G'))  
[]
>>> sorted(G.predecessors('A'))     # some edges but wrong direction
[]
>>> sorted(G.successors('D'))  
[]
>>> sorted(G.successors_iter('G'))   # no edges
[]
>>> sorted(G.predecessors_iter('G'))  
[]
>>> sorted(G.predecessors_iter('A'))     # some edges but wrong direction
[]
>>> sorted(G.successors_iter('D'))  
[]
>>> sorted(G.neighbors('j'))  
Traceback (most recent call last):
...
NetworkXError: node j not in graph
>>> sorted(G.predecessors('j'))  
Traceback (most recent call last):
...
NetworkXError: node j not in graph
>>> sorted(G.successors('j'))  
Traceback (most recent call last):
...
NetworkXError: node j not in graph
>>> sorted(G.neighbors_iter('j'))  
Traceback (most recent call last):
...
NetworkXError: node j not in graph
>>> sorted(G.predecessors_iter('j'))  
Traceback (most recent call last):
...
NetworkXError: node j not in graph
>>> sorted(G.successors_iter('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'), ('A', 'C'), ('B', 'C'), ('B', 'D'), ('C', 'D')]
>>> sorted(edges_iter(G))
[('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'), ('C', 'D')]
>>> 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]
>>> is_directed(G)
True


Iterators
---------

>>> sorted(G.nodes_iter())
['A', 'B', 'C', 'D', 'G', 'J', 'K']
>>> sorted(G.edges_iter())
[('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'), ('C', 'D')]
>>> 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

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

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

>>> E5=empty_graph(5)
>>> E10=empty_graph(10)
>>> H=E10.subgraph([])
>>> is_isomorphic(H,nullgraph)
True

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

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

Subgraph of a complete graph is a complete graph

>>> K1=complete_graph(1)
>>> K3=complete_graph(3)
>>> K5=complete_graph(5)
>>> H=K5.subgraph([1,2,3])
>>> is_isomorphic(H,K3)
True

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

>>> H=K5.subgraph(1)
>>> is_isomorphic(H,K1)
True
>>> J5=K5.copy()
>>> H=J5.subgraph(1,inplace=True)
>>> is_isomorphic(H,K1)
True
>>> is_isomorphic(J5,K1)
True

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

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

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

>>> H=K5.subgraph(iter(K3))
>>> is_isomorphic(H,K3)
True
>>> J5=K5.copy()
>>> H=J5.subgraph(iter(K3),inplace=True)
>>> is_isomorphic(H,K3)
True
>>> is_isomorphic(J5,K3)
True

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

>>> H=K5.subgraph(K3)
>>> is_isomorphic(H,K3)
True
>>> J5=K5.copy()
>>> H=J5.subgraph(K3,inplace=True)
>>> is_isomorphic(H,K3)
True
>>> is_isomorphic(J5,K3)
True

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

>>> H=K5.subgraph([9])
>>> is_isomorphic(H,null_graph())
True

Test reverse

>>> G=complete_graph(10)
>>> H=G.to_directed()
>>> HR=H.reverse()
>>> is_isomorphic(H,HR)
True
>>> sorted(H.edges())==sorted(HR.edges())
True

>>> H=DiGraph()
>>> foo=[H.add_edge(u,u+1) for u in range(0,5)]
>>> HR=H.reverse()
>>> [HR.has_edge(u+1,u) for u in range(0,5)]
[True, True, True, True, True]

>>> H=DiGraph()
>>> H.add_nodes_from([1,2,3,4])
>>> HR=H.reverse()
>>> sorted(HR.nodes())
[1, 2, 3, 4]