# HG changeset patch
# User marci
# Date 1078429087 0
# Node ID 8c6292ec54c6de0aea593aa6a8fc617ae446b202
# Parent  eb8dcb4ab78d8cc49f9f24fd6b9204f79962d823
graph wrappers

diff -r eb8dcb4ab78d -r 8c6292ec54c6 src/work/edmonds_karp.hh
--- a/src/work/edmonds_karp.hh	Thu Mar 04 15:13:43 2004 +0000
+++ b/src/work/edmonds_karp.hh	Thu Mar 04 19:38:07 2004 +0000
@@ -245,303 +245,6 @@
     };
   };
 
-  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
-  class ResGraphWrapper {
-  public:
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EachNodeIt EachNodeIt;
-  private:
-    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
-    typedef typename Graph::InEdgeIt OldInEdgeIt;
-    const Graph* G;
-    FlowMap* flow;
-    const CapacityMap* capacity;
-  public:
-    ResGraphWrapper(const Graph& _G, FlowMap& _flow, 
-	     const CapacityMap& _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; 
-    friend class EdgeIt; 
-    friend class OutEdgeIt; 
-
-    class EdgeIt {
-      friend class ResGraphWrapper<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; //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 { 
-	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);
-	}
-      }
-      void print() { 
-	if (out_or_in) {
-	  std::cout << "out "; 
-	  if (out.valid()) 
-	    std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out)); 
-	  else 
-	    std::cout << "invalid"; 
-	}
-	else {
-	  std::cout << "in "; 
-	  if (in.valid()) 
-	    std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in)); 
-	  else 
-	    std::cout << "invalid"; 
-	}
-	std::cout << std::endl;
-      }
-    };
-
-    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 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
-    public:
-      OutEdgeIt() { }
-    private:
-      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() && !(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() && !(EdgeIt::free()>0) ) { ++in; }
-	}
-      }
-    public:
-      OutEdgeIt& operator++() { 
-	if (out_or_in) {
-	  NodeIt v=/*resG->*/G->aNode(out);
-	  ++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() && !(EdgeIt::free()>0) ) { ++in; }
-	  }
-	} else {
-	  ++in;
-	  while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 
-	}
-	return *this; 
-      }
-    };
-
-    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) : EdgeIt(_G, _flow, _capacity) { 
-	out_or_in=true;
-	G->getFirst(v);
-	if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
-	while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
-	while (v.valid() && !out.valid()) { 
-	  ++v; 
-	  if (v.valid()) G->getFirst(out, v); 
-	  while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
-	}
-	if (!out.valid()) {
-	  out_or_in=0;
-	  G->getFirst(v);
-	  if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
-	  while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
-	  while (v.valid() && !in.valid()) { 
-	    ++v; 
-	    if (v.valid()) G->getFirst(in, v); 
-	    while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
-	  }
-	}
-      }
-      EachEdgeIt& operator++() { 
-	if (out_or_in) {
-	  ++out;
-	  while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
-	  while (v.valid() && !out.valid()) { 
-	    ++v; 
-	    if (v.valid()) G->getFirst(out, v); 
-	    while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
-	  }
-	  if (!out.valid()) {
-	    out_or_in=0;
-	    G->getFirst(v);
-	    if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
-	    while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
-	    while (v.valid() && !in.valid()) { 
-	      ++v; 
-	      if (v.valid()) G->getFirst(in, v); 
-	      while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
-	    }  
-	  }
-	} else {
-	  ++in;
-	  while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
-	  while (v.valid() && !in.valid()) { 
-	    ++v; 
-	    if (v.valid()) G->getFirst(in, v); 
-	    while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
-	  }
-	}
-	return *this;
-      }
-    };
-
-    void getFirst(EachNodeIt& v) const { G->getFirst(v); }
-    void getFirst(OutEdgeIt& e, NodeIt v) const { 
-      e=OutEdgeIt(*G, v, *flow, *capacity); 
-    }
-    void getFirst(EachEdgeIt& e) const { 
-      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 { 
-      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); }
-
-    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>
-    class NodeMap {
-      typename Graph::NodeMap<T> node_map; 
-    public:
-      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); }
-    };
-
-    template <typename T>
-    class EdgeMap {
-      typename Graph::EdgeMap<T> forward_map, backward_map; 
-    public:
-      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) 
-	  forward_map.set(e.out, a); 
-	else 
-	  backward_map.set(e.in, a); 
-      }
-      T get(EdgeIt e) { 
-	if (e.out_or_in) 
-	  return forward_map.get(e.out); 
-	else 
-	  return backward_map.get(e.in); 
-      }
-    };
-
-  };
 
   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
   class MaxFlow {
@@ -758,105 +461,105 @@
   };
 
   
