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

Timestamp:

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

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

 

Location:

src/work/marci

Files:

• bipartite_graphs.h (modified) (1 diff)
• makefile (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

src/work/marci/makefile

@@ -2 +2 @@
 CXX3=$(CXX)
 BOOSTROOT ?= /home/marci/boost
-INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
+INCLUDEDIRS ?= -I../../hugo -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
 
 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo