Changeset 657:531fc5f575ef in lemon-0.x for src/work

Timestamp:

05/24/04 12:43:44 (21 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

Not ready yet.

File:

• src/work/athos/mincostflow.h (modified) (6 diffs)

src/work/athos/mincostflow.h

@@ -11 +11 @@
 #include <hugo/maps.h>
 #include <vector>
+#include <list>
 #include <for_each_macros.h>
+#include <hugo/union_find.h>
 
 namespace hugo {
@@ -119 +121 @@
 
       typedef typename Graph::template NodeMap<int> HeapMap;
-      typedef Heap<Node, SupplyDemand, typename Graph::template NodeMap<int>,
+      typedef Heap< Node, SupplyDemand, typename Graph::template NodeMap<int>,
         std::greater<SupplyDemand> >    HeapType;
 
@@ -130 +132 @@
       HeapType deficit_nodes(deficit_nodes_map);
 
+      //A container to store nonabundant arcs
+      list<Edge> nonabundant_arcs;
       
       FOR_EACH_LOC(typename Graph::EdgeIt, e, G){
         flow.set(e,0);
+        nonabundant_arcs.push_back(e);
       }
 
       //Initial value for delta
       SupplyDemand delta = 0;
+
+      typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
+
+      //A union-find structure to store the abundant components
+      UFE::MapType abund_comp_map(G);
+      UFE abundant_components(abund_comp_map);
+
+
 
       FOR_EACH_LOC(typename Graph::NodeIt, n, G){
@@ -154 +167 @@
         //Initialize the copy of the Dijkstra potential to zero
         potential.set(n,0);
+        //Every single point is an abundant component initially 
+        abundant_components.insert(n);
       }
 
@@ -172 +187 @@
       while (max_excess > 0){
 
+        //Reset delta if still too big
+        if (8*number_of_nodes*max_excess <= delta){
+          delta = max_excess;
+          
+        }
+
         /*
          * Beginning of the delta scaling phase 
         */
-        
         //Merge and stuff
+        {
+          SupplyDemand buf=8*number_of_nodes*delta;
+          list<Edge>::iterator i = nonabundant_arcs.begin();
+          while ( i != nonabundant_arcs.end() ){
+            if (flow[i]>=buf){
+              Node a = abundant_components.find(res_graph.head(i));
+              Node b = abundant_components.find(res_graph.tail(i));
+              //Merge
+              if (a != b){
+                //Find path and augment
+                //!!!
+                //Find path and augment
+                abundant_components.join(a,b);
+              }
+              //What happens to i?
+              nonabundant_arcs.erase(i);
+            }
+            else
+              ++i;
+          }
+        }
+
 
         Node s = excess_nodes.top(); 
@@ -262 +304 @@
         }
         */
-        //Reset delta if still too big
-        if (8*number_of_nodes*max_excess <= delta){
-          delta = max_excess;
-          
-        }
+
           
       }//while(max_excess > 0)