def test_add_graph(self):
     gr1 = testlib.new_graph()
     gr2 = testlib.new_graph()
     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_shortest_path_should_fail_if_source_does_not_exist(self):    
     gr = testlib.new_graph()
     try:
         shortest_path(gr, 'invalid')
         assert False
     except (KeyError):
         pass

 def test_remove_node(self):
     gr = testlib.new_graph()
     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_invert_graph(self):
     gr = testlib.new_graph()
     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_xml_for_graph(self):
     gr = testlib.new_graph()
     dotstr = markup.write(gr)
     gr1 = markup.read(dotstr)
     dotstr = markup.write(gr1)
     gr2 = markup.read(dotstr)  
     graph_equality(gr1, gr2)

 def test_order_len_equivlance(self):
     """
     Verify the behavior of G.order()
     """
     gr = testlib.new_graph()
     assert len(gr) == gr.order()
     assert gr.order() == len( gr.node_neighbors )

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

 def test_add_empty_graph(self):
     gr1 = testlib.new_graph()
     gr1c = copy(gr1)
     gr2 = graph()
     gr1.add_graph(gr2)
     self.assertTrue(gr1.nodes() == gr1c.nodes())
     self.assertTrue(gr1.edges() == gr1c.edges())

 def test_bfs_in_graph(self):
     gr = testlib.new_graph()
     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_repr(self):
     """
     Validate the repr string
     """
     gr = testlib.new_graph()
     gr_repr = repr(gr)
     assert isinstance(gr_repr, str )
     assert gr.__class__.__name__ in gr_repr

 def test_dfs_in_graph(self):
     gr = testlib.new_graph()
     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_graph(self):
     gr = testlib.new_graph()
     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_for_graph(self):
     gr = testlib.new_graph()
     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_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_connected_components_in_graph(self):
     gr = testlib.new_graph()
     gr.add_nodes(['a','b','c'])
     gr.add_edge(('a','b'))
     
     cc = connected_components(gr)
     
     for n in gr:
         for m in gr:
             if (cc[n] == cc[m]):
                 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_graph(self):
     gr = testlib.new_graph()
     gr.add_nodes(['a','b','c'])
     gr.add_edge(('a','b'))
     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_minimal_spanning_tree_on_graph(self):
     gr = testlib.new_graph(wt_range=(1,10))
     mst = minimal_spanning_tree(gr, root=0)
     wt = tree_weight(gr, mst)
     len_dfs = len(depth_first_search(gr, root=0)[0])
     for each in mst:
         if (mst[each] != None):
             mst_copy = deepcopy(mst)
             del(mst_copy[each])
             for other in gr[each]:
                  mst_copy[each] = other
                  if (tree_weight(gr, mst_copy) < wt):
                      gr2 = graph()
                      add_spanning_tree(gr2, mst_copy)
                      assert len(depth_first_search(gr2, root=0)[0]) < len_dfs

 def test_cut_edges_in_graph(self):
     gr = testlib.new_graph()
     gr.add_nodes(['x','y'])
     gr.add_edge(('x','y'))
     gr.add_edge(('x',0))
     
     gr_copy = deepcopy(gr)
     
     ce = cut_edges(gr)
     
     for each in ce:
         before = number_of_connected_components(connected_components(gr))
         gr.del_edge(each)
         number_of_connected_components(connected_components(gr)) > before
         gr = gr_copy

    def test_topological_sorting_on_tree(self):
        gr = testlib.new_graph()
        st, pre, post = depth_first_search(gr)
        tree = pygraph.classes.digraph.digraph()

        
        for each in st:
            if st[each]:
                if (each not in tree.nodes()):
                    tree.add_node(each)
                if (st[each] not in tree.nodes()):
                    tree.add_node(st[each])
                tree.add_edge(st[each], each)
        
        ts = topological_sorting(tree)
        for each in ts:
            if (st[each]):
                assert ts.index(each) > ts.index(st[each])

 def test_cut_tree_with_random_graph(self):
     gr = testlib.new_graph()
     ct = cut_tree(gr)