COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 148:004fdf703abb in lemon-0.x for src/work


Ignore:
Timestamp:
03/03/04 15:30:38 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@208
Message:

G.next(...), G.valid(...), ...

Location:
src/work
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • src/work/bfs_iterator.hh

    r144 r148  
    545545
    546546  template <typename Graph, typename OutEdgeIt,
    547             typename ReachedMap=typename Graph::NodeMap<bool> >
     547            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
    548548  class BfsIterator4 {
    549549    typedef typename Graph::NodeIt NodeIt;
    … …  
    567567        bfs_queue.push(s);
    568568        G.getFirst(actual_edge, s);
    569         if (actual_edge.valid()) {
     569        if (G.valid(actual_edge)/*.valid()*/) {
    570570          NodeIt w=G.bNode(actual_edge);
    571571          if (!reached.get(w)) {
    … …  
    583583    BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
    584584    operator++() {
    585       if (actual_edge.valid()) {
    586         ++actual_edge;
    587         if (actual_edge.valid()) {
     585      if (G.valid(actual_edge)/*.valid()*/) {
     586        /*++*/G.next(actual_edge);
     587        if (G.valid(actual_edge)/*.valid()*/) {
    588588          NodeIt w=G.bNode(actual_edge);
    589589          if (!reached.get(w)) {
    … …  
    599599        if (!bfs_queue.empty()) {
    600600          G.getFirst(actual_edge, bfs_queue.front());
    601           if (actual_edge.valid()) {
     601          if (G.valid(actual_edge)/*.valid()*/) {
    602602            NodeIt w=G.bNode(actual_edge);
    603603            if (!reached.get(w)) {
    … …  
    616616    operator OutEdgeIt () const { return actual_edge; }
    617617    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    618     bool isANodeExamined() const { return !(actual_edge.valid()); }
     618    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
    619619    NodeIt aNode() const { return bfs_queue.front(); }
    620620    NodeIt bNode() const { return G.bNode(actual_edge); }
    … …  
    623623 }; 
    624624
     625
     626  template <typename GraphWrapper, typename OutEdgeIt,
     627            typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
     628  class BfsIterator5 {
     629    typedef typename GraphWrapper::NodeIt NodeIt;
     630    GraphWrapper G;
     631    std::queue<NodeIt> bfs_queue;
     632    ReachedMap& reached;
     633    bool b_node_newly_reached;
     634    OutEdgeIt actual_edge;
     635    bool own_reached_map;
     636  public:
     637    BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
     638      G(_G), reached(_reached),
     639      own_reached_map(false) { }
     640    BfsIterator5(const GraphWrapper& _G) :
     641      G(_G), reached(*(new ReachedMap(G /*, false*/))),
     642      own_reached_map(true) { }
     643    ~BfsIterator5() { if (own_reached_map) delete &reached; }
     644    void pushAndSetReached(NodeIt s) {
     645      reached.set(s, true);
     646      if (bfs_queue.empty()) {
     647        bfs_queue.push(s);
     648        G.getFirst(actual_edge, s);
     649        if (G.valid(actual_edge)/*.valid()*/) {
     650          NodeIt w=G.bNode(actual_edge);
     651          if (!reached.get(w)) {
     652            bfs_queue.push(w);
     653            reached.set(w, true);
     654            b_node_newly_reached=true;
     655          } else {
     656            b_node_newly_reached=false;
     657          }
     658        }
     659      } else {
     660        bfs_queue.push(s);
     661      }
     662    }
     663    BfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
     664    operator++() {
     665      if (G.valid(actual_edge)/*.valid()*/) {
     666        /*++*/G.next(actual_edge);
     667        if (G.valid(actual_edge)/*.valid()*/) {
     668          NodeIt w=G.bNode(actual_edge);
     669          if (!reached.get(w)) {
     670            bfs_queue.push(w);
     671            reached.set(w, true);
     672            b_node_newly_reached=true;
     673          } else {
     674            b_node_newly_reached=false;
     675          }
     676        }
     677      } else {
     678        bfs_queue.pop();
     679        if (!bfs_queue.empty()) {
     680          G.getFirst(actual_edge, bfs_queue.front());
     681          if (G.valid(actual_edge)/*.valid()*/) {
     682            NodeIt w=G.bNode(actual_edge);
     683            if (!reached.get(w)) {
     684              bfs_queue.push(w);
     685              reached.set(w, true);
     686              b_node_newly_reached=true;
     687            } else {
     688              b_node_newly_reached=false;
     689            }
     690          }
     691        }
     692      }
     693      return *this;
     694    }
     695    bool finished() const { return bfs_queue.empty(); }
     696    operator OutEdgeIt () const { return actual_edge; }
     697    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     698    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
     699    NodeIt aNode() const { return bfs_queue.front(); }
     700    NodeIt bNode() const { return G.bNode(actual_edge); }
     701    const ReachedMap& getReachedMap() const { return reached; }
     702    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
     703  }; 
     704
    625705  template <typename Graph, typename OutEdgeIt,
    626             typename ReachedMap=typename Graph::NodeMap<bool> >
     706            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
    627707  class DfsIterator4 {
    628708    typedef typename Graph::NodeIt NodeIt;
    … …  
    651731      actual_edge=dfs_stack.top();
    652732      //actual_node=G.aNode(actual_edge);
    653       if (actual_edge.valid()) {
     733      if (G.valid(actual_edge)/*.valid()*/) {
    654734        NodeIt w=G.bNode(actual_edge);
    655735        actual_node=w;
    … …  
    660740        } else {
    661741          actual_node=G.aNode(actual_edge);
    662           ++(dfs_stack.top());
     742          /*++*/G.next(dfs_stack.top());
    663743          b_node_newly_reached=false;
    664744        }
    … …  
    672752    operator OutEdgeIt () const { return actual_edge; }
    673753    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    674     bool isANodeExamined() const { return !(actual_edge.valid()); }
     754    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
    675755    NodeIt aNode() const { return actual_node; /*FIXME*/}
    676756    NodeIt bNode() const { return G.bNode(actual_edge); }
    … …  
    679759  };
    680760
    681 
    682 
    683   template <typename GraphWrapper, typename ReachedMap>
    684   class BfsIterator5 {
     761  template <typename GraphWrapper, typename OutEdgeIt,
     762            typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
     763  class DfsIterator5 {
    685764    typedef typename GraphWrapper::NodeIt NodeIt;
    686     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
    687     GraphWrapper gw;
    688     std::queue<NodeIt> bfs_queue;
    689     ReachedMap reached;
    690     bool b_node_newly_reached;
    691     OutEdgeIt actual_edge;
     765    GraphWrapper G;
     766    std::stack<OutEdgeIt> dfs_stack;
     767    bool b_node_newly_reached;
     768    OutEdgeIt actual_edge;
     769    NodeIt actual_node;
     770    ReachedMap& reached;
     771    bool own_reached_map;
    692772  public:
    693     BfsIterator5(GraphWrapper _gw) :
    694       gw(_gw), reached(_gw.getGraph()) { }
     773    DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
     774      G(_G), reached(_reached),
     775      own_reached_map(false) { }
     776    DfsIterator5(const GraphWrapper& _G) :
     777      G(_G), reached(*(new ReachedMap(G /*, false*/))),
     778      own_reached_map(true) { }
     779    ~DfsIterator5() { if (own_reached_map) delete &reached; }
    695780    void pushAndSetReached(NodeIt s) {
     781      actual_node=s;
    696782      reached.set(s, true);
    697       if (bfs_queue.empty()) {
    698         bfs_queue.push(s);
    699         gw.getFirst(actual_edge, s);
    700         if (actual_edge.valid()) {
    701           NodeIt w=gw.bNode(actual_edge);
    702           if (!reached.get(w)) {
    703             bfs_queue.push(w);
    704             reached.set(w, true);
    705             b_node_newly_reached=true;
    706           } else {
    707             b_node_newly_reached=false;
    708           }
    709         }
    710       } else {
    711         bfs_queue.push(s);
    712       }
    713     }
    714     BfsIterator5<GraphWrapper, ReachedMap>&
     783      dfs_stack.push(G.template first<OutEdgeIt>(s));
     784    }
     785    DfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
    715786    operator++() {
    716       if (actual_edge.valid()) {
    717         ++actual_edge;
    718         if (actual_edge.valid()) {
    719           NodeIt w=gw.bNode(actual_edge);
    720           if (!reached.get(w)) {
    721             bfs_queue.push(w);
    722             reached.set(w, true);
    723             b_node_newly_reached=true;
    724           } else {
    725             b_node_newly_reached=false;
    726           }
    727         }
    728       } else {
    729         bfs_queue.pop();
    730         if (!bfs_queue.empty()) {
    731           gw.getFirst(actual_edge, bfs_queue.front());
    732           if (actual_edge.valid()) {
    733             NodeIt w=gw.bNode(actual_edge);
    734             if (!reached.get(w)) {
    735               bfs_queue.push(w);
    736               reached.set(w, true);
    737               b_node_newly_reached=true;
    738             } else {
    739               b_node_newly_reached=false;
    740             }
    741           }
    742         }
    743       }
    744       return *this;
    745     }
    746     bool finished() const { return bfs_queue.empty(); }
     787      actual_edge=dfs_stack.top();
     788      //actual_node=G.aNode(actual_edge);
     789      if (G.valid(actual_edge)/*.valid()*/) {
     790        NodeIt w=G.bNode(actual_edge);
     791        actual_node=w;
     792        if (!reached.get(w)) {
     793          dfs_stack.push(G.template first<OutEdgeIt>(w));
     794          reached.set(w, true);
     795          b_node_newly_reached=true;
     796        } else {
     797          actual_node=G.aNode(actual_edge);
     798          /*++*/G.next(dfs_stack.top());
     799          b_node_newly_reached=false;
     800        }
     801      } else {
     802        //actual_node=G.aNode(dfs_stack.top());
     803        dfs_stack.pop();
     804      }
     805      return *this;
     806    }
     807    bool finished() const { return dfs_stack.empty(); }
    747808    operator OutEdgeIt () const { return actual_edge; }
    748809    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    749     bool isANodeExamined() const { return !(actual_edge.valid()); }
    750     NodeIt aNode() const { return bfs_queue.front(); }
    751     NodeIt bNode() const { return gw.bNode(actual_edge); }
     810    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
     811    NodeIt aNode() const { return actual_node; /*FIXME*/}
     812    NodeIt bNode() const { return G.bNode(actual_edge); }
    752813    const ReachedMap& getReachedMap() const { return reached; }
    753     const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
    754  };
     814    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
     815  };
    755816
    756817

  • src/work/edmonds_karp.hh

    r141 r148  
    149149      OldOutEdgeIt out;
    150150      OldInEdgeIt in;
    151       bool out_or_in; //1, iff out
    152     public:
    153       EdgeIt() : out_or_in(1) { }
     151      bool out_or_in; //true, iff out
     152    public:
     153      EdgeIt() : out_or_in(true) { }
    154154      Number free() const {
    155155        if (out_or_in) {
    … …  
    247247
    248248  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    249   class ResGraph3 {
     249  class ResGraphWrapper {
    250250  public:
    251251    typedef typename Graph::NodeIt NodeIt;
    252252    typedef typename Graph::EachNodeIt EachNodeIt;
    253 
    254253  private:
    255     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
    256254    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
    257255    typedef typename Graph::InEdgeIt OldInEdgeIt;
    258     const Graph& G;
    259     FlowMap& flow;
    260     const CapacityMap& capacity;
    261   public:
    262     ResGraph3(const Graph& _G, FlowMap& _flow,
     256    const Graph* G;
     257    FlowMap* flow;
     258    const CapacityMap* capacity;
     259  public:
     260    ResGraphWrapper(const Graph& _G, FlowMap& _flow,
    263261             const CapacityMap& _capacity) :
    264       G(_G), flow(_flow), capacity(_capacity) { }
    265 
     262      G(&_G), flow(&_flow), capacity(&_capacity) { }
     263//     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
     264//       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
    266265    class EdgeIt;
    267266    class OutEdgeIt;
    … …  
    270269
    271270    class EdgeIt {
    272       friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
     271      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    273272    protected:
    274273      //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
    … …  
    279278      OldOutEdgeIt out;
    280279      OldInEdgeIt in;
    281       bool out_or_in; //1, iff out
    282     public:
    283       EdgeIt() : out_or_in(1) { }
     280      bool out_or_in; //true, iff out
     281    public:
     282      EdgeIt() : out_or_in(true) { }
     283      EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
     284        G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
    284285      //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) { }
    285286      Number free() const {
    … …  
    318319    };
    319320
     321    Number free(OldOutEdgeIt out) const {
     322      return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
     323    }
     324    Number free(OldInEdgeIt in) const {
     325      return (/*resG->*/flow->get(in));
     326    }
     327
    320328    class OutEdgeIt : public EdgeIt {
    321       friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
     329      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    322330    public:
    323331      OutEdgeIt() { }
    324332    private:
    325       OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) {
    326         G=&_G;
    327         flow=&_flow;
    328         capacity=&_capacity;
     333      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
    329334        //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
    330335        G->getFirst(out, v);
    331         while( out.valid() && !(free()>0) ) { ++out; }
     336        while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    332337        if (!out.valid()) {
    333338          out_or_in=0;
    334339          //in=/*resG->*/G->template first<OldInEdgeIt>(v);
    335340          G->getFirst(in, v);
    336           while( in.valid() && !(free()>0) ) { ++in; }
     341          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    337342        }
    338343      }
    … …  
    342347          NodeIt v=/*resG->*/G->aNode(out);
    343348          ++out;
    344           while( out.valid() && !(free()>0) ) { ++out; }
     349          while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    345350          if (!out.valid()) {
    346351            out_or_in=0;
    347352            G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
    348             while( in.valid() && !(free()>0) ) { ++in; }
     353            while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    349354          }
    350355        } else {
    351356          ++in;
    352           while( in.valid() && !(free()>0) ) { ++in; }
     357          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    353358        }
    354359        return *this;
    … …  
    357362
    358363    class EachEdgeIt : public EdgeIt {
     364      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    359365      typename Graph::EachNodeIt v;
    360366    public:
    361367      EachEdgeIt() { }
    362368      //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
    363       EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) {
    364         G=&_G;
    365         flow=&_flow;
    366         capacity=&_capacity;
    367         out_or_in=1;
     369      EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
     370        out_or_in=true;
    368371        G->getFirst(v);
    369372        if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
    370         while (out.valid() && !(free()>0) ) { ++out; }
     373        while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    371374        while (v.valid() && !out.valid()) {
    372375          ++v;
    373376          if (v.valid()) G->getFirst(out, v);
    374           while (out.valid() && !(free()>0) ) { ++out; }
     377          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    375378        }
    376379        if (!out.valid()) {
    … …  
    378381          G->getFirst(v);
    379382          if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
    380           while (in.valid() && !(free()>0) ) { ++in; }
     383          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    381384          while (v.valid() && !in.valid()) {
    382385            ++v;
    383386            if (v.valid()) G->getFirst(in, v);
    384             while (in.valid() && !(free()>0) ) { ++in; }
     387            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    385388          }
    386389        }
    … …  
    389392        if (out_or_in) {
    390393          ++out;
    391           while (out.valid() && !(free()>0) ) { ++out; }
     394          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    392395          while (v.valid() && !out.valid()) {
    393396            ++v;
    394397            if (v.valid()) G->getFirst(out, v);
    395             while (out.valid() && !(free()>0) ) { ++out; }
     398            while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    396399          }
    397400          if (!out.valid()) {
    … …  
    399402            G->getFirst(v);
    400403            if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
    401             while (in.valid() && !(free()>0) ) { ++in; }
     404            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    402405            while (v.valid() && !in.valid()) {
    403406              ++v;
    404407              if (v.valid()) G->getFirst(in, v);
    405               while (in.valid() && !(free()>0) ) { ++in; }
     408              while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    406409            } 
    407410          }
    408411        } else {
    409412          ++in;
    410           while (in.valid() && !(free()>0) ) { ++in; }
     413          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    411414          while (v.valid() && !in.valid()) {
    412415            ++v;
    413416            if (v.valid()) G->getFirst(in, v);
    414             while (in.valid() && !(free()>0) ) { ++in; }
     417            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    415418          }
    416419        }
    … …  
    419422    };
    420423
     424    void getFirst(EachNodeIt& v) const { G->getFirst(v); }
    421425    void getFirst(OutEdgeIt& e, NodeIt v) const {
    422       e=OutEdgeIt(G, v, flow, capacity);
     426      e=OutEdgeIt(*G, v, *flow, *capacity);
    423427    }
    424428    void getFirst(EachEdgeIt& e) const {
    425       e=EachEdgeIt(G, flow, capacity);
    426     }
    427     void getFirst(EachNodeIt& v) const { G.getFirst(v); }
     429      e=EachEdgeIt(*G, *flow, *capacity);
     430    }
     431   
     432    EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
     433
     434    OutEdgeIt& next(OutEdgeIt& e) const {
     435      if (e.out_or_in) {
     436        NodeIt v=G->aNode(e.out);
     437        ++(e.out);
     438        while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     439        if (!G->valid(e.out)) {
     440          e.out_or_in=0;
     441          G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
     442          while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     443        }
     444      } else {
     445        ++(e.in);
     446        while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     447      }
     448      return e;
     449    }
     450
     451    EachEdgeIt& next(EachEdgeIt& e) const {
     452      if (e.out_or_in) {
     453        ++(e.out);
     454        while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     455          while (G->valid(e.v) && !G->valid(e.out)) {
     456            ++(e.v);
     457            if (G->valid(e.v)) G->getFirst(e.out, e.v);
     458            while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     459          }
     460          if (!G->valid(e.out)) {
     461            e.out_or_in=0;
     462            G->getFirst(e.v);
     463            if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
     464            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     465            while (G->valid(e.v) && !G->valid(e.in)) {
     466              ++(e.v);
     467              if (G->valid(e.v)) G->getFirst(e.in, e.v);
     468              while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     469            } 
     470          }
     471        } else {
     472          ++(e.in);
     473          while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     474          while (G->valid(e.v) && !G->valid(e.in)) {
     475            ++(e.v);
     476            if (G->valid(e.v)) G->getFirst(e.in, e.v);
     477            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     478          }
     479        }
     480        return e;
     481      }
    428482   
     483
    429484    template< typename It >
    430485    It first() const {
    … …  
    442497
    443498    NodeIt tail(EdgeIt e) const {
    444       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
     499      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
    445500    NodeIt head(EdgeIt e) const {
    446       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
     501      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
    447502
    448503    NodeIt aNode(OutEdgeIt e) const {
    449       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
     504      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
    450505    NodeIt bNode(OutEdgeIt e) const {
    451       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
    452 
    453     int id(NodeIt v) const { return G.id(v); }
     506      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
     507
     508    int id(NodeIt v) const { return G->id(v); }
     509
     510    bool valid(NodeIt n) const { return G->valid(n); }
     511    bool valid(EdgeIt e) const {
     512      return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
    454513
    455514    template <typename T>
    … …  
    457516      typename Graph::NodeMap<T> node_map;
    458517    public:
    459       NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
    460       NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(_G.G, a) { }
     518      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
     519      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
    461520      void set(NodeIt nit, T a) { node_map.set(nit, a); }
    462521      T get(NodeIt nit) const { return node_map.get(nit); }
    … …  
    467526      typename Graph::EdgeMap<T> forward_map, backward_map;
    468527    public:
    469       EdgeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.G), backward_map(_G.G) { }
    470       EdgeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.G, a), backward_map(_G.G, a) { }
     528      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }
     529      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }
    471530      void set(EdgeIt e, T a) {
    472531        if (e.out_or_in)
    … …  
    495554
    496555  private:
    497     const Graph& G;
     556    const Graph* G;
    498557    NodeIt s;
    499558    NodeIt t;
    500     FlowMap& flow;
    501     const CapacityMap& capacity;
    502     typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
     559    FlowMap* flow;
     560    const CapacityMap* capacity;
     561    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
    503562    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    504563    typedef typename AugGraph::EdgeIt AugEdgeIt;
    … …  
    510569  public:
    511570    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
    512       G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //, 
     571      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, 
    513572      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
    514573      { }
    515574    bool augmentOnShortestPath() {
    516       AugGraph res_graph(G, flow, capacity);
     575      AugGraph res_graph(*G, *flow, *capacity);
    517576      bool _augment=false;
    518577     
    519578      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    520       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
     579      BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
    521580      res_bfs.pushAndSetReached(s);
    522581       
    … …  
    530589      while ( !res_bfs.finished() ) {
    531590        AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
    532         if (e.valid() && res_bfs.isBNodeNewlyReached()) {
     591        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
    533592          NodeIt v=res_graph.tail(e);
    534593          NodeIt w=res_graph.head(e);
    535594          pred.set(w, e);
    536           if (pred.get(v).valid()) {
     595          if (res_graph.valid(pred.get(v))) {
    537596            free.set(w, std::min(free.get(v), e.free()));
    538597          } else {
    … …  
    548607        NodeIt n=t;
    549608        Number augment_value=free.get(t);
    550         while (pred.get(n).valid()) {
     609        while (res_graph.valid(pred.get(n))) {
    551610          AugEdgeIt e=pred.get(n);
    552611          e.augment(augment_value);
    … …  
    561620      bool _augment=false;
    562621
    563       AugGraph res_graph(G, flow, capacity);
     622      AugGraph res_graph(*G, *flow, *capacity);
    564623
    565624      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    … …  
    570629      while ( !bfs.finished() ) {
    571630        AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
    572         if (e.valid() && bfs.isBNodeNewlyReached()) {
     631        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    573632          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    574633        }
    … …  
    579638      MutableGraph F;
    580639      typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
    581       for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++n) {
     640      for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
    582641        res_graph_to_F.set(n, F.addNode());
    583642      }
    … …  
    587646
    588647      typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
    589       typename MutableGraph::EdgeMap<Number> free_on_edge(F);
     648      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
    590649
    591650      //Making F to the graph containing the edges of the residual graph
    592651      //which are in some shortest paths
    593       for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++e) {
     652      for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
    594653        if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
    595654          typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    596655          original_edge.update();
    597656          original_edge.set(f, e);
    598           free_on_edge.update();
    599           free_on_edge.set(f, e.free());
     657          residual_capacity.update();
     658          residual_capacity.set(f, e.free());
    600659        }
    601660      }
    … …  
    614673        while (!dfs.finished()) {
    615674          ++dfs;
    616           if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
     675          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
    617676            //std::cout << "OutEdgeIt: " << dfs;
    618677            //std::cout << " aNode: " << F.aNode(dfs);
    … …  
    622681            typename MutableGraph::NodeIt w=F.bNode(dfs);
    623682            pred.set(w, dfs);
    624             if (pred.get(v).valid()) {
    625               free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));
     683            if (F.valid(pred.get(v))) {
     684              free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
    626685            } else {
    627               free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/);
     686              free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/);
    628687            }
    629688            if (w==tF) {
    … …  
    658717          typename MutableGraph::NodeIt n=tF;
    659718          Number augment_value=free.get(tF);
    660           while (pred.get(n).valid()) {
     719          while (F.valid(pred.get(n))) {
    661720            typename MutableGraph::EdgeIt e=pred.get(n);
    662721            original_edge.get(e).augment(augment_value);
    663722            n=F.tail(e);
    664             if (free_on_edge.get(e)==augment_value)
     723            if (residual_capacity.get(e)==augment_value)
    665724              F.erase(e);
    666725            else
    667               free_on_edge.set(e, free_on_edge.get(e)-augment_value);
     726              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
    668727          }
    669728        }
    … …  
    691750    Number flowValue() {
    692751      Number a=0;
    693       for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
    694         a+=flow.get(i);
     752      OutEdgeIt e;
     753      for(G->getFirst(e, s); G->valid(e); G->next(e)) {
     754        a+=flow->get(e);
    695755      }
    696756      return a;
    697757    }
    698758  };
    699 
    700 
    701 /*
    702   template <typename Graph>
    703   class IteratorBoolNodeMap {
    704     typedef typename Graph::NodeIt NodeIt;
    705     typedef typename Graph::EachNodeIt EachNodeIt;
    706     class BoolItem {
    707     public:
    708       bool value;
    709       NodeIt prev;
    710       NodeIt next;
    711       BoolItem() : value(false), prev(), next() {}
    712     };
    713     NodeIt first_true;
    714     //NodeIt last_true;
    715     NodeIt first_false;
    716     //NodeIt last_false;
    717     const Graph& G;
    718     typename Graph::NodeMap<BoolItem> container;
    719   public:
    720     typedef bool ValueType;
    721     typedef NodeIt KeyType;
    722     IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {
    723       //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
    724       //BoolItem b=container.get(e);
    725       //b.me=e;
    726       //container.set(b);
    727       //}
    728       G.getFirst(first_false);
    729       NodeIt e_prev;
    730       for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
    731         container[e].prev=e_prev;
    732         if (e_prev.valid()) container[e_prev].next=e;
    733         e_prev=e;
    734       }
    735     }
    736     //NodeMap(const Graph& _G, T a) :
    737     //  G(_G), container(G.node_id, a) { }
    738     //FIXME
    739     void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
    740     T get(NodeIt nit) const { return container[G.id(nit)]; }
    741     //void update() { container.resize(G.node_id); }
    742     //void update(T a) { container.resize(G.node_id, a); }
    743   };
    744 */
    745759
    746760 

  • src/work/list_graph.hh

    r139 r148  
    303303    }
    304304
     305    bool valid(NodeIt n) const { return n.valid(); }
    305306    bool valid(EdgeIt e) const { return e.valid(); }
    306     bool valid(NodeIt n) const { return n.valid(); }
    307307   
    308308    template <typename It> It getNext(It it) const {

  • src/work/marci/graph_wrapper.h

    r105 r148  
    276276
    277277
    278 // FIXME: comparison should be made better!!!
    279   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
    280   class ResGraphWrapper
    281   {
    282     Graph* graph;
    283  
    284   public:
    285     typedef Graph BaseGraph;
    286 
    287     typedef typename Graph::NodeIt NodeIt;
    288     typedef typename Graph::EdgeIt EdgeIt;
    289  
    290     typedef typename Graph::EachNodeIt EachNodeIt;
     278
     279// // FIXME: comparison should be made better!!!
     280//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
     281//   class ResGraphWrapper
     282//   {
     283//     Graph* graph;
     284 
     285//   public:
     286//     typedef Graph BaseGraph;
     287
     288//     typedef typename Graph::NodeIt NodeIt;
     289//     typedef typename Graph::EdgeIt EdgeIt;
     290 
     291//     typedef typename Graph::EachNodeIt EachNodeIt;
    291292   
    292     class OutEdgeIt {
    293     public:
    294       //Graph::NodeIt n;
    295       bool out_or_in;
    296       typename Graph::OutEdgeIt o;
    297       typename Graph::InEdgeIt i;   
    298     };
    299     class InEdgeIt {
    300     public:
    301       //Graph::NodeIt n;
    302       bool out_or_in;
    303       typename Graph::OutEdgeIt o;
    304       typename Graph::InEdgeIt i;   
    305     };
    306     typedef typename Graph::SymEdgeIt SymEdgeIt;
    307     typedef typename Graph::EachEdgeIt EachEdgeIt;
    308 
    309     int nodeNum() const { return graph->nodeNum(); }
    310     int edgeNum() const { return graph->edgeNum(); }
    311 
    312     NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
    313 
    314     // EachEdge and SymEdge  is missing!!!!
    315     // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
    316 
    317     //FIXME
    318     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
    319       {
    320         e.n=n;
    321         graph->getFirst(e.o,n);
    322         while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
    323           graph->goNext(e.o);
    324         if(!graph->valid(e.o)) {
    325           graph->getFirst(e.i,n);
    326           while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
    327             graph->goNext(e.i);
    328         }
    329         return e;
    330       }
    331 /*
    332   OutEdgeIt &goNext(OutEdgeIt &e)
    333   {
    334   if(graph->valid(e.o)) {
    335   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
    336   graph->goNext(e.o);
    337   if(graph->valid(e.o)) return e;
    338   else graph->getFirst(e.i,e.n);
    339   }
    340   else {
    341   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
    342   graph->goNext(e.i);
    343   return e;
    344   }
    345   }
    346   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
    347 */
    348     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
    349 
    350     //FIXME
    351     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
    352       {
    353         e.n=n;
    354         graph->getFirst(e.i,n);
    355         while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
    356           graph->goNext(e.i);
    357         if(!graph->valid(e.i)) {
    358           graph->getFirst(e.o,n);
    359           while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
    360             graph->goNext(e.o);
    361         }
    362         return e;
    363       }
    364 /*
    365   InEdgeIt &goNext(InEdgeIt &e)
    366   {
    367   if(graph->valid(e.i)) {
    368   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
    369   graph->goNext(e.i);
    370   if(graph->valid(e.i)) return e;
    371   else graph->getFirst(e.o,e.n);
    372   }
    373   else {
    374   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
    375   graph->goNext(e.o);
    376   return e;
    377   }
    378   }
    379   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
    380 */
    381     //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
    382 
    383     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    384     //template<typename I> I next(const I i); { return graph->goNext(i); }
    385 
    386     template< typename It > It first() const {
    387       It e; getFirst(e); return e; }
    388 
    389     template< typename It > It first(NodeIt v) const {
    390       It e; getFirst(e, v); return e; }
    391 
    392     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    393     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
    394  
    395     template<typename I> NodeIt aNode(const I& e) const {
    396       return graph->aNode(e); }
    397     template<typename I> NodeIt bNode(const I& e) const {
    398       return graph->bNode(e); }
    399  
    400     //template<typename I> bool valid(const I i);
    401     //{ return graph->valid(i); }
    402  
    403     //template<typename I> void setInvalid(const I &i);
    404     //{ return graph->setInvalid(i); }
    405  
    406     NodeIt addNode() { return graph->addNode(); }
    407     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
    408       return graph->addEdge(tail, head); }
    409  
    410     template<typename I> void erase(const I& i) { graph->erase(i); }
    411  
    412     void clear() { graph->clear(); }
    413  
    414     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
    415     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
    416  
    417     void setGraph(Graph& _graph) { graph = &_graph; }
    418     Graph& getGraph() { return (*graph); }
    419 
    420     //ResGraphWrapper() : graph(0) { }
    421     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
    422   };
    423 
    424 
    425 // FIXME: comparison should be made better!!!
    426   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
    427   class ConstResGraphWrapper
    428   {
    429     const Graph* graph;
    430     const LowerMap* low;
    431     FlowMap* flow;
    432     const UpperMap* up;
    433   public:
    434     typedef Graph BaseGraph;
    435 
    436     typedef typename Graph::NodeIt NodeIt;
    437     typedef typename Graph::EdgeIt EdgeIt;
    438  
    439     typedef typename Graph::EachNodeIt EachNodeIt;
     293//     class OutEdgeIt {
     294//     public:
     295//       //Graph::NodeIt n;
     296//       bool out_or_in;
     297//       typename Graph::OutEdgeIt o;
     298//       typename Graph::InEdgeIt i;   
     299//     };
     300//     class InEdgeIt {
     301//     public:
     302//       //Graph::NodeIt n;
     303//       bool out_or_in;
     304//       typename Graph::OutEdgeIt o;
     305//       typename Graph::InEdgeIt i;   
     306//     };
     307//     typedef typename Graph::SymEdgeIt SymEdgeIt;
     308//     typedef typename Graph::EachEdgeIt EachEdgeIt;
     309
     310//     int nodeNum() const { return graph->nodeNum(); }
     311//     int edgeNum() const { return graph->edgeNum(); }
     312
     313//     NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
     314
     315//     // EachEdge and SymEdge  is missing!!!!
     316//     // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
     317
     318//     //FIXME
     319//     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
     320//       {
     321//      e.n=n;
     322//      graph->getFirst(e.o,n);
     323//      while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
     324//        graph->goNext(e.o);
     325//      if(!graph->valid(e.o)) {
     326//        graph->getFirst(e.i,n);
     327//        while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
     328//          graph->goNext(e.i);
     329//      }
     330//      return e;
     331//       }
     332// /*
     333//   OutEdgeIt &goNext(OutEdgeIt &e)
     334//   {
     335//   if(graph->valid(e.o)) {
     336//   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
     337//   graph->goNext(e.o);
     338//   if(graph->valid(e.o)) return e;
     339//   else graph->getFirst(e.i,e.n);
     340//   }
     341//   else {
     342//   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
     343//   graph->goNext(e.i);
     344//   return e;
     345//   }
     346//   }
     347//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
     348// */
     349//     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
     350
     351//     //FIXME
     352//     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
     353//       {
     354//      e.n=n;
     355//      graph->getFirst(e.i,n);
     356//      while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
     357//        graph->goNext(e.i);
     358//      if(!graph->valid(e.i)) {
     359//        graph->getFirst(e.o,n);
     360//        while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
     361//          graph->goNext(e.o);
     362//      }
     363//      return e;
     364//       }
     365// /*
     366//   InEdgeIt &goNext(InEdgeIt &e)
     367//   {
     368//   if(graph->valid(e.i)) {
     369//   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
     370//   graph->goNext(e.i);
     371//   if(graph->valid(e.i)) return e;
     372//   else graph->getFirst(e.o,e.n);
     373//   }
     374//   else {
     375//   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
     376//   graph->goNext(e.o);
     377//   return e;
     378//   }
     379//   }
     380//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
     381// */
     382//     //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
     383
     384//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
     385//     //template<typename I> I next(const I i); { return graph->goNext(i); }
     386
     387//     template< typename It > It first() const {
     388//       It e; getFirst(e); return e; }
     389
     390//     template< typename It > It first(NodeIt v) const {
     391//       It e; getFirst(e, v); return e; }
     392
     393//     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
     394//     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     395 
     396//     template<typename I> NodeIt aNode(const I& e) const {
     397//       return graph->aNode(e); }
     398//     template<typename I> NodeIt bNode(const I& e) const {
     399//       return graph->bNode(e); }
     400 
     401//     //template<typename I> bool valid(const I i);
     402//     //{ return graph->valid(i); }
     403 
     404//     //template<typename I> void setInvalid(const I &i);
     405//     //{ return graph->setInvalid(i); }
     406 
     407//     NodeIt addNode() { return graph->addNode(); }
     408//     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
     409//       return graph->addEdge(tail, head); }
     410 
     411//     template<typename I> void erase(const I& i) { graph->erase(i); }
     412 
     413//     void clear() { graph->clear(); }
     414 
     415//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
     416//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
     417 
     418//     void setGraph(Graph& _graph) { graph = &_graph; }
     419//     Graph& getGraph() { return (*graph); }
     420
     421//     //ResGraphWrapper() : graph(0) { }
     422//     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
     423//   };
     424
     425
     426// // FIXME: comparison should be made better!!!
     427//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
     428//   class ConstResGraphWrapper
     429//   {
     430//     const Graph* graph;
     431//     const LowerMap* low;
     432//     FlowMap* flow;
     433//     const UpperMap* up;
     434//   public:
     435//     typedef Graph BaseGraph;
     436
     437//     typedef typename Graph::NodeIt NodeIt;
     438//     typedef typename Graph::EdgeIt EdgeIt;
     439 
     440//     typedef typename Graph::EachNodeIt EachNodeIt;
    440441   
    441     class OutEdgeIt {
    442     public:
    443       //Graph::NodeIt n;
    444       bool out_or_in;
    445       typename Graph::SymEdgeIt sym;
    446     };
    447     class InEdgeIt {
    448     public:
    449       //Graph::NodeIt n;
    450       bool out_or_in;
    451       typename Graph::OutEdgeIt sym;
    452     };
    453     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    454     //typedef typename Graph::EachEdgeIt EachEdgeIt;
    455 
    456     int nodeNum() const { return graph->nodeNum(); }
    457     //int edgeNum() const { return graph->edgeNum(); }
    458 
    459     NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
    460 
    461     // EachEdge and SymEdge  is missing!!!!
    462     // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
     442//     class OutEdgeIt {
     443//     public:
     444//       //Graph::NodeIt n;
     445//       bool out_or_in;
     446//       typename Graph::SymEdgeIt sym;
     447//     };
     448//     class InEdgeIt {
     449//     public:
     450//       //Graph::NodeIt n;
     451//       bool out_or_in;
     452//       typename Graph::OutEdgeIt sym;
     453//     };
     454//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
     455//     //typedef typename Graph::EachEdgeIt EachEdgeIt;
     456
     457//     int nodeNum() const { return graph->nodeNum(); }
     458//     //int edgeNum() const { return graph->edgeNum(); }
     459
     460//     NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
     461
     462//     // EachEdge and SymEdge  is missing!!!!
     463//     // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
    463464
    464465   
    465     //FIXME
    466     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
    467       {
    468         e.n=n;
    469         graph->getFirst(e.o,n);
    470         while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
    471           graph->goNext(e.o);
    472         if(!graph->valid(e.o)) {
    473           graph->getFirst(e.i,n);
    474           while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
    475             graph->goNext(e.i);
    476         }
    477         return e;
    478       }
    479 /*
    480   OutEdgeIt &goNext(OutEdgeIt &e)
    481   {
    482   if(graph->valid(e.o)) {
    483   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
    484   graph->goNext(e.o);
    485   if(graph->valid(e.o)) return e;
    486   else graph->getFirst(e.i,e.n);
    487   }
    488   else {
    489   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
    490   graph->goNext(e.i);
    491   return e;
    492   }
    493   }
    494   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
    495 */
    496     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
    497 
    498     //FIXME
    499     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
    500       {
    501         e.n=n;
    502         graph->getFirst(e.i,n);
    503         while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
    504           graph->goNext(e.i);
    505         if(!graph->valid(e.i)) {
    506           graph->getFirst(e.o,n);
    507           while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
    508             graph->goNext(e.o);
    509         }
    510         return e;
    511       }
    512 /*
    513   InEdgeIt &goNext(InEdgeIt &e)
    514   {
    515   if(graph->valid(e.i)) {
    516   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
    517   graph->goNext(e.i);
    518   if(graph->valid(e.i)) return e;
    519   else graph->getFirst(e.o,e.n);
    520   }
    521   else {
    522   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
    523   graph->goNext(e.o);
    524   return e;
    525   }
    526   }
    527   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
    528 */
    529     //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
    530 
    531     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    532     //template<typename I> I next(const I i); { return graph->goNext(i); }
    533 
    534     template< typename It > It first() const {
    535       It e; getFirst(e); return e; }
    536 
    537     template< typename It > It first(NodeIt v) const {
    538       It e; getFirst(e, v); return e; }
    539 
    540     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    541     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
    542  
    543     template<typename I> NodeIt aNode(const I& e) const {
    544       return graph->aNode(e); }
    545     template<typename I> NodeIt bNode(const I& e) const {
    546       return graph->bNode(e); }
    547  
    548     //template<typename I> bool valid(const I i);
    549     //{ return graph->valid(i); }
    550  
    551     //template<typename I> void setInvalid(const I &i);
    552     //{ return graph->setInvalid(i); }
    553  
    554     NodeIt addNode() { return graph->addNode(); }
    555     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
    556       return graph->addEdge(tail, head); }
    557  
    558     template<typename I> void erase(const I& i) { graph->erase(i); }
    559  
    560     void clear() { graph->clear(); }
    561  
    562     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
    563     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
    564  
    565     void setGraph(const Graph& _graph) { graph = &_graph; }
    566     const Graph& getGraph() { return (*graph); }
    567 
    568     //ConstResGraphWrapper() : graph(0) { }
    569     ConstResGraphWrapper(const Graph& _graph) : graph(&_graph) { }
    570   };
     466//     //FIXME
     467//     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
     468//       {
     469//      e.n=n;
     470//      graph->getFirst(e.o,n);
     471//      while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
     472//        graph->goNext(e.o);
     473//      if(!graph->valid(e.o)) {
     474//        graph->getFirst(e.i,n);
     475//        while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
     476//          graph->goNext(e.i);
     477//      }
     478//      return e;
     479//       }
     480// /*
     481//   OutEdgeIt &goNext(OutEdgeIt &e)
     482//   {
     483//   if(graph->valid(e.o)) {
     484//   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
     485//   graph->goNext(e.o);
     486//   if(graph->valid(e.o)) return e;
     487//   else graph->getFirst(e.i,e.n);
     488//   }
     489//   else {
     490//   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
     491//   graph->goNext(e.i);
     492//   return e;
     493//   }
     494//   }
     495//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
     496// */
     497//     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
     498
     499//     //FIXME
     500//     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
     501//       {
     502//      e.n=n;
     503//      graph->getFirst(e.i,n);
     504//      while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
     505//        graph->goNext(e.i);
     506//      if(!graph->valid(e.i)) {
     507//        graph->getFirst(e.o,n);
     508//        while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
     509//          graph->goNext(e.o);
     510//      }
     511//      return e;
     512//       }
     513// /*
     514//   InEdgeIt &goNext(InEdgeIt &e)
     515//   {
     516//   if(graph->valid(e.i)) {
     517//   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
     518//   graph->goNext(e.i);
     519//   if(graph->valid(e.i)) return e;
     520//   else graph->getFirst(e.o,e.n);
     521//   }
     522//   else {
     523//   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
     524//   graph->goNext(e.o);
     525//   return e;
     526//   }
     527//   }
     528//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
     529// */
     530//     //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
     531
     532//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
     533//     //template<typename I> I next(const I i); { return graph->goNext(i); }
     534
     535//     template< typename It > It first() const {
     536//       It e; getFirst(e); return e; }
     537
     538//     template< typename It > It first(NodeIt v) const {
     539//       It e; getFirst(e, v); return e; }
     540
     541//     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
     542//     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     543 
     544//     template<typename I> NodeIt aNode(const I& e) const {
     545//       return graph->aNode(e); }
     546//     template<typename I> NodeIt bNode(const I& e) const {
     547//       return graph->bNode(e); }
     548 
     549//     //template<typename I> bool valid(const I i);
     550//     //{ return graph->valid(i); }
     551 
     552//     //template<typename I> void setInvalid(const I &i);
     553//     //{ return graph->setInvalid(i); }
     554 
     555//     NodeIt addNode() { return graph->addNode(); }
     556//     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
     557//       return graph->addEdge(tail, head); }
     558 
     559//     template<typename I> void erase(const I& i) { graph->erase(i); }
     560 
     561//     void clear() { graph->clear(); }
     562 
     563//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
     564//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
     565 
     566//     void setGraph(const Graph& _graph) { graph = &_graph; }
     567//     const Graph& getGraph() { return (*graph); }
     568
     569//     //ConstResGraphWrapper() : graph(0) { }
     570//     ConstResGraphWrapper(const Graph& _graph) : graph(&_graph) { }
     571//   };
    571572
    572573
Note: See TracChangeset for help on using the changeset viewer.