PseudoGraph
=============

Unit tests for PseudoGraph version of XGraph in xgraph.py
---------------------------------------------------------


In addition to the usual suspects 
(the simple graphs P1, P2, P3, K1, K2, null, etc.)
we perform unit tests with the following three PseudoGraphs:

  - G: PseudoGraph with nodes A,B,C,...
       named "test",
       first grown and the deleted



  - H: copy of G with extra integer nodes from P3 and K3

  - K: famous Konigsberg graph (from Euler) with nodes: A,B,C,D 
       named 'Konigsberg'
      
       .. class:: doctest-block
       .. image:: base_PseudoGraph_K.png

  - Km: Konigsberg graph with named, multiple bridges
        (m->multiedges=True)

  - Kms: Km + 2 self-loops at node D
         (ms->multiedges=True and selfloops=True)

  - L: PseudoGraph over two nodes 1 and 2 with 3 self-loops on 1
       and 4 parallel edges between 1 and 2.

>>> from pprint import *

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

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

>>> null=null_graph()
>>> P1=path_graph(1)
>>> P3=path_graph(3)
>>> P10=path_graph(10)
>>> K1=complete_graph(1)
>>> K3=complete_graph(3)
>>> K5=complete_graph(5)

Name
----

>>> G = XGraph(name="test", multiedges=True, selfloops=True)
>>> print G    # test of __str__
test
>>> print G.name
test

>>> H=XGraph(multiedges=True, selfloops=True)
>>> print H.name
No Name