-  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
-  class MaxFlow2 {
-  public:
-    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;
-  private:
-    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;
+//   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+//   class MaxFlow2 {
+//   public:
+//     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;
+//   private:
+//     const Graph& G;
+//     std::list<NodeIt>& S;
+//     std::list<NodeIt>& T;
+//     FlowMap& flow;
+//     const CapacityMap& capacity;
+//     typedef ResGraphWrapper<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);
+//       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<AugEdgeIt> pred(res_graph); 
+//       //filled up with invalid iterators
       
-      typename AugGraph::NodeMap<Number> free(res_graph);
+//       typename AugGraph::NodeMap<Number> 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; 
-	  }
-	}
+//       //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
+// 	++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);
-	}
-      }
+//       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;
-    }
-  };
+//       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;
+//     }
+//   };
 
 
 
diff -r eb8dcb4ab78d -r 8c6292ec54c6 src/work/makefile
--- a/src/work/makefile	Thu Mar 04 15:13:43 2004 +0000
+++ b/src/work/makefile	Thu Mar 04 19:38:07 2004 +0000
@@ -1,7 +1,7 @@
 INCLUDEDIRS ?= -I../include -I. -I./{marci,jacint,alpar,klao,akos}
 CXXFLAGS = -g -O -Wall $(INCLUDEDIRS) -ansi -pedantic
 
-BINARIES ?= bin_heap_demo marci_graph_demo iterator_bfs_dfs_demo graphdemo bfsdemo bfsdemo2
+BINARIES ?= bin_heap_demo marci_graph_demo iterator_bfs_dfs_demo
 
 # Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam
 # ismert rendszeren :-)  (Misi)
diff -r eb8dcb4ab78d -r 8c6292ec54c6 src/work/marci/edmonds_karp_demo.cc
--- a/src/work/marci/edmonds_karp_demo.cc	Thu Mar 04 15:13:43 2004 +0000
+++ b/src/work/marci/edmonds_karp_demo.cc	Thu Mar 04 19:38:07 2004 +0000
@@ -5,6 +5,7 @@
 #include <dimacs.hh>
 #include <edmonds_karp.hh>
 #include <time_measure.h>
+#include <graph_wrapper.h>
 
 using namespace hugo;
 
@@ -57,6 +58,24 @@
   NodeIt s, t;
   ListGraph::EdgeMap<int> cap(G);
   readDimacsMaxFlow(std::cin, G, s, t, cap);
