Changeset 263:f24f276e0b6b in lemon-0.x

Timestamp:

03/30/04 09:07:44 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

ResGraphWrapper? ...

Location:

src/work

Files:

• edmonds_karp.h (modified) (6 diffs)
• marci/graph_wrapper.h (modified) (5 diffs)

src/work/edmonds_karp.h

@@ -314 +314 @@
     }
 
+//     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;
@@ -320 +441 @@
 
       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;
@@ -329 +451 @@
           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);
@@ -364 +512 @@
         //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));
@@ -414 +562 @@
       return _augment;
     }
+
     template<typename MutableGraph> bool augmentOnBlockingFlow1() {      
       bool _augment=false;
@@ -421 +570 @@
       //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

src/work/marci/graph_wrapper.h

@@ -92 +92 @@
   
   public:
-    typedef typename GraphWrapper::BaseGraph BaseGraph;
+    //typedef typename GraphWrapper::BaseGraph BaseGraph;
 
     typedef typename GraphWrapper::Node Node;
@@ -106 +106 @@
     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); }
@@ -343 +343 @@
   };
 
+  //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>
@@ -858 +900 @@
 //       }
     };
+
+    //FIXME This is just for having InEdgeIt
+    typedef void InEdgeIt;
 
     class EdgeIt : public Edge {
@@ -1006 +1051 @@
       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); }