Changeset 75:87623302a68f in lemon-0.x for src/work

Timestamp:

02/16/04 12:29:48 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

.

Location:

src/work

Files:

• bfs_iterator.hh (modified) (2 diffs)
• edmonds_karp.hh (modified) (13 diffs)
• iterator_bfs_demo.cc (added)
• list_graph.hh (modified) (10 diffs)
• marci_graph_demo.cc (modified) (5 diffs)

src/work/bfs_iterator.hh

@@ -4 +4 @@
 #include <queue>
 #include <stack>
+#include <utility>
+#include <graph_wrapper.h>
 
 namespace marci {
@@ -467 +469 @@
  };
 
+
+  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
+  class BfsIterator3 {
+    typedef typename Graph::NodeIt NodeIt;
+    const Graph& G;
+    std::queue< std::pair<NodeIt, OutEdgeIt> > bfs_queue;
+    ReachedMap reached;
+    bool b_node_newly_reached;
+    OutEdgeIt actual_edge;
+  public:
+    BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
+    void pushAndSetReached(NodeIt s) { 
+      reached.set(s, true);
+      if (bfs_queue.empty()) {
+        bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
+        actual_edge=bfs_queue.front().second;
+        if (actual_edge.valid()) { 
+          NodeIt w=G.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
+            reached.set(w, true);
+            b_node_newly_reached=true;
+          } else {
+            b_node_newly_reached=false;
+          }
+        } //else {
+        //}
+      } else {
+        bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
+      }
+    }
+    BfsIterator3<Graph, OutEdgeIt, ReachedMap>& 
+    operator++() { 
+      if (bfs_queue.front().second.valid()) { 
+        ++(bfs_queue.front().second);
+        actual_edge=bfs_queue.front().second;
+        if (actual_edge.valid()) {
+          NodeIt w=G.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
+            reached.set(w, true);
+            b_node_newly_reached=true;
+          } else {
+            b_node_newly_reached=false;
+          }
+        }
+      } else {
+        bfs_queue.pop(); 
+        if (!bfs_queue.empty()) {
+          actual_edge=bfs_queue.front().second;
+          if (actual_edge.valid()) {
+            NodeIt w=G.bNode(actual_edge);
+            if (!reached.get(w)) {
+              bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
+              reached.set(w, true);
+              b_node_newly_reached=true;
+            } else {
+              b_node_newly_reached=false;
+            }
+          }
+        }
+      }
+      return *this;
+    }
+    bool finished() const { return bfs_queue.empty(); }
+    operator OutEdgeIt () const { return actual_edge; }
+    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
+    bool isANodeExamined() const { return !(actual_edge.valid()); }
+    NodeIt aNode() const { return bfs_queue.front().first; }
+    NodeIt bNode() const { return G.bNode(actual_edge); }
+    const ReachedMap& getReachedMap() const { return reached; }
+    //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
+ };
+
+  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
+  class BfsIterator4 {
+    typedef typename Graph::NodeIt NodeIt;
+    const Graph& G;
+    std::queue<NodeIt> bfs_queue;
+    ReachedMap reached;
+    bool b_node_newly_reached;
+    OutEdgeIt actual_edge;
+  public:
+    BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { }
+    void pushAndSetReached(NodeIt s) { 
+      reached.set(s, true);
+      if (bfs_queue.empty()) {
+        bfs_queue.push(s);
+        G.getFirst(actual_edge, s);
+        if (actual_edge.valid()) { 
+          NodeIt w=G.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(w);
+            reached.set(w, true);
+            b_node_newly_reached=true;
+          } else {
+            b_node_newly_reached=false;
+          }
+        } 
+      } else {
+        bfs_queue.push(s);
+      }
+    }
+    BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
+    operator++() { 
+      if (actual_edge.valid()) { 
+        ++actual_edge;
+        if (actual_edge.valid()) {
+          NodeIt w=G.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(w);
+            reached.set(w, true);
+            b_node_newly_reached=true;
+          } else {
+            b_node_newly_reached=false;
+          }
+        }
+      } else {
+        bfs_queue.pop(); 
+        if (!bfs_queue.empty()) {
+          G.getFirst(actual_edge, bfs_queue.front());
+          if (actual_edge.valid()) {
+            NodeIt w=G.bNode(actual_edge);
+            if (!reached.get(w)) {
+              bfs_queue.push(w);
+              reached.set(w, true);
+              b_node_newly_reached=true;
+            } else {
+              b_node_newly_reached=false;
+            }
+          }
+        }
+      }
+      return *this;
+    }
+    bool finished() const { return bfs_queue.empty(); }
+    operator OutEdgeIt () const { return actual_edge; }
+    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
+    bool isANodeExamined() const { return !(actual_edge.valid()); }
+    NodeIt aNode() const { return bfs_queue.front(); }
+    NodeIt bNode() const { return G.bNode(actual_edge); }
+    const ReachedMap& getReachedMap() const { return reached; }
+    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
+ };
+
+
+  template <typename GraphWrapper, typename ReachedMap>
+  class BfsIterator5 {
+    typedef typename GraphWrapper::NodeIt NodeIt;
+    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
+    GraphWrapper gw;
+    std::queue<NodeIt> bfs_queue;
+    ReachedMap reached;
+    bool b_node_newly_reached;
+    OutEdgeIt actual_edge;
+  public:
+    BfsIterator5(GraphWrapper _gw) : 
+      gw(_gw), reached(_gw.getGraph()) { }
+    void pushAndSetReached(NodeIt s) { 
+      reached.set(s, true);
+      if (bfs_queue.empty()) {
+        bfs_queue.push(s);
+        gw.getFirst(actual_edge, s);
+        if (actual_edge.valid()) { 
+          NodeIt w=gw.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(w);
+            reached.set(w, true);
+            b_node_newly_reached=true;
+          } else {
+            b_node_newly_reached=false;
+          }
+        } 
+      } else {
+        bfs_queue.push(s);
+      }
+    }
+    BfsIterator5<GraphWrapper, ReachedMap>& 
+    operator++() { 
+      if (actual_edge.valid()) { 
+        ++actual_edge;
+        if (actual_edge.valid()) {
+          NodeIt w=gw.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(w);
+            reached.set(w, true);
+            b_node_newly_reached=true;
+          } else {
+            b_node_newly_reached=false;
+          }
+        }
+      } else {
+        bfs_queue.pop(); 
+        if (!bfs_queue.empty()) {
+          gw.getFirst(actual_edge, bfs_queue.front());
+          if (actual_edge.valid()) {
+            NodeIt w=gw.bNode(actual_edge);
+            if (!reached.get(w)) {
+              bfs_queue.push(w);
+              reached.set(w, true);
+              b_node_newly_reached=true;
+            } else {
+              b_node_newly_reached=false;
+            }
+          }
+        }
+      }
+      return *this;
+    }
+    bool finished() const { return bfs_queue.empty(); }
+    operator OutEdgeIt () const { return actual_edge; }
+    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
+    bool isANodeExamined() const { return !(actual_edge.valid()); }
+    NodeIt aNode() const { return bfs_queue.front(); }
+    NodeIt bNode() const { return gw.bNode(actual_edge); }
+    const ReachedMap& getReachedMap() const { return reached; }
+    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
+ };
+
+
+
 } // namespace marci
 

