Changeset 194:a1680b3c516c in lemon-0.x for src/work

Timestamp:

03/17/04 16:09:48 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

.

Location:

src/work

Files:

• edmonds_karp.h (modified) (5 diffs)
• marci/makefile (modified) (2 diffs)
• marci/max_bipartite_matching_demo.cc (modified) (3 diffs)

src/work/edmonds_karp.h

@@ -533 +533 @@
   public:
     typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
     typedef typename Graph::Edge Edge;
     typedef typename Graph::EdgeIt EdgeIt;
@@ -564 +565 @@
       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
         Number f=0;
-        for(OutEdgeIt e=G->template first<OutEdgeIt>(); G->valid(e); G->next(e))
+        for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
           f+=flow->get(e);
         if (f<1) {
@@ -587 +588 @@
             free.set(w, res_graph.free(e)); 
           }
-          if (TMap(res_graph.head(e))) { 
+          if (T->get(res_graph.head(e))) { 
             n=res_graph.head(e);
             _augment=true; 
@@ -599 +600 @@
       if (_augment) {
         //Node n=t;
-        Number augment_value=free.get(t);
+        Number augment_value=free.get(n);
         while (res_graph.valid(pred.get(n))) { 
           AugEdge e=pred.get(n);
@@ -806 +807 @@
       } 
     }
-    template<typename MutableGraph> void run() {
-      //int num_of_augmentations=0;
-      //while (augmentOnShortestPath()) { 
-        while (augmentOnBlockingFlow<MutableGraph>()) { 
-        //std::cout << ++num_of_augmentations << " ";
-        //std::cout<<std::endl;
-      } 
-    }
+//     template<typename MutableGraph> void run() {
+//       //int num_of_augmentations=0;
+//       //while (augmentOnShortestPath()) { 
+//      while (augmentOnBlockingFlow<MutableGraph>()) { 
+//      //std::cout << ++num_of_augmentations << " ";
+//      //std::cout<<std::endl;
+//       } 
+//     } 
     Number flowValue() { 
       Number a=0;
-      OutEdgeIt e;
-      for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
+      EdgeIt e;
+      for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
         a+=flow->get(e);
       }

src/work/marci/makefile

@@ -10 +10 @@
 
 
-BINARIES = edmonds_karp_demo preflow_demo_leda lg_vs_sg leda_graph_demo leda_bfs_dfs
+BINARIES = edmonds_karp_demo preflow_demo_leda lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
 #preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar
 
@@ -28 +28 @@
 leda_graph_demo: leda_graph_demo.o
         $(CXX3) -Wall -O -L$(LEDAROOT) -o leda_graph_demo leda_graph_demo.o -lG -lL -lm
+
+max_bipartite_matching_demo.o:
+        $(CXX3) -Wall -O -I.. -I../alpar -I$(LEDAROOT)/incl -I. -c max_bipartite_matching_demo.cc
+
+max_bipartite_matching_demo: max_bipartite_matching_demo.o
+        $(CXX3) -Wall -O -L$(LEDAROOT) -o max_bipartite_matching_demo max_bipartite_matching_demo.o -lG -lL -lm
 
 leda_bfs_dfs.o:

src/work/marci/max_bipartite_matching_demo.cc

@@ -50 +50 @@
   typedef Graph::InEdgeIt InEdgeIt;
 
-  Node s, t;
+  //Node s, t;
   //Graph::EdgeMap<int> cap(G);
   //readDimacsMaxFlow(std::cin, G, s, t, cap);
@@ -66 +66 @@
     G.addEdge(s_nodes[random(20)], t_nodes[random(20)]);
   }
-  Graph::NodeMap<bool> s_map; //false
-  Graph::NodeMap<bool> t_map; //false
+  Graph::NodeMap<bool> s_map(G); //false
+  Graph::NodeMap<bool> t_map(G); //false
   
   for(int i=0; i<20; ++i) {
@@ -77 +77 @@
     std::cout << "on-the-fly max bipartite matching demo on wrapped leda graph..." << std::endl;
     Graph::EdgeMap<int> flow(G); //0 flow
-    Graph::EdgeMap<int> capacity(G, 1);
+    Graph::EdgeMap<int> cap(G, 1);
 
     Timer ts;