def test_dfs_very_deep_graph(self):
     gr = pygraph.classes.graph.graph()
     gr.add_nodes(range(0,20001))
     for i in range(0,20000):
         gr.add_edge((i,i+1))
     recursionlimit = getrecursionlimit()
     depth_first_search(gr, 0)
     assert getrecursionlimit() == recursionlimit

 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 testGraphDFS(self):
     G = pygraph.graph()
     G.add_nodes([1, 2, 3, 4, 5])
     G.add_edge(1, 2)
     G.add_edge(2, 3)
     G.add_edge(2, 4)
     G.add_edge(4, 5)
     G.add_edge(1, 5)
     G.add_edge(3, 5)
     st, pre, post = depth_first_search(G, 1, filter=filters.find(5))
     assert st == {1: None, 2: 1, 3: 2, 5: 3}
     st, pre, post = depth_first_search(G, 1, filter=filters.find(2))
     assert st == {1: None, 2: 1}

 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_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_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 get_connected(self, obj, aklass=None):
   st, pre, post = depth_first_search(self.gr, root=obj.id)
   if aklass:
     return [self.obj_by_id[k] for k in st.keys()
             if self.obj_by_id[k].__class__ == aklass]
   else:
     return [self.obj_by_id[k] for k in st.keys()]

def gen_gv(graph, word):
  """
  Given the source word for definition, build the gv graph based on 
  depth first search result on the given graph
  """

  st, pre, post = depth_first_search(graph, root=word)
  gst = digraph()
  gst.add_spanning_tree(st)
  
  dot = Digraph(comment=word)
  nodes = gst.nodes()
  edges =  gst.edges()
  
  for node in nodes:
    dot.node(node)

  for edge in edges:
    dot.edge(edge[0], edge[1])

  print dot.source
  word = word.decode('utf-8')
  gv_path = 'output/' + word + '.gv'
  # dot.render(gv_path, view=True)
  outf = codecs.open(gv_path, 'w', 'utf-8')

  outf.write(dot.render(gv_path, view=True))

  outf.close()

    def write_graphs_to_dots(self):
        assert self.build_graph
        self._load_packages()

        from pygraph.readwrite import dot

        base = self.output_dir

        with open(join(base, 'digraph.dot'), 'w') as f:
            data = dot.write(self.digraph)
            f.write(data)

        with open(join(base, 'bfs.dot'), 'w') as f:
            (st, order) = breadth_first_search(self.digraph)
            bfs = digraph()
            bfs.add_spanning_tree(st)
            data = dot.write(bfs)
            f.write(data)

        with open(join(base, 'dfs.dot'), 'w') as f:
            (st, pre, post) = depth_first_search(self.digraph)
            dfs = digraph()
            dfs.add_spanning_tree(st)
            data = dot.write(dfs)
            f.write(data)

 def testDigraphDFS(self):
     G = pygraph.digraph()
     G.add_nodes([1, 2, 3, 4, 5, 6, 7, 8, 9])
     G.add_edge(1, 2)
     G.add_edge(1, 3)
     G.add_edge(2, 4)
     G.add_edge(3, 5)
     G.add_edge(4, 6)
     G.add_edge(5, 7)
     G.add_edge(1, 8, wt=3)
     G.add_edge(7, 8, wt=3)
     G.add_edge(8, 9)
     G.add_edge(3, 9)
     st, pre, post = depth_first_search(G, 1, filter=filters.radius(2))
     assert st == {1: None, 2: 1, 3: 1, 4: 2, 5: 3, 9: 3}
     st, pre, post = depth_first_search(G, 7, filter=filters.radius(2))
     assert st == {7: None}

 def testSanityDigraph(self):
     G = pygraph.digraph()
     G.generate(100, 500)
     st, pre, post = depth_first_search(G)
     for each in G:
         if (st[each] != None):
             assert pre.index(each) > pre.index(st[each])
             assert post.index(each) < post.index(st[each])

def main():
    sweep()
    print node_par
    print dg2
    tranverse(dg2)
    print dg2
    st,pre,post = depth_first_search(dg2,root=0)
    print st

 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_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 output_graph(graph, root=None):
    """
    Returns a tuplet containing:
    - the result of the depth_first_search() function starting at 'root' (is is a tuplet)
    - a dot format output of the given graph (display it using graphviz dotty command)
    """

    dfs = depth_first_search(graph, root)
    dot = write(graph)
    return [dfs, dot]

 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

 def discourse_units(self):
     discourse_units = digraph()
     for tup in self.tuples:
         if tup.structure == "discourse" or tup.edge_type == "dominates" or "subordinates" in tup.edge_type:
             if not tup.from_node in discourse_units.nodes():
                 discourse_units.add_node(tup.from_node)
             if not tup.to_node in discourse_units.nodes():
                 discourse_units.add_node(tup.to_node)
             discourse_units.add_edge((tup.from_node, tup.to_node))
     st, order_pre, order_post = depth_first_search(discourse_units, root="k0")
     return order_pre

 def testDigraph(self):
     G = pygraph.digraph()
     G.add_nodes([1, 2, 3, 4, 5])
     G.add_edge(1, 2)
     G.add_edge(2, 3)
     G.add_edge(2, 4)
     G.add_edge(4, 5)
     G.add_edge(1, 5)
     G.add_edge(3, 5)
     st, pre, post = depth_first_search(G)
     assert st == {1: None, 2: 1, 3: 2, 4: 2, 5: 3}
     assert pre == [1, 2, 3, 5, 4]
     assert post == [5, 3, 4, 2, 1]

def topological_sorting(graph):
    """
    Topological sorting.

    @attention: Topological sorting is meaningful only for directed acyclic graphs.

    @type  graph: digraph
    @param graph: Graph.

    @rtype:  list
    @return: Topological sorting for the graph.
    """
    # The topological sorting of a DAG is equivalent to its reverse postordering.
    order = depth_first_search(graph)[2]
    order.reverse()
    return order