src/work/edmonds_karp.hh

@@ -3 +3 @@
 
 #include <algorithm>
+#include <list>
+#include <iterator>
 
 #include <bfs_iterator.hh>
@@ -8 +10 @@
 namespace marci {
 
-  template<typename Graph, typename T, typename FlowMap, typename CapacityMap>
+  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
   class ResGraph {
     typedef typename Graph::NodeIt NodeIt;
@@ -27 +29 @@
 
     class EdgeIt {
-      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
+      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
     protected:
-      const ResGraph<Graph, T, FlowMap, CapacityMap>* resG;
+      const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
       OldSymEdgeIt sym;
     public:
       EdgeIt() { } 
       //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
-      T free() const { 
+      Number free() const { 
         if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
           return (resG->capacity.get(sym)-resG->flow.get(sym)); 
@@ -42 +44 @@
       }
       bool valid() const { return sym.valid(); }
-      void augment(T a) const {
+      void augment(Number a) const {
         if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
           resG->flow.set(sym, resG->flow.get(sym)+a);
+          //resG->flow[sym]+=a;
         } else { 
           resG->flow.set(sym, resG->flow.get(sym)-a);
+          //resG->flow[sym]-=a;
         }
       }
@@ -52 +56 @@
 
     class OutEdgeIt : public EdgeIt {
-      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
+      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
     public:
       OutEdgeIt() { }
       //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
     private:
-      OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, NodeIt v) { 
+      OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { 
         resG=&_resG;
         sym=resG->G.template first<OldSymEdgeIt>(v);
@@ -66 +70 @@
         ++sym; 
         while( sym.valid() && !(free()>0) ) { ++sym; }
+        return *this; 
+      }
+    };
+
+    void getFirst(OutEdgeIt& e, NodeIt v) const { 
+      e=OutEdgeIt(*this, v); 
+    }
+    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
+    
+    template< typename It >
+    It first() const { 
+      It e;      
+      getFirst(e);
+      return e; 
+    }
+
+    template< typename It >
+    It first(NodeIt v) const { 
+      It e;
+      getFirst(e, v);
+      return e; 
+    }
+
+    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
+    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
+
+    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
+    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
+
+    int id(NodeIt v) const { return G.id(v); }
+
+    template <typename S>
+    class NodeMap {
+      typename Graph::NodeMap<S> node_map; 
+    public:
+      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
+      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
+      void set(NodeIt nit, S a) { node_map.set(nit, a); }
+      S get(NodeIt nit) const { return node_map.get(nit); }
+      S& operator[](NodeIt nit) { return node_map[nit]; } 
+      const S& operator[](NodeIt nit) const { return node_map[nit]; } 
+    };
+
+  };
+
+
+  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+  class ResGraph2 {
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::EachNodeIt EachNodeIt;
+    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
+    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
+    typedef typename Graph::InEdgeIt OldInEdgeIt;
+    
+    const Graph& G;
+    FlowMap& flow;
+    const CapacityMap& capacity;
+  public:
+    ResGraph2(const Graph& _G, FlowMap& _flow, 
+             const CapacityMap& _capacity) : 
+      G(_G), flow(_flow), capacity(_capacity) { }
+
+    class EdgeIt; 
+    class OutEdgeIt; 
+    friend class EdgeIt; 
+    friend class OutEdgeIt; 
+
+    class EdgeIt {
+      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
+    protected:
+      const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
+      //OldSymEdgeIt sym;
+      OldOutEdgeIt out;
+      OldInEdgeIt in;
+      bool out_or_in; //1, iff out
+    public:
+      EdgeIt() : out_or_in(1) { } 
+      Number free() const { 
+        if (out_or_in) { 
+          return (resG->capacity.get(out)-resG->flow.get(out)); 
+        } else { 
+          return (resG->flow.get(in)); 
+        }
+      }
+      bool valid() const { 
+        return out_or_in && out.valid() || in.valid(); }
+      void augment(Number a) const {
+        if (out_or_in) { 
+          resG->flow.set(out, resG->flow.get(out)+a);
+        } else { 
+          resG->flow.set(in, resG->flow.get(in)-a);
+        }
+      }
+    };
+
+    class OutEdgeIt : public EdgeIt {
+      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
+    public:
+      OutEdgeIt() { }
+    private:
+      OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { 
+        resG=&_resG;
+        out=resG->G.template first<OldOutEdgeIt>(v);
+        while( out.valid() && !(free()>0) ) { ++out; }
+        if (!out.valid()) {
+          out_or_in=0;
+          in=resG->G.template first<OldInEdgeIt>(v);
+          while( in.valid() && !(free()>0) ) { ++in; }
+        }
+      }
+    public:
+      OutEdgeIt& operator++() { 
+        if (out_or_in) {
+          NodeIt v=resG->G.aNode(out);
+          ++out;
+          while( out.valid() && !(free()>0) ) { ++out; }
+          if (!out.valid()) {
+            out_or_in=0;
+            in=resG->G.template first<OldInEdgeIt>(v);
+            while( in.valid() && !(free()>0) ) { ++in; }
+          }
+        } else {
+          ++in;
+          while( in.valid() && !(free()>0) ) { ++in; } 
+        }
         return *this; 
       }
@@ -89 +218 @@
     }
 
-    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
-    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
-
-    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
-    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
+    NodeIt tail(EdgeIt e) const { 
+      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)); }
+
+    NodeIt aNode(OutEdgeIt e) const { 
+      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); }
@@ -101 +234 @@
       typename Graph::NodeMap<S> node_map; 
     public:
-      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
-      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
+      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
+      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
       void set(NodeIt nit, S a) { node_map.set(nit, a); }
       S get(NodeIt nit) const { return node_map.get(nit); }
     };
