COIN-OR::LEMON - Graph Library

Changeset 263:f24f276e0b6b in lemon-0.x


Ignore:
Timestamp:
03/30/04 09:07:44 (16 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@369
Message:

ResGraphWrapper? ...

Location:
src/work
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.h

    r259 r263  
    314314    }
    315315
     316//     template<typename MutableGraph> bool augmentOnBlockingFlow() {     
     317//       bool _augment=false;
     318
     319//       AugGraph res_graph(*G, *flow, *capacity);
     320
     321//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
     322//       BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
     323
     324//       bfs.pushAndSetReached(s);
     325//       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
     326//       while ( !bfs.finished() ) {
     327//      AugOutEdgeIt e=bfs;
     328//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     329//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     330//      }
     331       
     332//      ++bfs;
     333//       } //computing distances from s in the residual graph
     334
     335//       MutableGraph F;
     336//       typename AugGraph::NodeMap<typename MutableGraph::Node>
     337//      res_graph_to_F(res_graph);
     338//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
     339//      res_graph_to_F.set(n, F.addNode());
     340//       }
     341     
     342//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
     343//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
     344
     345//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
     346//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
     347
     348//       //Making F to the graph containing the edges of the residual graph
     349//       //which are in some shortest paths
     350//       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
     351//      if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
     352//        typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     353//        original_edge.update();
     354//        original_edge.set(f, e);
     355//        residual_capacity.update();
     356//        residual_capacity.set(f, res_graph.free(e));
     357//      }
     358//       }
     359
     360//       bool __augment=true;
     361
     362//       while (__augment) {
     363//      __augment=false;
     364//      //computing blocking flow with dfs
     365//      typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
     366//      DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
     367//      typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
     368//      pred.set(sF, typename MutableGraph::Edge(INVALID));
     369//      //invalid iterators for sources
     370
     371//      typename MutableGraph::NodeMap<Number> free(F);
     372
     373//      dfs.pushAndSetReached(sF);     
     374//      while (!dfs.finished()) {
     375//        ++dfs;
     376//        if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
     377//          if (dfs.isBNodeNewlyReached()) {
     378//            typename MutableGraph::Node v=F.aNode(dfs);
     379//            typename MutableGraph::Node w=F.bNode(dfs);
     380//            pred.set(w, dfs);
     381//            if (F.valid(pred.get(v))) {
     382//              free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
     383//            } else {
     384//              free.set(w, residual_capacity.get(dfs));
     385//            }
     386//            if (w==tF) {
     387//              __augment=true;
     388//              _augment=true;
     389//              break;
     390//            }
     391             
     392//          } else {
     393//            F.erase(typename MutableGraph::OutEdgeIt(dfs));
     394//          }
     395//        }
     396//      }
     397
     398//      if (__augment) {
     399//        typename MutableGraph::Node n=tF;
     400//        Number augment_value=free.get(tF);
     401//        while (F.valid(pred.get(n))) {
     402//          typename MutableGraph::Edge e=pred.get(n);
     403//          res_graph.augment(original_edge.get(e), augment_value);
     404//          n=F.tail(e);
     405//          if (residual_capacity.get(e)==augment_value)
     406//            F.erase(e);
     407//          else
     408//            residual_capacity.set(e, residual_capacity.get(e)-augment_value);
     409//        }
     410//      }
     411       
     412//       }
     413           
     414//       return _augment;
     415//     }
     416
     417    template<typename GraphWrapper>
     418    class DistanceMap {
     419    protected:
     420      GraphWrapper gw;
     421      typename GraphWrapper::NodeMap<int> dist;
     422    public:
     423      DistanceMap(GraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
     424      //NodeMap(const ListGraph& _G, T a) :
     425      //G(_G), container(G.node_id, a) { }
     426      void set(const typename GraphWrapper::Node& n, int a) { dist[n]=a; }
     427      int get(const typename GraphWrapper::Node& n) const { return dist[n]; }
     428      bool get(const typename GraphWrapper::Edge& e) const {
     429        return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
     430      }
     431      //typename std::vector<T>::reference operator[](Node n) {
     432      //return container[/*G.id(n)*/n.node->id]; }
     433      //typename std::vector<T>::const_reference operator[](Node n) const {
     434      //return container[/*G.id(n)*/n.node->id];
     435    };
     436
    316437    template<typename MutableGraph> bool augmentOnBlockingFlow() {     
    317438      bool _augment=false;
     
    320441
    321442      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    322       BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
     443      BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
    323444
    324445      bfs.pushAndSetReached(s);
    325       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
     446      //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
     447      DistanceMap<AugGraph> dist(res_graph);
    326448      while ( !bfs.finished() ) {
    327449        AugOutEdgeIt e=bfs;
     
    329451          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    330452        }
    331        
    332453        ++bfs;
    333454      } //computing distances from s in the residual graph
    334455
     456//       MutableGraph F;
     457//       typename AugGraph::NodeMap<typename MutableGraph::Node>
     458//      res_graph_to_F(res_graph);
     459//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
     460//      res_graph_to_F.set(n, F.addNode());
     461//       }
     462     
     463//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
     464//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
     465
     466//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
     467//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
     468
     469//       //Making F to the graph containing the edges of the residual graph
     470//       //which are in some shortest paths
     471//       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
     472//      if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
     473//        typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     474//        original_edge.update();
     475//        original_edge.set(f, e);
     476//        residual_capacity.update();
     477//        residual_capacity.set(f, res_graph.free(e));
     478//      }
     479//       }
     480
    335481      MutableGraph F;
     482      typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;
     483      FilterResGraph filter_res_graph(res_graph, dist);
    336484      typename AugGraph::NodeMap<typename MutableGraph::Node>
    337485        res_graph_to_F(res_graph);
     
    364512        //computing blocking flow with dfs
    365513        typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
    366         DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
     514        DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F);
    367515        typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
    368516        pred.set(sF, typename MutableGraph::Edge(INVALID));
     
    414562      return _augment;
    415563    }
     564
    416565    template<typename MutableGraph> bool augmentOnBlockingFlow1() {     
    417566      bool _augment=false;
     
    421570      //bfs for distances on the residual graph
    422571      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    423       BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
     572      BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
    424573      bfs.pushAndSetReached(s);
    425574      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
  • src/work/marci/graph_wrapper.h

    r259 r263  
    9292 
    9393  public:
    94     typedef typename GraphWrapper::BaseGraph BaseGraph;
     94    //typedef typename GraphWrapper::BaseGraph BaseGraph;
    9595
    9696    typedef typename GraphWrapper::Node Node;
     
    106106    GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { }
    107107
    108     void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
    109     BaseGraph& getGraph() const { return gw.getGraph(); }
     108    //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
     109    //BaseGraph& getGraph() const { return gw.getGraph(); }
    110110   
    111111    template<typename I> I& first(I& i) const { return gw.first(i); }
     
    343343  };
    344344
     345  //Subgraph on the same node-set and partial edge-set
     346  template<typename GraphWrapper, typename EdgeFilterMap>
     347  class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
     348  protected:
     349    EdgeFilterMap* filter_map;
     350  public:
     351    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
     352    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
     353    typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
     354    typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
     355    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
     356    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
     357
     358    SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) :
     359      GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { } 
     360
     361    template<typename I> I& first(I& i) const {
     362      gw.first(i);
     363      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
     364      return i;
     365    }
     366    template<typename I, typename P> I& first(I& i, const P& p) const {
     367      gw.first(i, p);
     368      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
     369      return i;
     370    }
     371   
     372    //template<typename I> I getNext(const I& i) const {
     373    //  return gw.getNext(i);
     374    //}
     375    template<typename I> I& next(I &i) const {
     376      gw.next(i);
     377      while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
     378      return i;
     379    }
     380   
     381    template< typename It > It first() const {
     382      It e; this->first(e); return e; }
     383   
     384    template< typename It > It first(const Node& v) const {
     385      It e; this->first(e, v); return e; }
     386  };
    345387
    346388//   template<typename GraphWrapper>
     
    858900//       }
    859901    };
     902
     903    //FIXME This is just for having InEdgeIt
     904    typedef void InEdgeIt;
    860905
    861906    class EdgeIt : public Edge {
     
    10061051      return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }
    10071052
     1053    int nodeNum() const { return gw.nodeNum(); }
     1054    //FIXME
     1055    //int edgeNum() const { return gw.edgeNum(); }
     1056
     1057
    10081058    int id(Node v) const { return gw.id(v); }
    10091059
Note: See TracChangeset for help on using the changeset viewer.