+/*
+  typedef TrivGraphWrapper<ListGraph> TGW;
+  TGW gw(G);
+  TGW::EachNodeIt sw;
+  gw.getFirst(sw);
+  std::cout << "p1:" << gw.nodeNum() << std::endl;
+  gw.erase(sw);
+  std::cout << "p2:" << gw.nodeNum() << std::endl;
+
+  typedef const ListGraph cLG;
+  typedef TrivGraphWrapper<const cLG> CTGW;
+  CTGW cgw(G);
+  CTGW::EachNodeIt csw;
+  cgw.getFirst(csw);
+  std::cout << "p1:" << cgw.nodeNum() << std::endl;
+  //cgw.erase(csw);
+  std::cout << "p2:" << cgw.nodeNum() << std::endl;
+*/
 
   {
   std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
diff -r eb8dcb4ab78d -r 8c6292ec54c6 src/work/marci/graph_wrapper.h
--- a/src/work/marci/graph_wrapper.h	Thu Mar 04 15:13:43 2004 +0000
+++ b/src/work/marci/graph_wrapper.h	Thu Mar 04 19:38:07 2004 +0000
@@ -12,44 +12,45 @@
     typedef Graph BaseGraph;
 
     typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-  
     typedef typename Graph::EachNodeIt EachNodeIt;
 
+    typedef typename Graph::EdgeIt EdgeIt;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
     typedef typename Graph::InEdgeIt InEdgeIt;
-    typedef typename Graph::SymEdgeIt SymEdgeIt;
+    //typedef typename Graph::SymEdgeIt SymEdgeIt;
     typedef typename Graph::EachEdgeIt EachEdgeIt;
-
-    int nodeNum() const { return graph->nodeNum(); }
-    int edgeNum() const { return graph->edgeNum(); }
     
     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
     template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
       return graph->getFirst(i, p); }
-    //template<typename I> I next(const I i); { return graph->goNext(i); }
-    //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
+    
+    template<typename I> I getNext(const I& i) const { 
+      return graph->getNext(i); }
+    template<typename I> I& next(I &i) const { return graph->next(i); }    
 
     template< typename It > It first() const { 
       It e; getFirst(e); return e; }
 
-    template< typename It > It first(NodeIt v) const { 
+    template< typename It > It first(const NodeIt& v) const { 
       It e; getFirst(e, v); return e; }
 
     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
+
+    template<typename I> bool valid(const I& i) const 
+      { return graph->valid(i); }
+  
+    //template<typename I> void setInvalid(const I &i);
+    //{ return graph->setInvalid(i); }
+
+    int nodeNum() const { return graph->nodeNum(); }
+    int edgeNum() const { return graph->edgeNum(); }
   
     template<typename I> NodeIt aNode(const I& e) const { 
       return graph->aNode(e); }
     template<typename I> NodeIt bNode(const I& e) const { 
       return graph->bNode(e); }
   
-    //template<typename I> bool valid(const I& i) 
-    //{ return graph->valid(i); }
-  
-    //template<typename I> void setInvalid(const I &i);
-    //{ return graph->setInvalid(i); }
-  
     NodeIt addNode() const { return graph->addNode(); }
     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
       return graph->addEdge(tail, head); }
@@ -57,91 +58,30 @@
     template<typename I> void erase(const I& i) const { graph->erase(i); }
   
     void clear() const { graph->clear(); }
-  
+    
     template<typename T> class NodeMap : public Graph::NodeMap<T> { 
     public:
-      NodeMap(const Graph& _G) : Graph::NodeMap<T>(_G) { }
-      NodeMap(const Graph& _G, T a) : Graph::NodeMap<T>(_G, a) { }
+      NodeMap(const TrivGraphWrapper<Graph>& _G) : 
+	Graph::NodeMap<T>(*(_G.G)) { }
+      NodeMap(const TrivGraphWrapper<Graph>& _G, T a) : 
+	Graph::NodeMap<T>(*(_G.G), a) { }
     };
-    template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
-  
+    template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 
+    public:
+      EdgeMap(const TrivGraphWrapper<Graph>& _G) : 
+	Graph::EdgeMap<T>(*(_G.G)) { }
+      EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) : 
+	Graph::EdgeMap<T>(*(_G.G), a) { }
+    };
+    
     void setGraph(Graph& _graph) { graph = &_graph; }
-    Graph& getGraph() { return (*graph); }
+    Graph& getGraph() const { return (*graph); }
   
     //TrivGraphWrapper() : graph(0) { }
     TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
   };
 
   template<typename Graph>
