Changeset 148:004fdf703abb in lemon-0.x for src/work/edmonds_karp.hh

Timestamp:

03/03/04 15:30:38 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

G.next(...), G.valid(...), ...

File:

• src/work/edmonds_karp.hh (modified) (26 diffs)

src/work/edmonds_karp.hh

@@ -149 +149 @@
       OldOutEdgeIt out;
       OldInEdgeIt in;
-      bool out_or_in; //1, iff out
-    public:
-      EdgeIt() : out_or_in(1) { } 
+      bool out_or_in; //true, iff out
+    public:
+      EdgeIt() : out_or_in(true) { } 
       Number free() const { 
         if (out_or_in) { 
@@ -247 +247 @@
 
   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
-  class ResGraph3 {
+  class ResGraphWrapper {
   public:
     typedef typename Graph::NodeIt NodeIt;
     typedef typename Graph::EachNodeIt EachNodeIt;
-
   private:
-    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
     typedef typename Graph::OutEdgeIt OldOutEdgeIt;
     typedef typename Graph::InEdgeIt OldInEdgeIt;
-    const Graph& G;
-    FlowMap& flow;
-    const CapacityMap& capacity;
-  public:
-    ResGraph3(const Graph& _G, FlowMap& _flow, 
+    const Graph* G;
+    FlowMap* flow;
+    const CapacityMap* capacity;
+  public:
+    ResGraphWrapper(const Graph& _G, FlowMap& _flow, 
              const CapacityMap& _capacity) : 
-      G(_G), flow(_flow), capacity(_capacity) { }
-
+      G(&_G), flow(&_flow), capacity(&_capacity) { }
+//     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) : 
+//       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
     class EdgeIt; 
     class OutEdgeIt; 
@@ -270 +269 @@
 
     class EdgeIt {
-      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
+      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     protected:
       //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
@@ -279 +278 @@
       OldOutEdgeIt out;
       OldInEdgeIt in;
-      bool out_or_in; //1, iff out
-    public:
-      EdgeIt() : out_or_in(1) { } 
+      bool out_or_in; //true, iff out
+    public:
+      EdgeIt() : out_or_in(true) { } 
+      EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : 
+        G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
       //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
       Number free() const { 
@@ -318 +319 @@
     };
 
+    Number free(OldOutEdgeIt out) const { 
+      return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out)); 
+    }
+    Number free(OldInEdgeIt in) const { 
+      return (/*resG->*/flow->get(in)); 
+    }
+
     class OutEdgeIt : public EdgeIt {
-      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
+      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     public:
       OutEdgeIt() { }
     private:
-      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) { 
-        G=&_G;
-        flow=&_flow;
-        capacity=&_capacity;
+      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) { 
         //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
         G->getFirst(out, v);
-        while( out.valid() && !(free()>0) ) { ++out; }
+        while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
         if (!out.valid()) {
           out_or_in=0;
           //in=/*resG->*/G->template first<OldInEdgeIt>(v);
           G->getFirst(in, v);
-          while( in.valid() && !(free()>0) ) { ++in; }
+          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
         }
       }
@@ -342 +347 @@
           NodeIt v=/*resG->*/G->aNode(out);
           ++out;
-          while( out.valid() && !(free()>0) ) { ++out; }
+          while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
           if (!out.valid()) {
             out_or_in=0;
             G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
-            while( in.valid() && !(free()>0) ) { ++in; }
+            while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
           }
         } else {
           ++in;
-          while( in.valid() && !(free()>0) ) { ++in; } 
+          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 
         }
         return *this; 
@@ -357 +362 @@
 
     class EachEdgeIt : public EdgeIt {
+      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
       typename Graph::EachNodeIt v;
     public:
       EachEdgeIt() { }
       //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
-      EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) { 
-        G=&_G;
-        flow=&_flow;
-        capacity=&_capacity;
-        out_or_in=1;
+      EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) { 
+        out_or_in=true;
         G->getFirst(v);
         if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
-        while (out.valid() && !(free()>0) ) { ++out; }
+        while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
         while (v.valid() && !out.valid()) { 
           ++v; 
           if (v.valid()) G->getFirst(out, v); 
-          while (out.valid() && !(free()>0) ) { ++out; }
+          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
         }
         if (!out.valid()) {
@@ -378 +381 @@
           G->getFirst(v);
           if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
-          while (in.valid() && !(free()>0) ) { ++in; }
+          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
           while (v.valid() && !in.valid()) { 
             ++v; 
             if (v.valid()) G->getFirst(in, v); 
-            while (in.valid() && !(free()>0) ) { ++in; }
+            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
           }
         }
@@ -389 +392 @@
         if (out_or_in) {
           ++out;
-          while (out.valid() && !(free()>0) ) { ++out; }
+          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
           while (v.valid() && !out.valid()) { 
             ++v; 
             if (v.valid()) G->getFirst(out, v); 
-            while (out.valid() && !(free()>0) ) { ++out; }
+            while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
           }
           if (!out.valid()) {
@@ -399 +402 @@
             G->getFirst(v);
             if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
-            while (in.valid() && !(free()>0) ) { ++in; }
+            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
             while (v.valid() && !in.valid()) { 
               ++v; 
               if (v.valid()) G->getFirst(in, v); 
-              while (in.valid() && !(free()>0) ) { ++in; }
+              while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
             }  
           }
         } else {
           ++in;
-          while (in.valid() && !(free()>0) ) { ++in; }
+          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
           while (v.valid() && !in.valid()) { 
             ++v; 
             if (v.valid()) G->getFirst(in, v); 
-            while (in.valid() && !(free()>0) ) { ++in; }
+            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
           }
         }
@@ -419 +422 @@
     };
 
+    void getFirst(EachNodeIt& v) const { G->getFirst(v); }
     void getFirst(OutEdgeIt& e, NodeIt v) const { 
-      e=OutEdgeIt(G, v, flow, capacity); 
+      e=OutEdgeIt(*G, v, *flow, *capacity); 
     }
     void getFirst(EachEdgeIt& e) const { 
-      e=EachEdgeIt(G, flow, capacity); 
-    }
-    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
+      e=EachEdgeIt(*G, *flow, *capacity); 
+    }
+   
+    EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
+
+    OutEdgeIt& next(OutEdgeIt& e) const { 
+      if (e.out_or_in) {
+        NodeIt v=G->aNode(e.out);
+        ++(e.out);
+        while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
+        if (!G->valid(e.out)) {
+          e.out_or_in=0;
+          G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
+          while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+        }
+      } else {
+        ++(e.in);
+        while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); } 
+      }
+      return e;
+    }
+
+    EachEdgeIt& next(EachEdgeIt& e) const { 
+      if (e.out_or_in) {
+        ++(e.out);
+        while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
+          while (G->valid(e.v) && !G->valid(e.out)) { 
+            ++(e.v); 
+            if (G->valid(e.v)) G->getFirst(e.out, e.v); 
+            while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
+          }
+          if (!G->valid(e.out)) {
+            e.out_or_in=0;
+            G->getFirst(e.v);
+            if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
+            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+            while (G->valid(e.v) && !G->valid(e.in)) { 
+              ++(e.v); 
+              if (G->valid(e.v)) G->getFirst(e.in, e.v); 
+              while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+            }  
+          }
+        } else {
+          ++(e.in);
+          while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+          while (G->valid(e.v) && !G->valid(e.in)) { 
+            ++(e.v); 
+            if (G->valid(e.v)) G->getFirst(e.in, e.v); 
+            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
+          }
+        }
+        return e;
+      }
     