-
   };
 
-  template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
+  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+  class ResGraph3 {
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::EachNodeIt EachNodeIt;
+    //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 CapacityMap& _capacity) : 
+      G(_G), flow(_flow), capacity(_capacity) { }
+
+    class EdgeIt; 
+    class OutEdgeIt; 
+    friend class EdgeIt; 
+    friend class OutEdgeIt; 
+
+    class EdgeIt {
+      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
+    protected:
+      //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
+      const Graph* G;
+      FlowMap* flow;
+      const CapacityMap* capacity;
+      //OldSymEdgeIt sym;
+      OldOutEdgeIt out;
+      OldInEdgeIt in;
+      bool out_or_in; //1, iff out
+    public:
+      EdgeIt() : out_or_in(1) { } 
+      Number free() const { 
+        if (out_or_in) { 
+          return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out)); 
+        } else { 
+          return (/*resG->*/flow->get(in)); 
+        }
+      }
+      bool valid() const { 
+        return out_or_in && out.valid() || in.valid(); }
+      void augment(Number a) const {
+        if (out_or_in) { 
+          /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
+        } else { 
+          /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
+        }
+      }
+    };
+
+    class OutEdgeIt : public EdgeIt {
+      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
+    public:
+      OutEdgeIt() { }
+    private:
+      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) { 
+        G=&_G;
+        flow=&_flow;
+        capacity=&_capacity;
+        out=/*resG->*/G->template first<OldOutEdgeIt>(v);
+        while( out.valid() && !(free()>0) ) { ++out; }
+        if (!out.valid()) {
+          out_or_in=0;
+          in=/*resG->*/G->template first<OldInEdgeIt>(v);
+          while( in.valid() && !(free()>0) ) { ++in; }
+        }
+      }
+    public:
+      OutEdgeIt& operator++() { 
+        if (out_or_in) {
+          NodeIt v=/*resG->*/G->aNode(out);
+          ++out;
+          while( out.valid() && !(free()>0) ) { ++out; }
+          if (!out.valid()) {
+            out_or_in=0;
+            in=/*resG->*/G->template first<OldInEdgeIt>(v);
+            while( in.valid() && !(free()>0) ) { ++in; }
+          }
+        } else {
+          ++in;
+          while( in.valid() && !(free()>0) ) { ++in; } 
+        }
+        return *this; 
+      }
+    };
+
+    void getFirst(OutEdgeIt& e, NodeIt v) const { 
+      e=OutEdgeIt(G, v, flow, capacity); 
+    }
+    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
+    
+    template< typename It >
+    It first() const { 
+      It e;
+      getFirst(e);
+      return e; 
+    }
+
+    template< typename It >
+    It first(NodeIt v) const { 
+      It e;
+      getFirst(e, v);
+      return e; 
+    }
+
+    NodeIt tail(EdgeIt e) const { 
+      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)); }
+
+    NodeIt aNode(OutEdgeIt e) const { 
+      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); }
+
+    template <typename S>
+    class NodeMap {
+      typename Graph::NodeMap<S> node_map; 
+    public:
+      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
+      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
+      void set(NodeIt nit, S a) { node_map.set(nit, a); }
+      S get(NodeIt nit) const { return node_map.get(nit); }
+    };
+
+  };
+
+
+  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
   class MaxFlow {
     typedef typename Graph::NodeIt NodeIt;
@@ -121 +385 @@
     FlowMap& flow;
     const CapacityMap& capacity;
-    typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph;
+    typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
     typedef typename AugGraph::EdgeIt AugEdgeIt;
+
+    //AugGraph res_graph;    
+    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
+    //typename AugGraph::NodeMap<AugEdgeIt> pred; 
+    //typename AugGraph::NodeMap<int> free;
   public:
-    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
+    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : 
+      G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //,  
+      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) 
+      { }
     bool augment() {
       AugGraph res_graph(G, flow, capacity);
@@ -131 +403 @@
       
       typedef typename AugGraph::NodeMap<bool> ReachedMap;
-      BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
+      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
       res_bfs.pushAndSetReached(s);
         
       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
-      //filled with invalid iterators
+      //filled up with invalid iterators
+      //pred.set(s, AugEdgeIt());
       
       typename AugGraph::NodeMap<int> free(res_graph);
@@ -159 +432 @@
       if (_augment) {
         NodeIt n=t;
-        T augment_value=free.get(t);
+        Number augment_value=free.get(t);
         while (pred.get(n).valid()) { 
           AugEdgeIt e=pred.get(n);
@@ -172 +445 @@
       while (augment()) { } 
     }
-    T flowValue() { 
-      T a=0;
+    Number flowValue() { 
+      Number a=0;
       for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
         a+=flow.get(i);
@@ -181 +454 @@
   };
 
+
+/*
+  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 resize() { container.resize(G.node_id); }
+    //void resize(T a) { container.resize(G.node_id, a); }
+  };
+*/
+
+  
+  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+  class MaxFlow2 {
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::EdgeIt EdgeIt;
+    typedef typename Graph::EachEdgeIt EachEdgeIt;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    typedef typename Graph::InEdgeIt InEdgeIt;
+    const Graph& G;
+    std::list<NodeIt>& S;
+    std::list<NodeIt>& T;
+    FlowMap& flow;
+    const CapacityMap& capacity;
+    typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
+    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
+    typedef typename AugGraph::EdgeIt AugEdgeIt;
+    typename Graph::NodeMap<bool> SMap;
+    typename Graph::NodeMap<bool> TMap;
+  public:
+    MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { 
+      for(typename std::list<NodeIt>::const_iterator i=S.begin(); 
+          i!=S.end(); ++i) { 
+        SMap.set(*i, true); 
+      }
+      for (typename std::list<NodeIt>::const_iterator i=T.begin(); 
+           i!=T.end(); ++i) { 
+        TMap.set(*i, true); 
+      }
+    }
+    bool augment() {
+      AugGraph res_graph(G, flow, capacity);
+      bool _augment=false;
+      NodeIt reached_t_node;
+      
+      typedef typename AugGraph::NodeMap<bool> ReachedMap;
+      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
+      for(typename std::list<NodeIt>::const_iterator i=S.begin(); 
+          i!=S.end(); ++i) {
+        res_bfs.pushAndSetReached(*i);
+      }
+      //res_bfs.pushAndSetReached(s);
+        
+      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
+      //filled up with invalid iterators
+      
+      typename AugGraph::NodeMap<int> free(res_graph);
+        
+      //searching for augmenting path
+      while ( !res_bfs.finished() ) { 
+        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
+        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
+          NodeIt v=res_graph.tail(e);
+          NodeIt w=res_graph.head(e);
+          pred.set(w, e);
+          if (pred.get(v).valid()) {
+            free.set(w, std::min(free.get(v), e.free()));
+          } else {
+            free.set(w, e.free()); 
+          }
+          if (TMap.get(res_graph.head(e))) { 
+            _augment=true; 
+            reached_t_node=res_graph.head(e);
+            break; 
+          }
+        }
+        
+        ++res_bfs;
+      } //end of searching augmenting path
+
+      if (_augment) {
+        NodeIt n=reached_t_node;
+        Number augment_value=free.get(reached_t_node);
+        while (pred.get(n).valid()) { 
+          AugEdgeIt e=pred.get(n);
+          e.augment(augment_value); 
+          n=res_graph.tail(e);
+        }
+      }
+
+      return _augment;
+    }
+    void run() {
+      while (augment()) { } 
+    }
+    Number flowValue() { 
+      Number a=0;
+      for(typename std::list<NodeIt>::const_iterator i=S.begin(); 
+          i!=S.end(); ++i) { 
+        for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
+          a+=flow.get(e);
+        }
+        for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
+          a-=flow.get(e);
+        }
+      }
+      return a;
+    }
+  };
+
+
+
 } // namespace marci
 