-  class ConstTrivGraphWrapper {
-    const Graph* graph;
-  
-  public:
-    typedef Graph BaseGraph;
-
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-  
-    typedef typename Graph::EachNodeIt EachNodeIt;
-
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
-    typedef typename Graph::InEdgeIt InEdgeIt;
-    typedef typename Graph::SymEdgeIt SymEdgeIt;
-    typedef typename Graph::EachEdgeIt EachEdgeIt;
-
-    int nodeNum() const { return graph->nodeNum(); }
-    int edgeNum() const { return graph->edgeNum(); }
-    
-    template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
-    template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
-      return graph->getFirst(i, p); }
-    //template<typename I> I next(const I i); { return graph->goNext(i); }
-    //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
-
-    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 head(const EdgeIt& e) const { return graph->head(e); }
-    NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
-  
-    template<typename I> NodeIt aNode(const I& e) const { 
-      return graph->aNode(e); }
-    template<typename I> NodeIt bNode(const I& e) const { 
-      return graph->bNode(e); }
-  
-    //template<typename I> bool valid(const I& i) 
-    //{ return graph->valid(i); }
-  
-    //template<typename I> void setInvalid(const I &i);
-    //{ return graph->setInvalid(i); }
-  
-    NodeIt addNode() const { return graph->addNode(); }
-    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
-      return graph->addEdge(tail, head); }
-  
-    template<typename I> void erase(const I& i) const { graph->erase(i); }
-  
-    void clear() const { graph->clear(); }
-  
-    template<typename T> class NodeMap : public Graph::NodeMap<T> { 
-    public:
-      NodeMap(const Graph& _G) : Graph::NodeMap<T>(_G) { }
-      NodeMap(const Graph& _G, T a) : Graph::NodeMap<T>(_G, a) { }
-    };
-    template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
-  
-    void setGraph(const Graph& _graph) { graph = &_graph; }
-    const Graph& getGraph() { return (*graph); }
-  
-    //ConstTrivGraphWrapper() : graph(0) { }
-    ConstTrivGraphWrapper(const Graph& _graph) : graph(&_graph) { }
-  };
-
-
-  template<typename Graph>
   class RevGraphWrapper
   {
     Graph* graph;
@@ -149,129 +89,451 @@
   public:
     typedef Graph BaseGraph;
 
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-  
+    typedef typename Graph::NodeIt NodeIt;    
     typedef typename Graph::EachNodeIt EachNodeIt;
   
+    typedef typename Graph::EdgeIt EdgeIt;
     typedef typename Graph::OutEdgeIt InEdgeIt;
     typedef typename Graph::InEdgeIt OutEdgeIt;
-    typedef typename Graph::SymEdgeIt SymEdgeIt;
+    //typedef typename Graph::SymEdgeIt SymEdgeIt;
     typedef typename Graph::EachEdgeIt EachEdgeIt;
-
-    int nodeNum() const { return graph->nodeNum(); }
-    int edgeNum() const { return graph->edgeNum(); }
     
     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
     template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
       return graph->getFirst(i, p); }
-    //template<typename I> I next(const I i); { return graph->goNext(i); }
-    //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
+
+    template<typename I> I getNext(const I& i) const { 
+      return graph->getNext(i); }
+    template<typename I> I& next(I &i) const { return graph->next(i); }    
 
     template< typename It > It first() const { 
       It e; getFirst(e); return e; }
 
