Operators
=========

Unit tests for graph operations in operators.py

>>> from networkx import *
>>> from networkx.isomorph import graph_could_be_isomorphic
>>> is_isomorphic=graph_could_be_isomorphic # fast but weak isomorphism checker


subgraph
--------
subgraph of a null graph is a null graph

>>> null=null_graph()
>>> H=subgraph(null,[])
>>> is_isomorphic(H,null)
True

subgraph of an empty graph is an empty graph 

>>> E3=empty_graph(3)
>>> E5=empty_graph(5)
>>> E10=empty_graph(10)
>>> H=subgraph(E10,[])
>>> is_isomorphic(H,null)
True

subgraph of an  empty graph is an empty graph 

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

subgraph of a complete graph is a complete graph

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

test subgraph(G,nlist), where nlist is another graph

>>> H=subgraph(K5,K3)
>>> is_isomorphic(H,K3)
True

>>> H=subgraph(K5,[9]) # no error when inducing subgraph on nonexisting node
>>> is_isomorphic(H,null)
True


cartesian_product
-----------------

some classic graphs

>>> null=null_graph()
>>> empty1=empty_graph(1)
>>> empty10=empty_graph(10)
>>> K3=complete_graph(3)
>>> K5=complete_graph(5)
>>> K10=complete_graph(10)
>>> P2=path_graph(2)
>>> P3=path_graph(3)
>>> P5=path_graph(5)
>>> P10=path_graph(10)

null_graph X null_graph = null_graph

>>> G=cartesian_product(null,null)
>>> is_isomorphic(G,null)
True

null_graph X anything = null_graph and v.v.

>>> G=cartesian_product(null,empty10)
>>> is_isomorphic(G,null)
True
>>> G=cartesian_product(null,K3)
>>> is_isomorphic(G,null)
True
>>> G=cartesian_product(null,K10)
>>> is_isomorphic(G,null)
True
>>> G=cartesian_product(null,P3)
>>> is_isomorphic(G,null)
True
>>> G=cartesian_product(null,P10)
>>> is_isomorphic(G,null)
True
>>> G=cartesian_product(empty10,null)
>>> is_isomorphic(G,null)
True
>>> G=cartesian_product(K3,null)
>>> is_isomorphic(G,null)
True
>>> G=cartesian_product(K10,null)
>>> is_isomorphic(G,null)
True
>>> G=cartesian_product(P3,null)
>>> is_isomorphic(G,null)
True
>>> G=cartesian_product(P10,null)
>>> is_isomorphic(G,null)
True

order(GXH)=order(G)*order(H)

>>> G=cartesian_product(P5,K3)
>>> number_of_nodes(G)==5*3
True
>>> number_of_edges(G)==number_of_edges(P5)*number_of_nodes(K3)+number_of_edges(K3)*number_of_nodes(P5)
True
>>> G=cartesian_product(K3,K5)
>>> number_of_nodes(G)==3*5
True
>>> number_of_edges(G)==number_of_edges(K5)*number_of_nodes(K3)+number_of_edges(K3)*number_of_nodes(K5)
True

test some classic product graphs
cube = 2-path X 2-path

>>> G=cartesian_product(P2,P2)
>>> G=cartesian_product(P2,G)
>>> is_isomorphic(G,cubical_graph())
True

3x3 grid

>>> G=cartesian_product(P3,P3)
>>> is_isomorphic(G,grid_2d_graph(3,3))
True


complement
----------

complement of the complete graph is empty

>>> G=complement(K3)
>>> is_isomorphic(G,E3)
True
>>> G=complement(K5)
>>> is_isomorphic(G,E5)
True

for any G, G=complement(complement(G))

>>> P3cc=complement(complement(P3))
>>> is_isomorphic(P3,P3cc)
True
>>> nullcc=complement(complement(null))
>>> is_isomorphic(null,nullcc)
True
>>> b=bull_graph()
>>> bcc=complement(complement(b))
>>> is_isomorphic(b,bcc)
True


>>> G1=DiGraph()
>>> G1.add_edge('A','B')
>>> G1.add_edge('A','C')
>>> G1.add_edge('A','D')
>>> G2=DiGraph()
>>> G2.add_edge(1,2)
>>> G2.add_edge(1,3)
>>> G2.add_edge(1,4)
>>> G1C=complement(G1)
>>> sorted(G1C.edges())
[('B', 'A'), ('B', 'C'), ('B', 'D'), ('C', 'A'), ('C', 'B'), ('C', 'D'), ('D', 'A'), ('D', 'B'), ('D', 'C')]

union and compose
-----------------

>>> R=DiGraph()
>>> G=union(G1,G2,result=R)
>>> H=compose(G1,G2)
>>> sorted(G.edges())==sorted(H.edges())
True
>>> G.has_edge('A',1)
False

>>> G=union(K3,P3)
Traceback (most recent call last):
...
NetworkXError: node sets of G and H are not disjoint. Use appropriate rename=('Gprefix','Hprefix')

>>> H1=union(H,G1,rename=('H','G1'))
>>> sorted(H1.nodes())
['G1A', 'G1B', 'G1C', 'G1D', 'H1', 'H2', 'H3', 'H4', 'HA', 'HB', 'HC', 'HD']

>>> H2=union(H,G2,rename=("H",""))
>>> sorted(H2.nodes())
['1', '2', '3', '4', 'H1', 'H2', 'H3', 'H4', 'HA', 'HB', 'HC', 'HD']

>>> H1.has_edge('NB','NA')
False

>>> G=compose(G,G)
>>> sorted(G.edges())==sorted(H.edges())
True

