COIN-OR::LEMON - Graph Library

Changeset 569:3b6afd33c221 in lemon-0.x


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

BidirGraphWrapper?<Graph>, the map values are different for the opposite edges.

Location:
src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/graph_wrapper.h

    r565 r569  
    219219  };
    220220
     221
     222
    221223  /// A graph wrapper which reverses the orientation of the edges.
    222224
     
    292294
    293295  };
     296
     297
    294298
    295299  /// Wrapper for hiding nodes and edges from a graph.
     
    464468  };
    465469
     470
     471
    466472  /// A wrapper for forgetting the orientation of a graph.
    467473
     
    561567  };
    562568
    563  
    564 
    565   /// A wrapper for composing the residual graph for directed flow and circulation problems.
    566 
    567   /// A wrapper for composing the residual graph for directed flow and circulation problems.
    568   template<typename Graph, typename Number,
    569            typename CapacityMap, typename FlowMap>
    570   class ResGraphWrapper : public GraphWrapper<Graph> {
     569
     570
     571  /// A wrapper for composing bidirected graph from a directed one.
     572  /// experimental, for fezso's sake.
     573  template<typename Graph>
     574  class BidirGraphWrapper : public GraphWrapper<Graph> {
    571575  protected:
    572     const CapacityMap* capacity;
    573     FlowMap* flow;
    574 
    575     ResGraphWrapper() : GraphWrapper<Graph>(0),
    576                         capacity(0), flow(0) { }
    577     void setCapacityMap(const CapacityMap& _capacity) {
    578       capacity=&_capacity;
    579     }
    580     void setFlowMap(FlowMap& _flow) {
    581       flow=&_flow;
    582     }
     576    //const CapacityMap* capacity;
     577    //FlowMap* flow;
     578
     579    BidirGraphWrapper() : GraphWrapper<Graph>()/*,
     580                                                 capacity(0), flow(0)*/ { }
     581//     void setCapacityMap(const CapacityMap& _capacity) {
     582//       capacity=&_capacity;
     583//     }
     584//     void setFlowMap(FlowMap& _flow) {
     585//       flow=&_flow;
     586//     }
    583587
    584588  public:
    585589
    586     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
    587                     FlowMap& _flow) :
    588       GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
     590    BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
     591                                     FlowMap& _flow*/) :
     592      GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
    589593
    590594    class Edge;
     
    596600    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    597601    class Edge : public Graph::Edge {
    598       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
     602      friend class BidirGraphWrapper<Graph>;
    599603    protected:
    600604      bool backward; //true, iff backward
     
    619623
    620624    class OutEdgeIt {
    621       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
     625      friend class BidirGraphWrapper<Graph>;
    622626    protected:
    623627      typename Graph::OutEdgeIt out;
     
    630634      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
    631635//the unique invalid iterator
    632       OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
     636      OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
    633637        backward=false;
    634         resG.graph->first(out, v);
    635         while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
    636         if (!resG.graph->valid(out)) {
     638        _G.graph->first(out, v);
     639        while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
     640        if (!_G.graph->valid(out)) {
    637641          backward=true;
    638           resG.graph->first(in, v);
    639           while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
     642          _G.graph->first(in, v);
     643          while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
    640644        }
    641645      }
     
    653657
    654658    class InEdgeIt {
    655       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
     659      friend class BidirGraphWrapper<Graph>;
    656660    protected:
    657661      typename Graph::OutEdgeIt out;
     
    664668      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
    665669//the unique invalid iterator
    666       InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
     670      InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
    667671        backward=false;
    668         resG.graph->first(in, v);
    669         while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
    670         if (!resG.graph->valid(in)) {
     672        _G.graph->first(in, v);
     673        while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
     674        if (!_G.graph->valid(in)) {
    671675          backward=true;
    672           resG.graph->first(out, v);
    673           while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
     676          _G.graph->first(out, v);
     677          while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
    674678        }
    675679      }
     
    687691
    688692    class EdgeIt {
     693      friend class BidirGraphWrapper<Graph>;
     694    protected:
     695      typename Graph::EdgeIt e;
     696      bool backward;
     697    public:
     698      EdgeIt() { }
     699      EdgeIt(const Invalid& i) : e(i), backward(true) { }
     700      EdgeIt(const BidirGraphWrapper<Graph>& _G) {
     701        backward=false;
     702        _G.graph->first(e);
     703        while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
     704        if (!_G.graph->valid(e)) {
     705          backward=true;
     706          _G.graph->first(e);
     707          while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
     708        }
     709      }
     710      operator Edge() const {
     711        return Edge(e, this->backward);
     712      }
     713    };
     714
     715    using GraphWrapper<Graph>::first;
     716//     NodeIt& first(NodeIt& i) const {
     717//       i=NodeIt(*this); return i;
     718//     }
     719    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     720      i=OutEdgeIt(*this, p); return i;
     721    }
     722//    FIXME not tested
     723    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     724      i=InEdgeIt(*this, p); return i;
     725    }
     726    EdgeIt& first(EdgeIt& i) const {
     727      i=EdgeIt(*this); return i;
     728    }
     729 
     730    using GraphWrapper<Graph>::next;
     731//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
     732    OutEdgeIt& next(OutEdgeIt& e) const {
     733      if (!e.backward) {
     734        Node v=this->graph->aNode(e.out);
     735        this->graph->next(e.out);
     736        while(this->graph->valid(e.out) && !enabled(e)) {
     737          this->graph->next(e.out); }
     738        if (!this->graph->valid(e.out)) {
     739          e.backward=true;
     740          this->graph->first(e.in, v);
     741          while(this->graph->valid(e.in) && !enabled(e)) {
     742            this->graph->next(e.in); }
     743        }
     744      } else {
     745        this->graph->next(e.in);
     746        while(this->graph->valid(e.in) && !enabled(e)) {
     747          this->graph->next(e.in); }
     748      }
     749      return e;
     750    }
     751//     FIXME Not tested
     752    InEdgeIt& next(InEdgeIt& e) const {
     753      if (!e.backward) {
     754        Node v=this->graph->aNode(e.in);
     755        this->graph->next(e.in);
     756        while(this->graph->valid(e.in) && !enabled(e)) {
     757          this->graph->next(e.in); }
     758        if (!this->graph->valid(e.in)) {
     759          e.backward=true;
     760          this->graph->first(e.out, v);
     761          while(this->graph->valid(e.out) && !enabled(e)) {
     762            this->graph->next(e.out); }
     763        }
     764      } else {
     765        this->graph->next(e.out);
     766        while(this->graph->valid(e.out) && !enabled(e)) {
     767          this->graph->next(e.out); }
     768      }
     769      return e;
     770    }
     771    EdgeIt& next(EdgeIt& e) const {
     772      if (!e.backward) {
     773        this->graph->next(e.e);
     774        while(this->graph->valid(e.e) && !enabled(e)) {
     775          this->graph->next(e.e); }
     776        if (!this->graph->valid(e.e)) {
     777          e.backward=true;
     778          this->graph->first(e.e);
     779          while(this->graph->valid(e.e) && !enabled(e)) {
     780            this->graph->next(e.e); }
     781        }
     782      } else {
     783        this->graph->next(e.e);
     784        while(this->graph->valid(e.e) && !enabled(e)) {
     785          this->graph->next(e.e); }
     786      }
     787      return e;
     788    }
     789
     790    Node tail(Edge e) const {
     791      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
     792    Node head(Edge e) const {
     793      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
     794
     795    Node aNode(OutEdgeIt e) const {
     796      return ((!e.backward) ? this->graph->aNode(e.out) :
     797              this->graph->aNode(e.in)); }
     798    Node bNode(OutEdgeIt e) const {
     799      return ((!e.backward) ? this->graph->bNode(e.out) :
     800              this->graph->bNode(e.in)); }
     801
     802    Node aNode(InEdgeIt e) const {
     803      return ((!e.backward) ? this->graph->aNode(e.in) :
     804              this->graph->aNode(e.out)); }
     805    Node bNode(InEdgeIt e) const {
     806      return ((!e.backward) ? this->graph->bNode(e.in) :
     807              this->graph->bNode(e.out)); }
     808
     809//    int nodeNum() const { return graph->nodeNum(); }
     810    //FIXME
     811    void edgeNum() const { }
     812    //int edgeNum() const { return graph->edgeNum(); }
     813
     814
     815//    int id(Node v) const { return graph->id(v); }
     816
     817    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
     818    bool valid(Edge e) const {
     819      return this->graph->valid(e);
     820        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
     821    }
     822
     823    bool forward(const Edge& e) const { return !e.backward; }
     824    bool backward(const Edge& e) const { return e.backward; }
     825
     826//     void augment(const Edge& e, Number a) const {
     827//       if (!e.backward) 
     828// //   flow->set(e.out, flow->get(e.out)+a);
     829//      flow->set(e, (*flow)[e]+a);
     830//       else 
     831// //   flow->set(e.in, flow->get(e.in)-a);
     832//      flow->set(e, (*flow)[e]-a);
     833//     }
     834
     835    bool enabled(const Edge& e) const {
     836      if (!e.backward)
     837//      return (capacity->get(e.out)-flow->get(e.out));
     838        //return ((*capacity)[e]-(*flow)[e]);
     839        return true;
     840      else
     841//      return (flow->get(e.in));
     842        //return ((*flow)[e]);
     843        return true;
     844    }
     845
     846//     Number enabled(typename Graph::OutEdgeIt out) const {
     847// //      return (capacity->get(out)-flow->get(out));
     848//       return ((*capacity)[out]-(*flow)[out]);
     849//     }
     850   
     851//     Number enabled(typename Graph::InEdgeIt in) const {
     852// //      return (flow->get(in));
     853//       return ((*flow)[in]);
     854//     }
     855
     856    template <typename T>
     857    class EdgeMap {
     858      typename Graph::template EdgeMap<T> forward_map, backward_map;
     859    public:
     860      EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
     861      EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
     862      void set(Edge e, T a) {
     863        if (!e.backward)
     864          forward_map.set(e.out, a);
     865        else
     866          backward_map.set(e.in, a);
     867      }
     868      T operator[](Edge e) const {
     869        if (!e.backward)
     870          return forward_map[e.out];
     871        else
     872          return backward_map[e.in];
     873      }
     874//       T get(Edge e) const {
     875//      if (e.out_or_in)
     876//        return forward_map.get(e.out);
     877//      else
     878//        return backward_map.get(e.in);
     879//       }
     880    };
     881  };
     882
     883
     884
     885  /// A wrapper for composing the residual graph for directed flow and circulation problems.
     886
     887  /// A wrapper for composing the residual graph for directed flow and circulation problems.
     888  template<typename Graph, typename Number,
     889           typename CapacityMap, typename FlowMap>
     890  class ResGraphWrapper : public GraphWrapper<Graph> {
     891  protected:
     892    const CapacityMap* capacity;
     893    FlowMap* flow;
     894
     895    ResGraphWrapper() : GraphWrapper<Graph>(0),
     896                        capacity(0), flow(0) { }
     897    void setCapacityMap(const CapacityMap& _capacity) {
     898      capacity=&_capacity;
     899    }
     900    void setFlowMap(FlowMap& _flow) {
     901      flow=&_flow;
     902    }
     903
     904  public:
     905
     906    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
     907                    FlowMap& _flow) :
     908      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
     909
     910    class Edge;
     911    class OutEdgeIt;
     912    friend class Edge;
     913    friend class OutEdgeIt;
     914
     915    typedef typename GraphWrapper<Graph>::Node Node;
     916    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
     917    class Edge : public Graph::Edge {
     918      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
     919    protected:
     920      bool backward; //true, iff backward
     921//      typename Graph::Edge e;
     922    public:
     923      Edge() { }
     924      Edge(const typename Graph::Edge& _e, bool _backward) :
     925        Graph::Edge(_e), backward(_backward) { }
     926      Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
     927//the unique invalid iterator
     928      friend bool operator==(const Edge& u, const Edge& v) {
     929        return (v.backward==u.backward &&
     930                static_cast<typename Graph::Edge>(u)==
     931                static_cast<typename Graph::Edge>(v));
     932      }
     933      friend bool operator!=(const Edge& u, const Edge& v) {
     934        return (v.backward!=u.backward ||
     935                static_cast<typename Graph::Edge>(u)!=
     936                static_cast<typename Graph::Edge>(v));
     937      }
     938    };
     939
     940    class OutEdgeIt {
     941      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
     942    protected:
     943      typename Graph::OutEdgeIt out;
     944      typename Graph::InEdgeIt in;
     945      bool backward;
     946    public:
     947      OutEdgeIt() { }
     948      //FIXME
     949//      OutEdgeIt(const Edge& e) : Edge(e) { }
     950      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
     951//the unique invalid iterator
     952      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
     953        backward=false;
     954        _G.graph->first(out, v);
     955        while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
     956        if (!_G.graph->valid(out)) {
     957          backward=true;
     958          _G.graph->first(in, v);
     959          while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
     960        }
     961      }
     962      operator Edge() const {
     963//      Edge e;
     964//      e.forward=this->forward;
     965//      if (this->forward) e=out; else e=in;
     966//      return e;
     967        if (this->backward)
     968          return Edge(in, this->backward);
     969        else
     970          return Edge(out, this->backward);
     971      }
     972    };
     973
     974    class InEdgeIt {
     975      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
     976    protected:
     977      typename Graph::OutEdgeIt out;
     978      typename Graph::InEdgeIt in;
     979      bool backward;
     980    public:
     981      InEdgeIt() { }
     982      //FIXME
     983//      OutEdgeIt(const Edge& e) : Edge(e) { }
     984      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
     985//the unique invalid iterator
     986      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
     987        backward=false;
     988        _G.graph->first(in, v);
     989        while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
     990        if (!_G.graph->valid(in)) {
     991          backward=true;
     992          _G.graph->first(out, v);
     993          while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
     994        }
     995      }
     996      operator Edge() const {
     997//      Edge e;
     998//      e.forward=this->forward;
     999//      if (this->forward) e=out; else e=in;
     1000//      return e;
     1001        if (this->backward)
     1002          return Edge(out, this->backward);
     1003        else
     1004          return Edge(in, this->backward);
     1005      }
     1006    };
     1007
     1008    class EdgeIt {
    6891009      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    6901010    protected:
     
    6941014      EdgeIt() { }
    6951015      EdgeIt(const Invalid& i) : e(i), backward(true) { }
    696       EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
     1016      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
    6971017        backward=false;
    698         resG.graph->first(e);
    699         while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
    700         if (!resG.graph->valid(e)) {
     1018        _G.graph->first(e);
     1019        while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
     1020        if (!_G.graph->valid(e)) {
    7011021          backward=true;
    702           resG.graph->first(e);
    703           while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
     1022          _G.graph->first(e);
     1023          while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
    7041024        }
    7051025      }
     
    8751195  };
    8761196
     1197
     1198
    8771199  /// ErasingFirstGraphWrapper for blocking flows.
    8781200
  • src/work/marci/iterator_bfs_demo.cc

    r557 r569  
    315315  }
    316316
     317
     318
     319  {
     320    typedef BidirGraphWrapper<const Graph> GW;
     321    GW gw(G);
     322   
     323    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
     324   
     325    cout << "bfs and dfs iterator demo on the undirected graph" << endl;
     326    for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
     327      cout << node_name[GW::Node(n)] << ": ";
     328      cout << "out edges: ";
     329      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     330        cout << edge_name[e] << " ";
     331      cout << "in edges: ";
     332      for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     333        cout << edge_name[e] << " ";
     334      cout << endl;
     335    }
     336//     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
     337//       cout << edge_name.get(e) << " ";
     338//     }
     339//     cout << endl;
     340
     341    cout << "bfs from t ..." << endl;
     342    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
     343    bfs.pushAndSetReached(t);
     344    while (!bfs.finished()) {
     345      //cout << "edge: ";
     346      if (gw.valid(GW::OutEdgeIt(bfs))) {
     347        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
     348          node_name[gw.aNode(bfs)] <<
     349          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     350          node_name[gw.bNode(bfs)] <<
     351          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
     352           ": is not newly reached.");
     353      } else {
     354        cout << "invalid" << /*endl*/", " <<
     355          node_name[bfs.aNode()] <<
     356          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     357         
     358          "invalid.";
     359      }
     360      cout << endl;
     361      ++bfs;
     362    }
     363
     364    cout << "    /-->    ------------->            "<< endl;
     365    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
     366    cout << "  / |          |    /  /->     \\     "<< endl;
     367    cout << " /  |          |   /  |    ^    \\  "<< endl;
     368    cout << "s   |          |  /   |    |     \\->  t "<< endl;
     369    cout << " \\  |          | /    |    |     /->  "<< endl;
     370    cout << "  \\ |       --/ /     |    |    /     "<< endl;
     371    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
     372    cout << "    \\-->    ------------->         "<< endl;
     373   
     374    cout << "dfs from t ..." << endl;
     375    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
     376    dfs.pushAndSetReached(t);
     377    while (!dfs.finished()) {
     378      ++dfs;
     379      //cout << "edge: ";
     380      if (gw.valid(GW::OutEdgeIt(dfs))) {
     381        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
     382          node_name[gw.aNode(dfs)] <<
     383          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     384          node_name[gw.bNode(dfs)] <<
     385          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
     386           ": is not newly reached.");
     387      } else {
     388        cout << "invalid" << /*endl*/", " <<
     389          node_name[dfs.aNode()] <<
     390          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     391         
     392          "invalid.";
     393      }
     394      cout << endl;
     395    }
     396  }
     397
     398
     399
    317400  return 0;
    318401}
Note: See TracChangeset for help on using the changeset viewer.