def test_add_digraph(self):
     gr1 = testlib.new_digraph()
     gr2 = testlib.new_digraph()
     gr1.add_graph(gr2)
     for each in gr2.nodes():
         self.assertTrue(each in gr1)
     for each in gr2.edges():
         self.assertTrue(each in gr1.edges())

 def test_add_empty_digraph(self):
     gr1 = testlib.new_digraph()
     gr1c = copy(gr1)
     gr2 = digraph()
     gr1.add_graph(gr2)
     self.assertTrue(gr1.nodes() == gr1c.nodes())
     self.assertTrue(gr1.edges() == gr1c.edges())

 def test_reverse_digraph(self):
     gr = testlib.new_digraph()
     rev = gr.reverse()
     for (u, v) in gr.edges():
         self.assertTrue((v, u) in rev.edges())
     for (u, v) in rev.edges():
         self.assertTrue((v, u) in gr.edges())

 def test_invert_digraph(self):
     gr = testlib.new_digraph()
     inv = gr.inverse()
     for each in gr.edges():
         self.assertTrue(each not in inv.edges())
     for each in inv.edges():
         self.assertTrue(each not in gr.edges())

 def test_shortest_path_on_digraph(self):
     # Test stub: not checking for correctness yet
     gr = testlib.new_digraph(wt_range=(1,10))
     st, dist = shortest_path(gr, 0)
     for each in gr:
         if (each in dist):
             assert bf_path(gr, 0, each, dist[each])    

 def test_dot_xml_digraph(self):
     gr = testlib.new_digraph()
     dotstr = markup.write(gr)
     gr1 = markup.read(dotstr)
     dotstr = markup.write(gr1)
     gr2 = markup.read(dotstr)  
     graph_equality(gr1, gr2)

 def test_dot_for_digraph(self):
     gr = testlib.new_digraph()
     dotstr = dot.write(gr)
     gr1 = dot.read(dotstr)
     dotstr = dot.write(gr1)
     gr2 = dot.read(dotstr)  
     graph_equality(gr1, gr2)

 def test_remove_node(self):
     gr = testlib.new_digraph()
     gr.del_node(0)
     self.assertTrue(0 not in gr)
     for each, other in gr.edges():
         self.assertTrue(each in gr)
         self.assertTrue(other in gr)

 def test_bfs_in_digraph(self):
     gr = testlib.new_digraph()
     st, lo = breadth_first_search(gr)
     for each in gr:
         if (st[each] != None):
             assert lo.index(each) > lo.index(st[each])
     for node in st:
         assert gr.has_edge((st[node], node)) or st[node] == None

 def test_bfs_in_digraph(self):
     gr = testlib.new_digraph()
     gr.add_node('find-me')
     gr.add_edge((0, 'find-me'))
     st, lo = breadth_first_search(gr, root=0, filter=find('find-me'))
     assert st['find-me'] == 0
     for each in st:
         assert st[each] == None or st[each] == 0 or st[st[each]] == 0

 def test_dfs_in_digraph(self):
     gr = testlib.new_digraph()
     st, pre, post = depth_first_search(gr)
     for each in gr:
         if (st[each] != None):
             assert pre.index(each) > pre.index(st[each])
             assert post.index(each) < post.index(st[each])
     for node in st:
         assert gr.has_edge((st[node], node)) or st[node] == None

 def test_dfs_in_digraph(self):
     gr = testlib.new_digraph()
     gr.add_node('find-me')
     gr.add_node('dont-find-me')
     gr.add_edge((0, 'find-me'))
     gr.add_edge(('find-me','dont-find-me'))
     st, pre, post = depth_first_search(gr, root=0, filter=find('find-me'))
     assert st['find-me'] == 0
     assert 'dont-find-me' not in st

 def test_xml_digraph(self):
     gr = testlib.new_digraph()
     dotstr = markup.write(gr)
     gr1 = markup.read(dotstr)
     dotstr = markup.write(gr1)
     gr2 = markup.read(dotstr)  
     graph_equality(gr1, gr2)
     assert len(gr.nodes()) == len(gr1.nodes())
     assert len(gr.edges()) == len(gr1.edges())

 def test_dot_for_digraph(self):
     gr = testlib.new_digraph()
     dotstr = dot.write(gr)
     gr1 = dot.read(dotstr)
     dotstr = dot.write(gr1)
     gr2 = dot.read(dotstr)  
     graph_equality(gr1, gr2)
     assert len(gr.nodes()) == len(gr1.nodes())
     assert len(gr.edges()) == len(gr1.edges())

 def test_output_names_in_dot(self):
     gr1 = testlib.new_graph()
     gr1.name = "Some name 1"
     gr2 = testlib.new_digraph()
     gr2.name = "Some name 2"
     gr3 = testlib.new_hypergraph()
     gr3.name = "Some name 3"
     assert "Some name 1" in dot.write(gr1)
     assert "Some name 2" in dot.write(gr2)
     assert "Some name 3" in dot.write(gr3)

 def test_pagerank_random(self):
     G = testlib.new_digraph()
     md = 0.00001
     df = 0.85
     pr = pagerank(G, damping_factor=df, min_delta=md)
     min_value = (1.0-df)/len(G)
     for node in G:
         expected = min_value
         for each in G.incidents(node):
             expected += (df * pr[each] / len(G.neighbors(each)))
         assert abs(pr[node] - expected) < md

 def test_mutual_accessibility_in_digraph(self):
     gr = testlib.new_digraph()
     
     ma = mutual_accessibility(gr)
     for n in gr:
         for m in gr:
             if (m in ma[n]):
                 assert m in depth_first_search(gr, n)[0]
                 assert n in depth_first_search(gr, m)[0]
             else:
                 assert m not in depth_first_search(gr, n)[0] or n not in depth_first_search(gr, m)[0]

 def test_accessibility_in_digraph(self):
     gr = testlib.new_digraph()
     gr.add_nodes(['a','b','c'])
     gr.add_edge(('a','b'))
     gr.add_edge(('a','c'))
     
     ac = accessibility(gr)
     
     for n in gr:
         for m in gr:
             if (m in ac[n]):
                 assert m in depth_first_search(gr, n)[0]
             else:
                 assert m not in depth_first_search(gr, n)[0]

 def test_mutual_accessibility_in_digraph(self):
     gr = testlib.new_digraph()
     gr.add_nodes(['a','b','c'])
     gr.add_edge(('a','b'))
     gr.add_edge(('b','a'))
     gr.add_edge(('a','c'))
     
     ma = mutual_accessibility(gr)
     for n in gr:
         for m in gr:
             if (m in ma[n]):
                 assert m in depth_first_search(gr, n)[0]
                 assert n in depth_first_search(gr, m)[0]
             else:
                 assert m not in depth_first_search(gr, n)[0] or n not in depth_first_search(gr, m)[0]

 def test_topological_sorting_on_digraph(self):
     
     def is_ordered(node, list):
         # Has parent on list
         for each in list:
             if gr.has_edge(each, node):
                 return True
         # Has no possible ancestors on list
         st, pre, post = depth_first_search(gr, node)
         for each in list:
             if (each in st):
                 return False
         return True
         
     gr = testlib.new_digraph()
     ts = topological_sorting(gr)
     
     while (ts):
         x = ts.pop()
         assert is_ordered(x, ts)