src/work/list_graph.hh

@@ -45 +45 @@
       NodeMap(const ListGraph& _G, T a) : 
         G(_G), container(G.node_id, a) { }
-      void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
-      T get(NodeIt nit) const { return container[G.id(nit)]; }
+      void set(NodeIt n, T a) { container[/*G.id(n)*/n.node->id]=a; }
+      T get(NodeIt n) const { return container[/*G.id(n)*/n.node->id]; }
+      T& operator[](NodeIt n) { return container[/*G.id(n)*/n.node->id]; }
+      const T& operator[](NodeIt n) const { return container[/*G.id(n)*/n.node->id]; }
       void resize() { container.resize(G.node_id); }
       void resize(T a) { container.resize(G.node_id, a); }
@@ -61 +63 @@
       EdgeMap(const ListGraph& _G, T a) : 
         G(_G), container(G.edge_id, a) { }
-      void set(EdgeIt eit, T a) { container[G.id(eit)]=a; }
-      T get(EdgeIt eit) const { return container[G.id(eit)]; }
+      void set(EdgeIt e, T a) { container[/*G.id(e)*/e.edge->id]=a; }
+      T get(EdgeIt e) const { return container[/*G.id(e)*/e.edge->id]; }
+      T& operator[](EdgeIt e) { return container[/*G.id(e)*/e.edge->id]; } 
+      const T& operator[](EdgeIt e) const { return container[/*G.id(e)*/e.edge->id]; } 
       void resize() { container.resize(G.edge_id); }
       void resize(T a) { container.resize(G.edge_id, a); }