-    template< typename It > It first(NodeIt v) const { 
+    template< typename It > It first(const NodeIt& v) const { 
       It e; getFirst(e, v); return e; }
 
     NodeIt head(const EdgeIt& e) const { return graph->tail(e); }
     NodeIt tail(const EdgeIt& e) const { return graph->head(e); }
   
+    template<typename I> bool valid(const I& i) const 
+      { return graph->valid(i); }
+  
+    //template<typename I> void setInvalid(const I &i);
+    //{ return graph->setInvalid(i); }
+  
     template<typename I> NodeIt aNode(const I& e) const { 
       return graph->aNode(e); }
     template<typename I> NodeIt bNode(const I& e) const { 
       return graph->bNode(e); }
-  
-    //template<typename I> bool valid(const I i);
-    //{ return graph->valid(i); }
-  
-    //template<typename I> void setInvalid(const I &i);
-    //{ return graph->setInvalid(i); }
-  
-    NodeIt addNode() { return graph->addNode(); }
-    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { 
+
+    NodeIt addNode() const { return graph->addNode(); }
+    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
       return graph->addEdge(tail, head); }
   
-    template<typename I> void erase(const I& i) { graph->erase(i); }
+    int nodeNum() const { return graph->nodeNum(); }
+    int edgeNum() const { return graph->edgeNum(); }
   
-    void clear() { graph->clear(); }
+    template<typename I> void erase(const I& i) const { graph->erase(i); }
   
-    template<typename T> class NodeMap : public Graph::NodeMap<T> { };
-    template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
-  
+    void clear() const { graph->clear(); }
+
+    template<typename T> class NodeMap : public Graph::NodeMap<T> { 
+    public:
+      NodeMap(const RevGraphWrapper<Graph>& _G) : 
+	Graph::NodeMap<T>(*(_G.G)) { }
+      NodeMap(const RevGraphWrapper<Graph>& _G, T a) : 
+	Graph::NodeMap<T>(*(_G.G), a) { }
+    };
+    template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 
+    public:
+      EdgeMap(const RevGraphWrapper<Graph>& _G) : 
+	Graph::EdgeMap<T>(*(_G.G)) { }
+      EdgeMap(const RevGraphWrapper<Graph>& _G, T a) : 
+	Graph::EdgeMap<T>(*(_G.G), a) { }
+    };
+
     void setGraph(Graph& _graph) { graph = &_graph; }
-    Graph& getGraph() { return (*graph); }
+    Graph& getGraph() const { return (*graph); }
 
     //RevGraphWrapper() : graph(0) { }
     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
   };
 