>>> G2=union(G2,G2,rename=('','copy'))
>>> sorted(G2.nodes())
['1', '2', '3', '4', 'copy1', 'copy2', 'copy3', 'copy4']

>>> G2.neighbors('copy4')
[]
>>> sorted(G2.neighbors('copy1'))
['copy2', 'copy3', 'copy4']

>>> len(G)
8
>>> number_of_edges(G)
6
>>> E=disjoint_union(G,G)
>>> len(E)
16
>>> number_of_edges(E)
12
>>> E=disjoint_union(G1,G2)
>>> sorted(E.nodes())
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

convert_data_structure
----------------------

>>> G1.has_edge('B', 'A')
False
>>> UG=convert_to_undirected(G1)
>>> sorted(UG.edges())
[('A', 'B'), ('A', 'C'), ('A', 'D')]
>>> UG.has_edge('B', 'A')
True
>>> DG=convert_to_directed(UG)
>>> DG.adj==UG.adj
True
>>> DG.delete_edge('A','B')
>>> number_of_edges(DG)
5
>>> UG.delete_edge('A','B')
>>> number_of_edges(UG)
2



convert_node_labels_to_integers
-------------------------------

test that empty graph converts fine for all options
 
>>> G=empty_graph()
>>> H=convert_node_labels_to_integers(G,100)
>>> print H.name
(empty_graph(0))_with_int_labels
>>> H.nodes()
[]
>>> H.edges()
[]

>>> G=empty_graph()
>>> H=convert_node_labels_to_integers(G,100,ordering="sorted")
>>> print H.name
(empty_graph(0))_with_int_labels
>>> H.nodes()
[]
>>> H.edges()
[]

>>> G=empty_graph()
>>> H=convert_node_labels_to_integers(G,100,ordering="default")
>>> print H.name
(empty_graph(0))_with_int_labels
>>> H.nodes()
[]
>>> H.edges()
[]

>>> G=empty_graph()
>>> H=convert_node_labels_to_integers(G,100,ordering="increasing degree")
>>> print H.name
(empty_graph(0))_with_int_labels
>>> H.nodes()
[]
>>> H.edges()
[]

>>> G=empty_graph()
>>> H=convert_node_labels_to_integers(G,100,ordering="decreasing degree")
>>> print H.name
(empty_graph(0))_with_int_labels
>>> H.nodes()
[]
>>> H.edges()
[]

>>> G=empty_graph()
>>> G.add_edges_from([('A','B'),('A','C'),('B','C'),('C','D')])
>>> G.name="paw"
>>> H=convert_node_labels_to_integers(G)
>>> degH=H.degree()
>>> degG=G.degree()
>>> print degH.sort()==degG.sort()
True

>>> H=convert_node_labels_to_integers(G,1000)
>>> degH=H.degree()
>>> degG=G.degree()
>>> print degH.sort()==degG.sort()
True
>>> H.nodes()
[1000, 1001, 1002, 1003]

>>> H=convert_node_labels_to_integers(G,ordering="increasing degree")
>>> degH=H.degree()
>>> degG=G.degree()
>>> print degH.sort()==degG.sort()
True
>>> degree(H,0)==1
True
>>> degree(H,1)==2
True
>>> degree(H,2)==2
True
>>> degree(H,3)==3
True

>>> H=convert_node_labels_to_integers(G,ordering="decreasing degree")
>>> degH=H.degree()
>>> degG=G.degree()
>>> print degH.sort()==degG.sort()
True
>>> degree(H,0)==3
True
>>> degree(H,1)==2
True
>>> degree(H,2)==2
True
>>> degree(H,3)==1
True

>>> H=convert_node_labels_to_integers(G,ordering="increasing degree",discard_old_labels=False)
>>> degH=H.degree()
>>> degG=G.degree()
>>> print degH.sort()==degG.sort()
True
>>> degree(H,0)==1
True
>>> degree(H,1)==2
True
>>> degree(H,2)==2
True
>>> degree(H,3)==3
True
>>> mapping=H.node_labels
>>> mapping['C']==3
True
>>> mapping['D']==0
True
>>> mapping['A']==1 or mapping['A']==2
True
>>> mapping['B']==1 or mapping['B']==2
True

>>> G=empty_graph()
>>> G.add_edges_from([('C','D'),('A','B'),('A','C'),('B','C')])
>>> G.name="paw"
>>> H=convert_node_labels_to_integers(G,ordering="sorted")
>>> degH=H.degree()
>>> degG=G.degree()
>>> print degH.sort()==degG.sort()
True

>>> H=convert_node_labels_to_integers(G,ordering="sorted",discard_old_labels=False)
>>> mapping=H.node_labels
>>> mapping['A']==0
True
>>> mapping['B']==1
True
>>> mapping['C']==2
True
>>> mapping['D']==3
True

>>> H=convert_node_labels_to_integers(G,ordering="increasing age")
Traceback (most recent call last):
...
NetworkXError: unknown value of node ordering variable: ordering


relabel
-------
>>> G=empty_graph()
>>> G.add_edges_from([('A','B'),('A','C'),('B','C'),('C','D')])
>>> mapping={'A':'aardvark','B':'bear','C':'cat','D':'dog'}
>>> H=relabel_nodes(G,mapping)
>>> sorted(H.nodes())
['aardvark', 'bear', 'cat', 'dog']
>>> def mapping(n):
...    return ord(n)

>>> H=relabel_nodes(G,mapping)
>>> sorted(H.nodes())
[65, 66, 67, 68]