@@ -77 +81 @@
     class node_item {
       friend class ListGraph;
+      template <typename T> friend class NodeMap;
+      
       friend class NodeIt;
       friend class EachNodeIt;
@@ -100 +106 @@
     class edge_item {
       friend class ListGraph;
+      template <typename T> friend class EdgeMap;
+
       friend class NodeIt;
       friend class EachNodeIt;
@@ -255 +263 @@
     /* for experimental purpose */
 
-    void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); }
-    void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); }
-    void getFirst(OutEdgeIt& e, NodeIt v) const { e=OutEdgeIt(v); }
-    void getFirst(InEdgeIt& e, NodeIt v) const { e=InEdgeIt(v); }
-    void getFirst(SymEdgeIt& e, NodeIt v) const { e=SymEdgeIt(v); }
+    EachNodeIt& getFirst(EachNodeIt& v) const { 
+      v=EachNodeIt(*this); return v; }
+    EachEdgeIt& getFirst(EachEdgeIt& e) const { 
+      e=EachEdgeIt(*this); return e; }
+    OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const { 
+      e=OutEdgeIt(v); return e; }
+    InEdgeIt& getFirst(InEdgeIt& e, NodeIt v) const { 
+      e=InEdgeIt(v); return e; }
+    SymEdgeIt& getFirst(SymEdgeIt& e, NodeIt v) const { 
+      e=SymEdgeIt(v); return e; }
     //void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); }
     //void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); }