-  template<typename Graph>
-  class SymGraphWrapper
-  {
-    Graph* graph;
+
+//   template<typename Graph>
+//   class SymGraphWrapper
+//   {
+//     Graph* graph;
   
+//   public:
+//     typedef Graph BaseGraph;
+
+//     typedef typename Graph::NodeIt NodeIt;
+//     typedef typename Graph::EdgeIt EdgeIt;
+  
+//     typedef typename Graph::EachNodeIt EachNodeIt;
+    
+//     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
+//     //iranyitatlant, ami van
+//     //mert csak 1 dolgot lehet be typedef-elni
+//     typedef typename Graph::OutEdgeIt SymEdgeIt;
+//     //typedef typename Graph::InEdgeIt SymEdgeIt;
+//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
+//     typedef typename Graph::EachEdgeIt EachEdgeIt;
+
+//     int nodeNum() const { return graph->nodeNum(); }
+//     int edgeNum() const { return graph->edgeNum(); }
+    
+//     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
+//     template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
+//       return graph->getFirst(i, p); }
+//     //template<typename I> I next(const I i); { return graph->goNext(i); }
+//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
+
+//     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 head(const EdgeIt& e) const { return graph->head(e); }
+//     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
+  
+//     template<typename I> NodeIt aNode(const I& e) const { 
+//       return graph->aNode(e); }
+//     template<typename I> NodeIt bNode(const I& e) const { 
+//       return graph->bNode(e); }
+  
+//     //template<typename I> bool valid(const I i);
+//     //{ return graph->valid(i); }
+  
+//     //template<typename I> void setInvalid(const I &i);
+//     //{ return graph->setInvalid(i); }
+  
+//     NodeIt addNode() { return graph->addNode(); }
+//     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { 
+//       return graph->addEdge(tail, head); }
+  
+//     template<typename I> void erase(const I& i) { graph->erase(i); }
+  
+//     void clear() { graph->clear(); }
+  
+//     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
+//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
+  
+//     void setGraph(Graph& _graph) { graph = &_graph; }
+//     Graph& getGraph() { return (*graph); }
+
+//     //SymGraphWrapper() : graph(0) { }
+//     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
+//   };
+
+
+  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+  class ResGraphWrapper {
   public:
     typedef Graph BaseGraph;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::EachNodeIt EachNodeIt;
+  private:
+    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
+    typedef typename Graph::InEdgeIt OldInEdgeIt;
+    const Graph* G;
+    FlowMap* flow;
+    const CapacityMap* capacity;
+  public:
+    ResGraphWrapper(const Graph& _G, FlowMap& _flow, 
+	     const CapacityMap& _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; 
+    friend class EdgeIt; 
+    friend class OutEdgeIt; 
 
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-  
-    typedef typename Graph::EachNodeIt EachNodeIt;
+    class EdgeIt {
+      friend class ResGraphWrapper<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; //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 { 
+	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);
+	}
+      }
+      void print() { 
+	if (out_or_in) {
+	  std::cout << "out "; 
+	  if (out.valid()) 
+	    std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out)); 
+	  else 
+	    std::cout << "invalid"; 
+	}
+	else {
+	  std::cout << "in "; 
+	  if (in.valid()) 
+	    std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in)); 
+	  else 
+	    std::cout << "invalid"; 
+	}
+	std::cout << std::endl;
+      }
+    };
+
+    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 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
+    public:
+      OutEdgeIt() { }
+    private:
+      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() && !(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() && !(EdgeIt::free()>0) ) { ++in; }
+	}
+      }
+    public:
+      OutEdgeIt& operator++() { 
+	if (out_or_in) {
+	  NodeIt v=/*resG->*/G->aNode(out);
+	  ++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() && !(EdgeIt::free()>0) ) { ++in; }
+	  }
+	} else {
+	  ++in;
+	  while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 
+	}
+	return *this; 
+      }
+    };
+
+    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) : EdgeIt(_G, _flow, _capacity) { 
+	out_or_in=true;
+	G->getFirst(v);
+	if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
+	while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+	while (v.valid() && !out.valid()) { 
+	  ++v; 
+	  if (v.valid()) G->getFirst(out, v); 
+	  while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+	}
+	if (!out.valid()) {
+	  out_or_in=0;
+	  G->getFirst(v);
+	  if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
+	  while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+	  while (v.valid() && !in.valid()) { 
+	    ++v; 
+	    if (v.valid()) G->getFirst(in, v); 
+	    while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+	  }
+	}
+      }
+      EachEdgeIt& operator++() { 
+	if (out_or_in) {
+	  ++out;
+	  while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+	  while (v.valid() && !out.valid()) { 
+	    ++v; 
+	    if (v.valid()) G->getFirst(out, v); 
+	    while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
+	  }
+	  if (!out.valid()) {
+	    out_or_in=0;
+	    G->getFirst(v);
+	    if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
+	    while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+	    while (v.valid() && !in.valid()) { 
+	      ++v; 
+	      if (v.valid()) G->getFirst(in, v); 
+	      while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+	    }  
+	  }
+	} else {
+	  ++in;
+	  while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+	  while (v.valid() && !in.valid()) { 
+	    ++v; 
+	    if (v.valid()) G->getFirst(in, v); 
+	    while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
+	  }
+	}
+	return *this;
+      }
+    };
+
+    void getFirst(EachNodeIt& v) const { G->getFirst(v); }
+    void getFirst(OutEdgeIt& e, NodeIt v) const { 
+      e=OutEdgeIt(*G, v, *flow, *capacity); 
+    }
+    void getFirst(EachEdgeIt& e) const { 
+      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;
+      }
     
