# HG changeset patch
# User marci
# Date 1080630464 0
# Node ID f24f276e0b6ba39741875b691adff9e6491a99cb
# Parent  60de0f16a4a1eabeda66f8817b43e2dbecc2c599
ResGraphWrapper ...

diff -r 60de0f16a4a1 -r f24f276e0b6b src/work/edmonds_karp.h
--- a/src/work/edmonds_karp.h	Mon Mar 29 21:43:27 2004 +0000
+++ b/src/work/edmonds_karp.h	Tue Mar 30 07:07:44 2004 +0000
@@ -313,26 +313,174 @@
       return _augment;
     }
 
+//     template<typename MutableGraph> bool augmentOnBlockingFlow() {      
+//       bool _augment=false;
+
+//       AugGraph res_graph(*G, *flow, *capacity);
+
+//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
+//       BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
+
+//       bfs.pushAndSetReached(s);
+//       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
+//       while ( !bfs.finished() ) { 
+// 	AugOutEdgeIt e=bfs;
+// 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
+// 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+// 	}
+	
+// 	++bfs;
+//       } //computing distances from s in the residual graph
+
+//       MutableGraph F;
+//       typename AugGraph::NodeMap<typename MutableGraph::Node> 
+// 	res_graph_to_F(res_graph);
+//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
+// 	res_graph_to_F.set(n, F.addNode());
+//       }
+      
+//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
+//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
+
+//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
+//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
+
+//       //Making F to the graph containing the edges of the residual graph 
+//       //which are in some shortest paths
+//       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
+// 	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
+// 	  typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+// 	  original_edge.update();
+// 	  original_edge.set(f, e);
+// 	  residual_capacity.update();
+// 	  residual_capacity.set(f, res_graph.free(e));
+// 	} 
+//       }
+
+//       bool __augment=true;
+
+//       while (__augment) {
+// 	__augment=false;
+// 	//computing blocking flow with dfs
+// 	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
+// 	DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
+// 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
+// 	pred.set(sF, typename MutableGraph::Edge(INVALID));
+// 	//invalid iterators for sources
+
+// 	typename MutableGraph::NodeMap<Number> free(F);
+
+// 	dfs.pushAndSetReached(sF);      
+// 	while (!dfs.finished()) {
+// 	  ++dfs;
+// 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
+// 	    if (dfs.isBNodeNewlyReached()) {
+// 	      typename MutableGraph::Node v=F.aNode(dfs);
+// 	      typename MutableGraph::Node w=F.bNode(dfs);
+// 	      pred.set(w, dfs);
+// 	      if (F.valid(pred.get(v))) {
+// 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
+// 	      } else {
+// 		free.set(w, residual_capacity.get(dfs)); 
+// 	      }
+// 	      if (w==tF) { 
+// 		__augment=true; 
+// 		_augment=true;
+// 		break; 
+// 	      }
+	      
+// 	    } else {
+// 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
+// 	    }
+// 	  } 
+// 	}
+
+// 	if (__augment) {
+// 	  typename MutableGraph::Node n=tF;
+// 	  Number augment_value=free.get(tF);
+// 	  while (F.valid(pred.get(n))) { 
+// 	    typename MutableGraph::Edge e=pred.get(n);
+// 	    res_graph.augment(original_edge.get(e), augment_value); 
+// 	    n=F.tail(e);
+// 	    if (residual_capacity.get(e)==augment_value) 
+// 	      F.erase(e); 
+// 	    else 
+// 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);
+// 	  }
+// 	}
+	
+//       }
+            
+//       return _augment;
+//     }
+
+    template<typename GraphWrapper> 
+    class DistanceMap {
+    protected:
+      GraphWrapper gw;
+      typename GraphWrapper::NodeMap<int> dist; 
+    public:
+      DistanceMap(GraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
+      //NodeMap(const ListGraph& _G, T a) : 
+      //G(_G), container(G.node_id, a) { }
+      void set(const typename GraphWrapper::Node& n, int a) { dist[n]=a; }
+      int get(const typename GraphWrapper::Node& n) const { return dist[n]; }
+      bool get(const typename GraphWrapper::Edge& e) const { 
+	return (dist.get(gw.tail(e))<dist.get(gw.head(e))); 
+      }
+      //typename std::vector<T>::reference operator[](Node n) { 
+      //return container[/*G.id(n)*/n.node->id]; }
+      //typename std::vector<T>::const_reference operator[](Node n) const { 
+      //return container[/*G.id(n)*/n.node->id]; 
+    };
+
     template<typename MutableGraph> bool augmentOnBlockingFlow() {      
       bool _augment=false;
 
       AugGraph res_graph(*G, *flow, *capacity);
 
       typedef typename AugGraph::NodeMap<bool> ReachedMap;
-      BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
+      BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
 
       bfs.pushAndSetReached(s);
-      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
+      //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
+      DistanceMap<AugGraph> dist(res_graph);
       while ( !bfs.finished() ) { 
 	AugOutEdgeIt e=bfs;
 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
 	}
-	
 	++bfs;
       } //computing distances from s in the residual graph
 
+//       MutableGraph F;
+//       typename AugGraph::NodeMap<typename MutableGraph::Node> 
+// 	res_graph_to_F(res_graph);
+//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
+// 	res_graph_to_F.set(n, F.addNode());
+//       }
+      
+//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
+//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
+
+//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
+//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
+
+//       //Making F to the graph containing the edges of the residual graph 
+//       //which are in some shortest paths
+//       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
+// 	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
+// 	  typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+// 	  original_edge.update();
+// 	  original_edge.set(f, e);
+// 	  residual_capacity.update();
+// 	  residual_capacity.set(f, res_graph.free(e));
+// 	} 
+//       }
+
       MutableGraph F;
+      typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;
+      FilterResGraph filter_res_graph(res_graph, dist);
       typename AugGraph::NodeMap<typename MutableGraph::Node> 
 	res_graph_to_F(res_graph);
       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
@@ -363,7 +511,7 @@
 	__augment=false;
 	//computing blocking flow with dfs
 	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
-	DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
+	DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F);
 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
 	pred.set(sF, typename MutableGraph::Edge(INVALID));
 	//invalid iterators for sources
