# HG changeset patch
# User marci
# Date 1076930988 0
# Node ID 87623302a68f5a1696da26ba74351a326934d154
# Parent  82d3dbe912d9336237e723ddea45e10558dee6a1
.

diff -r 82d3dbe912d9 -r 87623302a68f src/work/bfs_iterator.hh
--- a/src/work/bfs_iterator.hh	Mon Feb 16 10:57:01 2004 +0000
+++ b/src/work/bfs_iterator.hh	Mon Feb 16 11:29:48 2004 +0000
@@ -3,6 +3,8 @@
 
 #include <queue>
 #include <stack>
+#include <utility>
+#include <graph_wrapper.h>
 
 namespace marci {
 
@@ -466,6 +468,227 @@
     const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
  };
 
+
+  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
 
 #endif //BFS_ITERATOR_HH
diff -r 82d3dbe912d9 -r 87623302a68f src/work/edmonds_karp.hh
--- a/src/work/edmonds_karp.hh	Mon Feb 16 10:57:01 2004 +0000
+++ b/src/work/edmonds_karp.hh	Mon Feb 16 11:29:48 2004 +0000
@@ -2,12 +2,14 @@
 #define EDMONDS_KARP_HH
 
 #include <algorithm>
+#include <list>
+#include <iterator>
 
 #include <bfs_iterator.hh>
 
 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;
     typedef typename Graph::EachNodeIt EachNodeIt;
@@ -26,14 +28,14 @@
     friend class OutEdgeIt; 
 
     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)); 
 	} else { 
@@ -41,22 +43,24 @@
 	}
       }
       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;
 	}
       }
     };
 
     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);
 	while( sym.valid() && !(free()>0) ) { ++sym; }
@@ -76,6 +80,131 @@
     
     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; 
+      }
+    };
+
+    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; 
@@ -88,11 +217,15 @@
       return e; 
     }
 
-    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
-    NodeIt head(EdgeIt 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 G.aNode(e.sym); }
-    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
+    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); }
 
@@ -100,15 +233,146 @@
     class NodeMap {
       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 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 T, typename FlowMap, typename CapacityMap>
+
+  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
   class MaxFlow {
     typedef typename Graph::NodeIt NodeIt;
     typedef typename Graph::EdgeIt EdgeIt;
@@ -120,21 +384,30 @@
     NodeIt t;
     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);
       bool _augment=false;
       
       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);
 	
@@ -158,7 +431,7 @@
 
       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);
 	  e.augment(augment_value); 
@@ -171,8 +444,8 @@
     void run() {
       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);
       }
@@ -180,6 +453,153 @@
     }
   };
 
