Changeset 549:5531429143bc in lemon-0.x for src/work

Timestamp:

05/06/04 17:10:48 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

 

Location:

src/work/marci

Files:

• bfs_dfs_misc.h (modified) (2 diffs)
• makefile (modified) (1 diff)
• top_sort.dim (added)
• top_sort_test.cc (added)

src/work/marci/bfs_dfs_misc.h

@@ -20 +20 @@
       if (!reached[n]) {
         bfs.pushAndSetReached(n);
-        bool_map.set(n, false) {
-          while (!bfs.finished()) {
-            if (bfs.isBNodeNewlyReached()) {
-              bool_map.set(bfs.bNode())=!bfs.aNode();
-            } else {
-              if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
-                return false;
-              }
+        bool_map.set(n, false);
+        while (!bfs.finished()) {
+          if (bfs.isBNodeNewlyReached()) {
+            bool_map.set(bfs.bNode())=!bfs.aNode();
+          } else {
+            if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
+              return false;
             }
-            ++bfs;
           }
+          ++bfs;
         }
       }
     }
+    
     return true;
   }
@@ -39 +39 @@
   /// experimental topsort, 
   /// I think the final version will work as an iterator
+  /// if the graph is not a acyclic, the na pre-topological order is obtained 
+  /// (see Schrijver's book)
   template<typename Graph> 
-  void topSort(Graph& g, std::list<typename Graph::Node>& l) {
+  void topSort(const Graph& g, std::list<typename Graph::Node>& l) {
     l.clear();
     typedef typename Graph::template NodeMap<bool> ReachedMap;

src/work/marci/makefile

@@ -5 +5 @@
 
 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
-BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_2 bipartite_matching_try_3
+BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_2 bipartite_matching_try_3 top_sort_test
 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda