Changeset 2514:57143c09dc20 in lemon-0.x for demo

Timestamp:

11/17/07 21:58:11 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Redesign the maximum flow algorithms

Redesigned interface
Preflow changed to use elevator
Edmonds-Karp does not use the ResGraphAdaptor?
Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)

Location:

demo

Files:

• disjoint_paths_demo.cc (modified) (4 diffs)
• sub_graph_adaptor_demo.cc (modified) (2 diffs)

demo/disjoint_paths_demo.cc

@@ -64 +64 @@
   Graph::EdgeMap<int> flow(graph);
 
-  Preflow<Graph, int, Capacity> preflow(graph, source, target, capacity, flow); 
+  Preflow<Graph, Capacity> preflow(graph, capacity, source, target); 
   
   preflow.run();
@@ -73 +73 @@
     title("edge disjoint paths").scaleToA4().
     copyright("(C) 2003-2007 LEMON Project").drawArrows().
-    edgeColors(composeMap(functorMap(color), flow)).
+    edgeColors(composeMap(functorMap(color), preflow.flowMap())).
     coords(coords).run();
 
@@ -88 +88 @@
   SGraph::EdgeMap<int> sflow(sgraph);
 
-  Preflow<SGraph, int, SCapacity> spreflow(sgraph, SGraph::outNode(source), 
-                                           SGraph::inNode(target), 
-                                           scapacity, sflow);
+  Preflow<SGraph, SCapacity> spreflow(sgraph, scapacity, 
+                                      SGraph::outNode(source), 
+                                      SGraph::inNode(target));
 
   spreflow.run();
@@ -100 +100 @@
     title("node disjoint paths").scaleToA4().
     copyright("(C) 2003-2007 LEMON Project").drawArrows().
-    edgeColors(composeMap(functorMap(color), sflow)).
+    edgeColors(composeMap(functorMap(color), spreflow.flowMap())).
     coords(SGraph::combinedNodeMap(coords,
                                    shiftMap(coords,

demo/sub_graph_adaptor_demo.cc

@@ -110 +110 @@
 
   ConstMap<Edge, int> const_1_map(1);
-  Graph::EdgeMap<int> flow(g, 0);
   // Max flow between s and t in the graph of tight edges.
-  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
-    preflow(gw, s, t, const_1_map, flow);
+  Preflow<SubGW, ConstMap<Edge, int> > preflow(gw, const_1_map, s, t);
   preflow.run();
 
@@ -121 +119 @@
        << endl;
   for(EdgeIt e(g); e!=INVALID; ++e) 
-    if (flow[e])
+    if (preflow.flow(e) != 0)
       cout << " " << g.id(e) << ", "
            << g.id(g.source(e)) << "--"