The first PseudoGraph
(cf. http://mathworld.wolfram.com/KoenigsbergBridgeProblem.html)

>>> K=XGraph(name="Konigsberg", multiedges=True, loops=True) 
>>> sorted(K) # test empty K.__iter__
[]
>>> 'Euler' in K # test __contains__
False
>>> len(K) # test K.__len__
0
>>> K.__str__() # name
'Konigsberg'


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

G.clear()
>>> 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 undirected
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')  # There should now be two undirected edges
>>> G.get_edge('A','C')
[1, 1]
>>> 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')
True

>>> 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')  # 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('HI'),tuple('DD'),tuple('IJ'),tuple('JK')])
>>> G.has_edge(('I','J'))
True
>>> G.has_edge(('D','D'))
True
>>> 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.delete_edge('D','D')  # test self loops
>>> G.has_edge('D','D')
False
>>> G.add_edge('N','M')  
>>> G.get_edge('M','N')
[1, 1]
>>> G.delete_edge('M','N')  # delete all parallel edges if none specified
>>> 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(list('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']

pprint(sorted(G.edges()))

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

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

nbunch can be a set

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

nbunch can be a graph

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

nbunch can be a dict with nodes as keys

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

nbunch can be a single node

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

G.edges() does not support with_labels=True option

>>> sorted(G.edges(with_labels=True))
Traceback (most recent call last):
...
NetworkXError: with_labels=True option not supported. Rather use neighbors()


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

nbunch can be a set

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

nbunch can be a graph

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

nbunch can be a dict with nodes as keys

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

nbunch can be a single node

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

G.edges_iter() does not support with_labels=True option

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

nbunch can be nothing (whole graph)

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

At this stage G should be the following PseudoGraph:

.. class:: doctest-block
.. image:: base_PseudoGraph_G.png


*Now make H*

>>> H=G.copy()
>>> H.delete_nodes_from( ['G', 'J', 'K'])
>>> sorted(H.edges())  # test copy
[('A', 'A', 1), ('A', 'B', 1), ('A', 'B', 1), ('A', 'C', 1), ('B', 'D', 1), ('C', 'B', 1), ('C', 'D', 1)]

Now grow and shrink H using various forms of nbunch
 
>>> H.add_nodes_from(P3) # add nbunch of nodes (nbunch=Graph)
>>> sorted(H.nodes())
[1, 2, 3, 'A', 'B', 'C', 'D']
>>> H.delete_nodes_from(P3) # delete nbunch of nodes (nbunch=Graph)
>>> sorted(H.nodes())
['A', 'B', 'C', 'D']

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

>>> nbunch=P3.degree(with_labels=True) # create dict with keys to add
>>>                                    # to H
>>> H.add_nodes_from(nbunch) # add nbunch of nodes (nbunch=dict)
>>> sorted(H.nodes())
[1, 2, 3, 'A', 'B', 'C', 'D']
>>> H.delete_nodes_from(nbunch) # delete nbunch of nodes (nbunch=dict)
>>> sorted(H.nodes())
['A', 'B', 'C', 'D']


Build Konigsberg graph using only add_edge

>>> K.add_edges_from([("A","B"),("A","B")])
>>> K.add_edges_from([("A","C"),("A","C")])
>>> K.add_edges_from([("A","D"),("C","D"),("B","D")])


>>> sorted(K) # test K.__iter__
['A', 'B', 'C', 'D']
>>> 'A' in K # test contains
True

Build Km, Konigsberg graph with named edges

>>> Km=XGraph(name="Konigsberg",multiedges=True)
>>> Km.add_edges_from([("A","B","Honey"),("A","B","Blacksmith's")])
>>> Km.add_edges_from([("A","C","Green"),("A","C","Connecting")])
>>> Km.add_edges_from([("A","D","Merchant's"),("C","D","High"),("B","D","Wooden")])

Build Kms = Km + 2 self-loops at node D

>>> Kms=XGraph(name="Konigsberg",multiedges=True,selfloops=True)
>>> Kms.add_edges_from(Km.edges())
>>> Kms.add_edge(["D","D","D self-loop 1"])
>>> Kms.add_edge(["D","D","D self-loop 2"])


Build graph L: 3 self-loops + 4-skein

>>> L=XGraph(multiedges=True, selfloops=True)
>>> L.add_edges_from([(1,1),(1,1),(1,1)]) # 3 self-loops at node 1
>>> L.add_edges_from([(1,2),(1,2),(1,2),(1,2)]) # 4 parallel edges
>>> sorted(L.edges())
[(1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 2, 1), (1, 2, 1), (1, 2, 1), (1, 2, 1)]

>>> sorted(L.edges([1,2]))
[(1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 2, 1), (1, 2, 1), (1, 2, 1), (1, 2, 1)]



Extracting objects imbedded into edges.
---------------------------------------

>>> H.clear()
>>> H.add_edge(1,2,"hi")
>>> H.get_edge(1,2)
['hi']
>>> H.edges(1)
[(1, 2, 'hi')]
>>> sorted(H.edges_iter(1))
[(1, 2, 'hi')]
>>> sorted(H.nodes())
[1, 2]
>>> H.add_edges_from([(1,2,"there"),(1,3,"oof"),(1,1,"loop")])
>>> sorted(H.edges(1))
[(1, 1, 'loop'), (1, 2, 'hi'), (1, 2, 'there'), (1, 3, 'oof')]
>>> sorted(H.edges(2))
[(2, 1, 'hi'), (2, 1, 'there')]
>>> sorted(H.edges())
[(1, 1, 'loop'), (1, 2, 'hi'), (1, 2, 'there'), (1, 3, 'oof')]
>>> sorted(H.edges_iter(1))
[(1, 1, 'loop'), (1, 2, 'hi'), (1, 2, 'there'), (1, 3, 'oof')]
>>> sorted(H.edges_iter(2))
[(2, 1, 'hi'), (2, 1, 'there')]
>>> sorted(H.edges_iter())
[(1, 1, 'loop'), (1, 2, 'hi'), (1, 2, 'there'), (1, 3, 'oof')]
>>> H.delete_edge(1,1,'ooops')   # should fail silently
>>> H.delete_edge(1,1,'loop')   
>>> sorted(H.edges(1))
[(1, 2, 'hi'), (1, 2, 'there'), (1, 3, 'oof')]
>>> H.delete_edge(1,2) # should delete both edges between 1 and 2 
>>> sorted(H.edges(1))
[(1, 3, 'oof')]
>>> H.add_edges_from([(4,5),(4,6),(3,4)])
>>> sorted(H.edges(4))
[(4, 3, 1), (4, 5, 1), (4, 6, 1)]
>>> H.add_edge(5,6)
>>> sorted(H.edges(6))
[(6, 4, 1), (6, 5, 1)]
>>> H.add_edges_from([(4,5),(1,1)])
>>> sorted(H.edges(4))
[(4, 3, 1), (4, 5, 1), (4, 5, 1), (4, 6, 1)]
>>> sorted(H.edges(1))
[(1, 1, 1), (1, 3, 'oof')]
>>> sorted(H.nodes())
[1, 2, 3, 4, 5, 6]
>>> H.delete_nodes_from([1,2,3,4,5,6])
>>> sorted(H.edges(1))
[]



Properties
----------

degree of single node must return single int

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

degree of single node in iterable container must return list

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

with_labels=True always return a dict with nodes as keys

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

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

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


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

*Back in Konigsberg*

>>> number_of_nodes(K)
4
>>> number_of_edges(K)
7



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

copy
---- 

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

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

  # to_directed


*Back in Konigsberg*

>>> Ksub=K.subgraph(['A','B'])
>>> sorted( Ksub.edges() )
[('A', 'B', 1), ('A', 'B', 1)]

Neighbors
---------

>>> sorted(G['A'])   # test __getitem__
['A', 'B', 'C']
>>> sorted(G.neighbors('A'))
['A', 'B', 'C']
>>> sorted(G.neighbors_iter('A'))
['A', 'B', 'C']
>>> G.neighbors('A',with_labels=True)
{'A': [1], 'C': [1], 'B': [1, 1]}
>>> sorted(G.neighbors_iter('A',with_labels=True))
[('A', [1]), ('B', [1, 1]), ('C', [1])]


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

>>> sorted(nodes(G))
['A', 'B', 'C', 'D', 'G', 'J', 'K']
>>> sorted(edges(G))
[('A', 'A', 1), ('A', 'B', 1), ('A', 'B', 1), ('A', 'C', 1), ('B', 'D', 1), ('C', 'B', 1), ('C', 'D', 1)]

>>> sorted(degree(G))
[0, 0, 0, 2, 3, 4, 5]
>>> sorted(neighbors(G,'A'))
['A', 'B', 'C']
>>> neighbors(G,'A',with_labels=True)
{'A': [1], 'C': [1], 'B': [1, 1]}

>>> number_of_nodes(G)
7
>>> number_of_edges(G)
7


*Back in Konigsberg*

>>> sorted(nodes(K))
['A', 'B', 'C', 'D']
>>> pprint(sorted(edges(K)))
[('A', 'B', 1),
 ('A', 'B', 1),
 ('A', 'C', 1),
 ('A', 'C', 1),
 ('A', 'D', 1),
 ('B', 'D', 1),
 ('C', 'D', 1)]

>>> pprint(sorted(edges(Km)))
[('A', 'B', "Blacksmith's"),
 ('A', 'B', 'Honey'),
 ('A', 'C', 'Connecting'),
 ('A', 'C', 'Green'),
 ('A', 'D', "Merchant's"),
 ('B', 'D', 'Wooden'),
 ('C', 'D', 'High')]

>>> pprint(sorted(edges(Kms)))
[('A', 'B', "Blacksmith's"),
 ('A', 'B', 'Honey'),
 ('A', 'C', 'Connecting'),
 ('A', 'C', 'Green'),
 ('A', 'D', "Merchant's"),
 ('B', 'D', 'Wooden'),
 ('C', 'D', 'High'),
 ('D', 'D', 'D self-loop 1'),
 ('D', 'D', 'D self-loop 2')]


Iterators
---------

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

>>> sorted(G.degree())
[0, 0, 0, 2, 3, 4, 5]

>>> sorted(G.degree_iter())
[0, 0, 0, 2, 3, 4, 5]

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


*Back in Konigsberg*

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

>>> sorted(K.degree_iter())
[3, 3, 3, 5]

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

>>> sorted(K.neighbors_iter('B'))
['A', 'D']

>>> sorted(K.neighbors_iter('C'))
['A', 'D']

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

>>> sorted(K.neighbors_iter('X'))
Traceback (most recent call last):
...
NetworkXError: node X not in graph


ban_selfloops, clear
--------------------

>>> G.ban_selfloops()
>>> sorted(G.edges())
[('A', 'B', 1), ('A', 'B', 1), ('A', 'C', 1), ('B', 'D', 1), ('C', 'B', 1), ('C', 'D', 1)]
>>> G.clear()
>>> number_of_nodes(G)
0

*Back in Konigsberg*

>>> K.ban_selfloops() # no selfloops, so should be unchanged
>>> sorted(K.edges())
[('A', 'B', 1), ('A', 'B', 1), ('A', 'C', 1), ('A', 'C', 1), ('A', 'D', 1), ('B', 'D', 1), ('C', 'D', 1)]
>>> K.clear()
>>> number_of_nodes(K)
0