-    //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
-    //iranyitatlant, ami van
-    //mert csak 1 dolgot lehet be typedef-elni
-    typedef typename Graph::OutEdgeIt SymEdgeIt;
-    //typedef typename Graph::InEdgeIt SymEdgeIt;
-    //typedef typename Graph::SymEdgeIt SymEdgeIt;
-    typedef typename Graph::EachEdgeIt EachEdgeIt;
 
-    int nodeNum() const { return graph->nodeNum(); }
-    int edgeNum() const { return graph->edgeNum(); }
-    
-    template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
-    template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
-      return graph->getFirst(i, p); }
-    //template<typename I> I next(const I i); { return graph->goNext(i); }
-    //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
+    template< typename It >
+    It first() const { 
+      It e;
+      getFirst(e);
+      return e; 
+    }
 
-    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; 
+    }
 
-    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 head(const EdgeIt& e) const { return graph->head(e); }
-    NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
-  
-    template<typename I> NodeIt aNode(const I& e) const { 
-      return graph->aNode(e); }
-    template<typename I> NodeIt bNode(const I& e) const { 
-      return graph->bNode(e); }
-  
-    //template<typename I> bool valid(const I i);
-    //{ return graph->valid(i); }
-  
-    //template<typename I> void setInvalid(const I &i);
-    //{ return graph->setInvalid(i); }
-  
-    NodeIt addNode() { return graph->addNode(); }
-    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { 
-      return graph->addEdge(tail, head); }
-  
-    template<typename I> void erase(const I& i) { graph->erase(i); }
-  
-    void clear() { graph->clear(); }
-  
-    template<typename T> class NodeMap : public Graph::NodeMap<T> { };
-    template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
-  
-    void setGraph(Graph& _graph) { graph = &_graph; }
-    Graph& getGraph() { return (*graph); }
+    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)); }
 
-    //SymGraphWrapper() : graph(0) { }
-    SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
+    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> class NodeMap : public Graph::NodeMap<T> { 
+    public:
+      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) 
+	: Graph::NodeMap<T>(*(_G.G)) { }
+      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, 
+	      T a) : Graph::NodeMap<T>(*(_G.G), a) { }
+    };
+
+//     template <typename T>
+//     class NodeMap {
+//       typename Graph::NodeMap<T> node_map; 
+//     public:
+//       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); }
+//     };
+
+    template <typename T>
+    class EdgeMap {
+      typename Graph::EdgeMap<T> forward_map, backward_map; 
+    public:
+      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) 
+	  forward_map.set(e.out, a); 
+	else 
+	  backward_map.set(e.in, a); 
+      }
+      T get(EdgeIt e) { 
+	if (e.out_or_in) 
+	  return forward_map.get(e.out); 
+	else 
+	  return backward_map.get(e.in); 
+      }
+    };
+
   };
 
 
@@ -422,158 +684,6 @@
 //     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
 //   };
 