@@ -334 +347 @@
     class NodeIt {
       friend class ListGraph;
+      template <typename T> friend class NodeMap;
 
       friend class EdgeIt;
@@ -368 +382 @@
     class EdgeIt {
       friend class ListGraph;
+      template <typename T> friend class EdgeMap;
       
       friend class NodeIt;
@@ -414 +429 @@
     class OutEdgeIt : public EdgeIt {
       friend class ListGraph;
-      node_item* v;
-    protected:
-      OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
-    public:
-      OutEdgeIt() : EdgeIt(), v(0) { }
-      OutEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
+      //node_item* v;
+    protected:
+      OutEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
+    public:
+      OutEdgeIt() : EdgeIt()/*, v(0)*/ { }
+      OutEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
       OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
     protected:
-      NodeIt aNode() const { return NodeIt(v); }
-      NodeIt bNode() const { 
-        return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }
+      NodeIt aNode() const { return NodeIt(edge->_tail); }
+      NodeIt bNode() const { return NodeIt(edge->_head); }
     };
     
     class InEdgeIt : public EdgeIt {
       friend class ListGraph;
-      node_item* v;
-    protected:
-      InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_in_edge; }
-    public:
-      InEdgeIt() : EdgeIt(), v(0) { }
-      InEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
+      //node_item* v;
+    protected:
+      InEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
+    public:
+      InEdgeIt() : EdgeIt()/*, v(0)*/ { }
+      InEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
       InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
     protected:
-      NodeIt aNode() const { return NodeIt(v); }
-      NodeIt bNode() const { 
-        return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }
+      NodeIt aNode() const { return NodeIt(edge->_head); }
+      NodeIt bNode() const { return NodeIt(edge->_tail); }
     };
 
@@ -445 +458 @@
       friend class ListGraph;
       bool out_or_in; //1 iff out, 0 iff in
-      node_item* v;
-    protected:
-      SymEdgeIt(const NodeIt& _v) : v(_v.node) { 
+      //node_item* v;
+    protected:
+      SymEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ { 
         out_or_in=1;
-        edge=v->_first_out_edge; 
-        if (!edge) { edge=v->_first_in_edge; out_or_in=0; }
+        edge=_v.node->_first_out_edge; 
+        if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
       }
     public:
-      SymEdgeIt() : EdgeIt(), v(0) { }
-      SymEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { 
+      SymEdgeIt() : EdgeIt() /*, v(0)*/ { }
+      SymEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ { 
         out_or_in=1;
-        edge=v->_first_out_edge; 
-        if (!edge) { edge=v->_first_in_edge; out_or_in=0; }
+        edge=_v.node->_first_out_edge; 
+        if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
       }
       SymEdgeIt& operator++() { 
         if (out_or_in) { 
+          node_item* v=edge->_tail;
           edge=edge->_next_out; 
           if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
@@ -469 +483 @@
       }
     protected:
-      NodeIt aNode() const { return NodeIt(v); }
+      NodeIt aNode() const { 
+        return (out_or_in) ? NodeIt(edge->_tail) : NodeIt(edge->_head); }
       NodeIt bNode() const { 
-        return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }
+        return (out_or_in) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }
     };
 

src/work/marci_graph_demo.cc

@@ -95 +95 @@
   }
   std::cout << std::endl;
-
+/*
   std::cout << "bfs from the first node" << std::endl;
   bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
@@ -109 +109 @@
   }
   std::cout<<std::endl;
-
+*/
 
   std::cout << "augmenting path flow algorithm test..." << std::endl;
@@ -174 +174 @@
   //flowG.setTail(v3_t, v2);
   //flowG.setHead(v3_t, s);
-
+/*
   for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) { 
     std::cout << node_name.get(i) << ": ";
@@ -189 +189 @@
     std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
   }
-
+*/
   /*
   while (flowG.first<EachEdgeIt>().valid()) {
@@ -220 +220 @@
   */
 
-  std::cout << std::endl;
-  //std::cout << "meg jo" << std::flush;
-
-  ListGraph::EdgeMap<int> flow(flowG, 0);
-  MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
-  max_flow_test.run();
-
-  std::cout << "maximum flow: "<< std::endl;
-  for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
-    std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
-  }
-  std::cout<<std::endl;
-  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+  //std::cout << std::endl;
+
+
+  {
+    ListGraph::EdgeMap<int> flow(flowG, 0);
+    MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
+    max_flow_test.run();
+    
+    std::cout << "maximum flow: "<< std::endl;
+    for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
+      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
+    }
+    std::cout<<std::endl;
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+  }
+
+  {
+    std::list<NodeIt> S;
+    S.push_back(s); S.push_back(v3);
+    std::list<NodeIt> T;
+    T.push_back(t);
+
+    ListGraph::EdgeMap<int> flow(flowG, 0);
+    MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap);
+    max_flow_test.run();
+    
+    std::cout << "maximum flow: "<< std::endl;
+    for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) { 
+      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
+    }
+    std::cout<<std::endl;
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+  }
 
   return 0;