+
+/*
+  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
 
 #endif //EDMONDS_KARP_HH
diff -r 82d3dbe912d9 -r 87623302a68f src/work/iterator_bfs_demo.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/iterator_bfs_demo.cc	Mon Feb 16 11:29:48 2004 +0000
@@ -0,0 +1,129 @@
+#include <iostream>
+#include <vector>
+#include <string>
+
+#include <list_graph.hh>
+#include <bfs_iterator.hh>
+#include <graph_wrapper.h>
+
+using namespace marci;
+
+int main (int, char*[])
+{
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EdgeIt EdgeIt;
+  typedef ListGraph::EachNodeIt EachNodeIt;
+  typedef ListGraph::EachEdgeIt EachEdgeIt;
+  typedef ListGraph::OutEdgeIt OutEdgeIt;
+  typedef ListGraph::InEdgeIt InEdgeIt;
+  typedef ListGraph::SymEdgeIt SymEdgeIt;
+ 
+  ListGraph G;
+
+  NodeIt s=G.addNode();
+  NodeIt v1=G.addNode();
+  NodeIt v2=G.addNode();
+  NodeIt v3=G.addNode();
+  NodeIt v4=G.addNode();
+  NodeIt t=G.addNode();
+  
+  G.addEdge(s, v1);
+  G.addEdge(s, v2);
+  G.addEdge(v1, v2);
+  G.addEdge(v2, v1);
+  G.addEdge(v1, v3);
+  G.addEdge(v3, v2);
+  G.addEdge(v2, v4);
+  G.addEdge(v4, v3);
+  G.addEdge(v3, t);
+  G.addEdge(v4, t);
+
+  std::cout << "bfs and dfs demo on the directed graph" << std::endl;
+  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { 
+    std::cout << i << ": ";
+    std::cout << "out edges: ";
+    for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) 
+      std::cout << j << " ";
+    std::cout << "in edges: ";
+    for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) 
+      std::cout << j << " ";
+    std::cout << std::endl;
+  }
+  
+  {
+    std::cout << "iterator bfs demo 4 ..." << std::endl;
+    BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
+    bfs.pushAndSetReached(s);
+    while (!bfs.finished()) {
+      if (OutEdgeIt(bfs).valid()) {
+	std::cout << "OutEdgeIt: " << bfs; 
+	std::cout << " aNode: " << G.aNode(bfs); 
+	std::cout << " bNode: " << G.bNode(bfs) << " ";
+      } else { 
+	std::cout << "OutEdgeIt: " << "invalid"; 
+	std::cout << " aNode: " << bfs.aNode(); 
+	std::cout << " bNode: " << "invalid" << " ";
+      }
+      if (bfs.isBNodeNewlyReached()) { 
+	std::cout << "bNodeIsNewlyReached ";
+      } else { 
+	std::cout << "bNodeIsNotNewlyReached ";
+      } 
+      if (bfs.isANodeExamined()) { 
+	std::cout << "aNodeIsExamined ";
+      } else { 
+	std::cout << "aNodeIsNotExamined ";
+      } 
+      std::cout<<std::endl;
+      ++bfs;
+    }
+  }
+
+  typedef ConstTrivGraphWrapper<ListGraph> CTGW;
+  CTGW wG(G);
+
+  std::cout << "bfs and dfs demo on the directed graph" << std::endl;
+  for(CTGW::EachNodeIt i=wG.first<CTGW::EachNodeIt>(); i.valid(); ++i) { 
+    std::cout << i << ": ";
+    std::cout << "out edges: ";
+    for(CTGW::OutEdgeIt j=wG.first<CTGW::OutEdgeIt>(i); j.valid(); ++j) 
+      std::cout << j << " ";
+    std::cout << "in edges: ";
+    for(CTGW::InEdgeIt j=wG.first<CTGW::InEdgeIt>(i); j.valid(); ++j) 
+      std::cout << j << " ";
+    std::cout << std::endl;
+  }
+
+
+  {
+    std::cout << "iterator bfs demo 5 ..." << std::endl;
+    BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG);
+    bfs.pushAndSetReached(s);
+    while (!bfs.finished()) {
+      if (OutEdgeIt(bfs).valid()) {
+	std::cout << "OutEdgeIt: " << bfs; 
+	std::cout << " aNode: " << wG.aNode(bfs); 
+	std::cout << " bNode: " << wG.bNode(bfs) << " ";
+      } else { 
+	std::cout << "OutEdgeIt: " << "invalid"; 
+	std::cout << " aNode: " << bfs.aNode(); 
+	std::cout << " bNode: " << "invalid" << " ";
+      }
+      if (bfs.isBNodeNewlyReached()) { 
+	std::cout << "bNodeIsNewlyReached ";
+      } else { 
+	std::cout << "bNodeIsNotNewlyReached ";
+      } 
+      if (bfs.isANodeExamined()) { 
+	std::cout << "aNodeIsExamined ";
+      } else { 
+	std::cout << "aNodeIsNotExamined ";
+      } 
+      std::cout<<std::endl;
+      ++bfs;
+    }
+  }
+
+
+  return 0;
+}
diff -r 82d3dbe912d9 -r 87623302a68f src/work/list_graph.hh
--- a/src/work/list_graph.hh	Mon Feb 16 10:57:01 2004 +0000
+++ b/src/work/list_graph.hh	Mon Feb 16 11:29:48 2004 +0000
@@ -44,8 +44,10 @@
       NodeMap(const ListGraph& _G) : G(_G), container(G.node_id) { }
       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); }
     };
@@ -60,8 +62,10 @@
       EdgeMap(const ListGraph& _G) : G(_G), container(G.edge_id) { }
       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); }
     };
@@ -76,6 +80,8 @@
 
     class node_item {
       friend class ListGraph;
+      template <typename T> friend class NodeMap;
+      
       friend class NodeIt;
       friend class EachNodeIt;
       friend class EdgeIt;
@@ -99,6 +105,8 @@
 
     class edge_item {
       friend class ListGraph;
+      template <typename T> friend class EdgeMap;
+
       friend class NodeIt;
       friend class EachNodeIt;
       friend class EdgeIt;
@@ -254,11 +262,16 @@
     /* same methods in other style */
     /* 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); }
 
@@ -333,6 +346,7 @@
 
     class NodeIt {
       friend class ListGraph;
+      template <typename T> friend class NodeMap;
 
       friend class EdgeIt;
       friend class OutEdgeIt;
@@ -367,6 +381,7 @@
 
     class EdgeIt {
       friend class ListGraph;
+      template <typename T> friend class EdgeMap;
       
       friend class NodeIt;
       friend class EachNodeIt;
@@ -413,53 +428,52 @@
     
     class OutEdgeIt : public EdgeIt {
       friend class ListGraph;
-      node_item* v;
+      //node_item* v;
     protected:
-      OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
+      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->_first_out_edge; }
+      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;
+      //node_item* v;
     protected:
-      InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_in_edge; }
+      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->_first_in_edge; }
+      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); }
     };
 
     class SymEdgeIt : public EdgeIt {
       friend class ListGraph;
       bool out_or_in; //1 iff out, 0 iff in
-      node_item* v;
+      //node_item* v;
     protected:
-      SymEdgeIt(const NodeIt& _v) : v(_v.node) { 
+      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; }
 	} else {
@@ -468,9 +482,10 @@
 	return *this;
       }
     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); }
     };
 
   };
diff -r 82d3dbe912d9 -r 87623302a68f src/work/marci_graph_demo.cc
--- a/src/work/marci_graph_demo.cc	Mon Feb 16 10:57:01 2004 +0000
+++ b/src/work/marci_graph_demo.cc	Mon Feb 16 11:29:48 2004 +0000
@@ -94,7 +94,7 @@
     std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
   }
   std::cout << std::endl;
-
+/*
   std::cout << "bfs from the first node" << std::endl;
   bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
   bfs_test.run();
@@ -108,7 +108,7 @@
     std::cout << bfs_test.dist.get(i) << " ";
   }
   std::cout<<std::endl;
-
+*/
 
   std::cout << "augmenting path flow algorithm test..." << std::endl;
   ListGraph flowG;
@@ -173,7 +173,7 @@
 
   //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) << ": ";
     std::cout << "out edges: ";
@@ -188,7 +188,7 @@
   for(EachEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++e) {
     std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
   }
-
+*/
   /*
   while (flowG.first<EachEdgeIt>().valid()) {
     flowG.deleteEdge(flowG.first<EachEdgeIt>());
@@ -219,19 +219,39 @@
   }
   */
 
-  std::cout << std::endl;
-  //std::cout << "meg jo" << std::flush;
+  //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)<<") ";
+  {
+    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;
-  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;
 }