-
-// // FIXME: comparison should be made better!!!
-//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
-//   class ConstResGraphWrapper
-//   {
-//     const Graph* graph;
-//     const LowerMap* low;
-//     FlowMap* flow;
-//     const UpperMap* up;
-//   public:
-//     typedef Graph BaseGraph;
-
-//     typedef typename Graph::NodeIt NodeIt;
-//     typedef typename Graph::EdgeIt EdgeIt;
-  
-//     typedef typename Graph::EachNodeIt EachNodeIt;
-   
-//     class OutEdgeIt {
-//     public:
-//       //Graph::NodeIt n;
-//       bool out_or_in;
-//       typename Graph::SymEdgeIt sym;
-//     };
-//     class InEdgeIt {
-//     public:
-//       //Graph::NodeIt n;
-//       bool out_or_in;
-//       typename Graph::OutEdgeIt sym;
-//     };
-//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
-//     //typedef typename Graph::EachEdgeIt EachEdgeIt;
-
-//     int nodeNum() const { return graph->nodeNum(); }
-//     //int edgeNum() const { return graph->edgeNum(); }
-
-//     NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
-
-//     // EachEdge and SymEdge  is missing!!!!
-//     // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
-
-    
-//     //FIXME
-//     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const 
-//       {
-// 	e.n=n;
-// 	graph->getFirst(e.o,n);
-// 	while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
-// 	  graph->goNext(e.o);
-// 	if(!graph->valid(e.o)) {
-// 	  graph->getFirst(e.i,n);
-// 	  while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
-// 	    graph->goNext(e.i);
-// 	}
-// 	return e;
-//       }
-// /*
-//   OutEdgeIt &goNext(OutEdgeIt &e)
-//   {
-//   if(graph->valid(e.o)) {
-//   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
-//   graph->goNext(e.o);
-//   if(graph->valid(e.o)) return e;
-//   else graph->getFirst(e.i,e.n);
-//   }
-//   else {
-//   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
-//   graph->goNext(e.i);
-//   return e;
-//   }
-//   }
-//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
-// */
-//     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
-
-//     //FIXME
-//     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const 
-//       {
-// 	e.n=n;
-// 	graph->getFirst(e.i,n);
-// 	while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
-// 	  graph->goNext(e.i);
-// 	if(!graph->valid(e.i)) {
-// 	  graph->getFirst(e.o,n);
-// 	  while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
-// 	    graph->goNext(e.o);
-// 	}
-// 	return e;
-//       }
-// /*
-//   InEdgeIt &goNext(InEdgeIt &e)
-//   {
-//   if(graph->valid(e.i)) {
-//   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
-//   graph->goNext(e.i);
-//   if(graph->valid(e.i)) return e;
-//   else graph->getFirst(e.o,e.n);
-//   }
-//   else {
-//   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
-//   graph->goNext(e.o);
-//   return e;
-//   }
-//   }
-//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
-// */
-//     //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
-
-//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
-//     //template<typename I> I next(const I i); { return graph->goNext(i); }
-
-//     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 head(const EdgeIt& e) const { return graph->head(e); }
-//     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
-  
-//     template<typename I> NodeIt aNode(const I& e) const { 
-//       return graph->aNode(e); }
-//     template<typename I> NodeIt bNode(const I& e) const { 
-//       return graph->bNode(e); }
-  
-//     //template<typename I> bool valid(const I i);
-//     //{ return graph->valid(i); }
-  
-//     //template<typename I> void setInvalid(const I &i);
-//     //{ return graph->setInvalid(i); }
-  
-//     NodeIt addNode() { return graph->addNode(); }
-//     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { 
-//       return graph->addEdge(tail, head); }
-  
-//     template<typename I> void erase(const I& i) { graph->erase(i); }
-  
-//     void clear() { graph->clear(); }
-  
-//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
-//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
-  
-//     void setGraph(const Graph& _graph) { graph = &_graph; }
-//     const Graph& getGraph() { return (*graph); }
-
-//     //ConstResGraphWrapper() : graph(0) { }
-//     ConstResGraphWrapper(const Graph& _graph) : graph(&_graph) { }
-//   };
-
-
-
-
-
 } //namespace hugo
 
 #endif //GRAPH_WRAPPER_H
diff -r eb8dcb4ab78d -r 8c6292ec54c6 src/work/marci_graph_demo.cc
--- a/src/work/marci_graph_demo.cc	Thu Mar 04 15:13:43 2004 +0000
+++ b/src/work/marci_graph_demo.cc	Thu Mar 04 19:38:07 2004 +0000
@@ -245,7 +245,7 @@
     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);
@@ -263,6 +263,6 @@
     std::cout<<std::endl;
     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   }
-
+*/
   return 0;
 }