@@ -413,6 +561,7 @@
             
       return _augment;
     }
+
     template<typename MutableGraph> bool augmentOnBlockingFlow1() {      
       bool _augment=false;
 
@@ -420,7 +569,7 @@
 
       //bfs for distances on the residual graph
       typedef typename AugGraph::NodeMap<bool> ReachedMap;
-      BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
+      BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
       bfs.pushAndSetReached(s);
       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
 
diff -r 60de0f16a4a1 -r f24f276e0b6b src/work/marci/graph_wrapper.h
--- a/src/work/marci/graph_wrapper.h	Mon Mar 29 21:43:27 2004 +0000
+++ b/src/work/marci/graph_wrapper.h	Tue Mar 30 07:07:44 2004 +0000
@@ -91,7 +91,7 @@
     GraphWrapper gw;
   
   public:
-    typedef typename GraphWrapper::BaseGraph BaseGraph;
+    //typedef typename GraphWrapper::BaseGraph BaseGraph;
 
     typedef typename GraphWrapper::Node Node;
     typedef typename GraphWrapper::NodeIt NodeIt;
@@ -105,8 +105,8 @@
     //GraphWrapperSkeleton() : gw() { }
     GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { }
 
-    void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
-    BaseGraph& getGraph() const { return gw.getGraph(); }
+    //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
+    //BaseGraph& getGraph() const { return gw.getGraph(); }
     
     template<typename I> I& first(I& i) const { return gw.first(i); }
     template<typename I, typename P> I& first(I& i, const P& p) const { 
@@ -342,6 +342,48 @@
       { return GraphWrapperSkeleton<GraphWrapper>::head(e); }
   };
 
+  //Subgraph on the same node-set and partial edge-set
+  template<typename GraphWrapper, typename EdgeFilterMap>
+  class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
+  protected:
+    EdgeFilterMap* filter_map;
+  public:
+    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
+    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
+    typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
+    typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
+    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
+    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
+
+    SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) : 
+      GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { }  
+
+    template<typename I> I& first(I& i) const { 
+      gw.first(i); 
+      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
+      return i;
+    }
+    template<typename I, typename P> I& first(I& i, const P& p) const { 
+      gw.first(i, p); 
+      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
+      return i;
+    }
+    
+    //template<typename I> I getNext(const I& i) const { 
+    //  return gw.getNext(i); 
+    //}
+    template<typename I> I& next(I &i) const { 
+      gw.next(i); 
+      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
+      return i;
+    }
+    
+    template< typename It > It first() const { 
+      It e; this->first(e); return e; }
+    
+    template< typename It > It first(const Node& v) const { 
+      It e; this->first(e, v); return e; }
+  };
 
 //   template<typename GraphWrapper>
 //   class UndirGraphWrapper {
@@ -858,6 +900,9 @@
 //       }
     };
 
+    //FIXME This is just for having InEdgeIt
+    typedef void InEdgeIt;
+
     class EdgeIt : public Edge {
       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
       typename Graph::NodeIt v;
@@ -1005,6 +1050,11 @@
     Node bNode(OutEdgeIt e) const { 
       return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
 
+    int nodeNum() const { return gw.nodeNum(); }
+    //FIXME
+    //int edgeNum() const { return gw.edgeNum(); }
+
+
     int id(Node v) const { return gw.id(v); }
 
     bool valid(Node n) const { return gw.valid(n); }