+
     template< typename It >
     It first() const { 
@@ -442 +497 @@
 
     NodeIt tail(EdgeIt e) const { 
-      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
+      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
     NodeIt head(EdgeIt e) const { 
-      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
+      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
 
     NodeIt aNode(OutEdgeIt e) const { 
-      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
+      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
     NodeIt bNode(OutEdgeIt e) const { 
-      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
-
-    int id(NodeIt v) const { return G.id(v); }
+      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
+
+    int id(NodeIt v) const { return G->id(v); }
+
+    bool valid(NodeIt n) const { return G->valid(n); }
+    bool valid(EdgeIt e) const { 
+      return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
 
     template <typename T>
@@ -457 +516 @@
       typename Graph::NodeMap<T> node_map; 
     public:
-      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
-      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(_G.G, a) { }
+      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
+      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
       void set(NodeIt nit, T a) { node_map.set(nit, a); }
       T get(NodeIt nit) const { return node_map.get(nit); }
@@ -467 +526 @@
       typename Graph::EdgeMap<T> forward_map, backward_map; 
     public:
-      EdgeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.G), backward_map(_G.G) { }
-      EdgeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.G, a), backward_map(_G.G, a) { }
+      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }
+      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }
       void set(EdgeIt e, T a) { 
         if (e.out_or_in) 
@@ -495 +554 @@
 
   private:
-    const Graph& G;
+    const Graph* G;
     NodeIt s;
     NodeIt t;
-    FlowMap& flow;
-    const CapacityMap& capacity;
-    typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
+    FlowMap* flow;
+    const CapacityMap* capacity;
+    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
     typedef typename AugGraph::EdgeIt AugEdgeIt;
@@ -510 +569 @@
   public:
     MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : 
-      G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //,  
+      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //,  
       //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) 
       { }
     bool augmentOnShortestPath() {
-      AugGraph res_graph(G, flow, capacity);
+      AugGraph res_graph(*G, *flow, *capacity);
       bool _augment=false;
       
       typedef typename AugGraph::NodeMap<bool> ReachedMap;
-      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
+      BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
       res_bfs.pushAndSetReached(s);
         
@@ -530 +589 @@
       while ( !res_bfs.finished() ) { 
         AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
-        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
+        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
           NodeIt v=res_graph.tail(e);
           NodeIt w=res_graph.head(e);
           pred.set(w, e);
-          if (pred.get(v).valid()) {
+          if (res_graph.valid(pred.get(v))) {
             free.set(w, std::min(free.get(v), e.free()));
           } else {
@@ -548 +607 @@
         NodeIt n=t;
         Number augment_value=free.get(t);
-        while (pred.get(n).valid()) { 
+        while (res_graph.valid(pred.get(n))) { 
           AugEdgeIt e=pred.get(n);
           e.augment(augment_value); 
@@ -561 +620 @@
       bool _augment=false;
 
-      AugGraph res_graph(G, flow, capacity);
+      AugGraph res_graph(*G, *flow, *capacity);
 
       typedef typename AugGraph::NodeMap<bool> ReachedMap;
@@ -570 +629 @@
       while ( !bfs.finished() ) { 
         AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
-        if (e.valid() && bfs.isBNodeNewlyReached()) {
+        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
           dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
         }
@@ -579 +638 @@
       MutableGraph F;
       typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
-      for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++n) {
+      for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
         res_graph_to_F.set(n, F.addNode());
       }
@@ -587 +646 @@
 
       typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
-      typename MutableGraph::EdgeMap<Number> free_on_edge(F);
+      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
 
       //Making F to the graph containing the edges of the residual graph 
       //which are in some shortest paths
-      for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++e) {
+      for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
         if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
           typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
           original_edge.update();
           original_edge.set(f, e);
-          free_on_edge.update();
-          free_on_edge.set(f, e.free());
+          residual_capacity.update();
+          residual_capacity.set(f, e.free());
         } 
       }
@@ -614 +673 @@
         while (!dfs.finished()) {
           ++dfs;
-          if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
+          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
             //std::cout << "OutEdgeIt: " << dfs; 
             //std::cout << " aNode: " << F.aNode(dfs); 
@@ -622 +681 @@
             typename MutableGraph::NodeIt w=F.bNode(dfs);
             pred.set(w, dfs);
-            if (pred.get(v).valid()) {
-              free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));
+            if (F.valid(pred.get(v))) {
+              free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
             } else {
-              free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/); 
+              free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/); 
             }
             if (w==tF) { 
@@ -658 +717 @@
           typename MutableGraph::NodeIt n=tF;
           Number augment_value=free.get(tF);
-          while (pred.get(n).valid()) { 
+          while (F.valid(pred.get(n))) { 
             typename MutableGraph::EdgeIt e=pred.get(n);
             original_edge.get(e).augment(augment_value); 
             n=F.tail(e);
-            if (free_on_edge.get(e)==augment_value) 
+            if (residual_capacity.get(e)==augment_value) 
               F.erase(e); 
             else 
-              free_on_edge.set(e, free_on_edge.get(e)-augment_value);
+              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
           }
         }
@@ -691 +750 @@
     Number flowValue() { 
       Number a=0;
-      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
-        a+=flow.get(i);
+      OutEdgeIt e;
+      for(G->getFirst(e, s); G->valid(e); G->next(e)) {
+        a+=flow->get(e);
       }
       return a;
     }
   };
-
-
-/*
-  template <typename Graph>
-  class IteratorBoolNodeMap {
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EachNodeIt EachNodeIt;
-    class BoolItem {
-    public:
-      bool value;
-      NodeIt prev;
-      NodeIt next;
-      BoolItem() : value(false), prev(), next() {}
-    };
-    NodeIt first_true;
-    //NodeIt last_true;
-    NodeIt first_false;
-    //NodeIt last_false;
-    const Graph& G; 
-    typename Graph::NodeMap<BoolItem> container;
-  public:
-    typedef bool ValueType;
-    typedef NodeIt KeyType;
-    IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) { 
-      //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
-      //BoolItem b=container.get(e);
-      //b.me=e;
-      //container.set(b);
-      //} 
-      G.getFirst(first_false);
-      NodeIt e_prev;
-      for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
-        container[e].prev=e_prev;
-        if (e_prev.valid()) container[e_prev].next=e;
-        e_prev=e;
-      }
-    }
-    //NodeMap(const Graph& _G, T a) : 
-    //  G(_G), container(G.node_id, a) { }
-    //FIXME
-    void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
-    T get(NodeIt nit) const { return container[G.id(nit)]; }
-    //void update() { container.resize(G.node_id); }
-    //void update(T a) { container.resize(G.node_id, a); }
-  };
-*/