Changeset 540:405ccc3105e1 in lemon-0.x for src/work/marci/bipartite_graphs.h

Timestamp:

05/06/04 15:44:48 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@712

Message:

 

File:

• src/work/marci/bipartite_graphs.h (modified) (1 diff)

src/work/marci/bipartite_graphs.h

@@ -36 +36 @@
     return true;
   }
+
+  /// experimental topsort, 
+  /// I think the final version will work as an iterator
+  template<typename Graph> 
+  void topSort(Graph& g, std::list<typename Graph::Node>& l) {
+    l.clear();
+    typedef typename Graph::template NodeMap<bool> ReachedMap;
+    ReachedMap reached(g/*, false*/);
+    DfsIterator<Graph, ReachedMap> dfs(g, reached);
+    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
+      if (!reached[n]) {
+        dfs.pushAndSetReached(n);
+        while (!bfs.finished()) {
+          if (bfs.isANodeExamined()) {
+            l.push_back(bfs.aNode());
+          }
+          ++bfs;
+        }
+      }
+    }
+  }
 }
 #endif //HUGO_BIPARTITE_GRAPHS_H