Changeset 298:315d826faa8f in lemon-0.x for src/work/marci/experiment/edmonds_karp_1.h

Timestamp:

04/05/04 16:19:02 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

graph_wrappers ...

File:

• src/work/marci/experiment/edmonds_karp_1.h (modified) (2 diffs)

src/work/marci/experiment/edmonds_karp_1.h

@@ -249 +249 @@
 
 
-  template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
+  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
   class MaxFlow {
   protected:
-    typedef GraphWrapper GW;
-    typedef typename GW::Node Node;
-    typedef typename GW::Edge Edge;
-    typedef typename GW::EdgeIt EdgeIt;
-    typedef typename GW::OutEdgeIt OutEdgeIt;
-    typedef typename GW::InEdgeIt InEdgeIt;
-    //const Graph* G;
-    //GW gw;
-    const GW* g;
+    typedef typename Graph::Node Node;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::EdgeIt EdgeIt;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    typedef typename Graph::InEdgeIt InEdgeIt;
+    const Graph* g;
     Node s;
     Node t;
     FlowMap* flow;
     const CapacityMap* capacity;
-    typedef ResGraphWrapper<const GW, Number, FlowMap, CapacityMap > ResGW;
+    typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW;
     typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
     typedef typename ResGW::Edge ResGWEdge;
   public:
 
-    MaxFlow(const GW& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : 
+    MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : 
       g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
 
@@ -646 +643 @@
       return _augment;
     }
-
-//     bool augmentOnBlockingFlow2() {
-//       bool _augment=false;
-
-//       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
-//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
-//       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
-//       typedef typename EAugGraph::Edge EAugEdge;
-
-//       EAugGraph res_graph(*G, *flow, *capacity);
-
-//       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
-//       BfsIterator5< 
-//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 
-//      /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ 
-//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
-      
-//       bfs.pushAndSetReached(s);
-
-//       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
-//      NodeMap<int>& dist=res_graph.dist;
-
-//       while ( !bfs.finished() ) {
-//      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
-//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
-//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
-//      }
-//      ++bfs;  
-//       } //computing distances from s in the residual graph
-
-//       bool __augment=true;
-
-//       while (__augment) {
-
-//      __augment=false;
-//      //computing blocking flow with dfs
-//      typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
-//      DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > 
-//        dfs(res_graph);
-//      typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); 
-//      pred.set(s, EAugEdge(INVALID));
-//      //invalid iterators for sources
-
-//      typename EAugGraph::NodeMap<Number> free(res_graph);
-
-//      dfs.pushAndSetReached(s);
-//      while (!dfs.finished()) {
-//        ++dfs;
-//        if (res_graph.valid(EAugOutEdgeIt(dfs))) { 
-//          if (dfs.isBNodeNewlyReached()) {
-          
-//            typename EAugGraph::Node v=res_graph.aNode(dfs);
-//            typename EAugGraph::Node w=res_graph.bNode(dfs);
-
-//            pred.set(w, EAugOutEdgeIt(dfs));
-//            if (res_graph.valid(pred.get(v))) {
-//              free.set(w, std::min(free.get(v), res_graph.free(dfs)));
-//            } else {
-//              free.set(w, res_graph.free(dfs)); 
-//            }
-              
-//            if (w==t) { 
-//              __augment=true; 
-//              _augment=true;
-//              break; 
-//            }
-//          } else {
-//            res_graph.erase(dfs);
-//          }
-//        } 
-
-//      }
-
-//      if (__augment) {
-//        typename EAugGraph::Node n=t;
-//        Number augment_value=free.get(t);
-//        while (res_graph.valid(pred.get(n))) { 
-//          EAugEdge e=pred.get(n);
-//          res_graph.augment(e, augment_value);
-//          n=res_graph.tail(e);
-//          if (res_graph.free(e)==0)
-//            res_graph.erase(e);
-//        }
-//      }
-      
-//       }
-            
-//       return _augment;
-//     }
 
     void run() {