COIN-OR::LEMON - Graph Library

Changeset 75:87623302a68f in lemon-0.x for src/work


Ignore:
Timestamp:
02/16/04 12:29:48 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@98
Message:

.

Location:
src/work
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed
  • src/work/bfs_iterator.hh

    r64 r75  
    44#include <queue>
    55#include <stack>
     6#include <utility>
     7#include <graph_wrapper.h>
    68
    79namespace marci {
     
    467469 };
    468470
     471
     472  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
     473  class BfsIterator3 {
     474    typedef typename Graph::NodeIt NodeIt;
     475    const Graph& G;
     476    std::queue< std::pair<NodeIt, OutEdgeIt> > bfs_queue;
     477    ReachedMap reached;
     478    bool b_node_newly_reached;
     479    OutEdgeIt actual_edge;
     480  public:
     481    BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
     482    void pushAndSetReached(NodeIt s) {
     483      reached.set(s, true);
     484      if (bfs_queue.empty()) {
     485        bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
     486        actual_edge=bfs_queue.front().second;
     487        if (actual_edge.valid()) {
     488          NodeIt w=G.bNode(actual_edge);
     489          if (!reached.get(w)) {
     490            bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
     491            reached.set(w, true);
     492            b_node_newly_reached=true;
     493          } else {
     494            b_node_newly_reached=false;
     495          }
     496        } //else {
     497        //}
     498      } else {
     499        bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
     500      }
     501    }
     502    BfsIterator3<Graph, OutEdgeIt, ReachedMap>&
     503    operator++() {
     504      if (bfs_queue.front().second.valid()) {
     505        ++(bfs_queue.front().second);
     506        actual_edge=bfs_queue.front().second;
     507        if (actual_edge.valid()) {
     508          NodeIt w=G.bNode(actual_edge);
     509          if (!reached.get(w)) {
     510            bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
     511            reached.set(w, true);
     512            b_node_newly_reached=true;
     513          } else {
     514            b_node_newly_reached=false;
     515          }
     516        }
     517      } else {
     518        bfs_queue.pop();
     519        if (!bfs_queue.empty()) {
     520          actual_edge=bfs_queue.front().second;
     521          if (actual_edge.valid()) {
     522            NodeIt w=G.bNode(actual_edge);
     523            if (!reached.get(w)) {
     524              bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
     525              reached.set(w, true);
     526              b_node_newly_reached=true;
     527            } else {
     528              b_node_newly_reached=false;
     529            }
     530          }
     531        }
     532      }
     533      return *this;
     534    }
     535    bool finished() const { return bfs_queue.empty(); }
     536    operator OutEdgeIt () const { return actual_edge; }
     537    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     538    bool isANodeExamined() const { return !(actual_edge.valid()); }
     539    NodeIt aNode() const { return bfs_queue.front().first; }
     540    NodeIt bNode() const { return G.bNode(actual_edge); }
     541    const ReachedMap& getReachedMap() const { return reached; }
     542    //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
     543 };
     544
     545  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
     546  class BfsIterator4 {
     547    typedef typename Graph::NodeIt NodeIt;
     548    const Graph& G;
     549    std::queue<NodeIt> bfs_queue;
     550    ReachedMap reached;
     551    bool b_node_newly_reached;
     552    OutEdgeIt actual_edge;
     553  public:
     554    BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { }
     555    void pushAndSetReached(NodeIt s) {
     556      reached.set(s, true);
     557      if (bfs_queue.empty()) {
     558        bfs_queue.push(s);
     559        G.getFirst(actual_edge, s);
     560        if (actual_edge.valid()) {
     561          NodeIt w=G.bNode(actual_edge);
     562          if (!reached.get(w)) {
     563            bfs_queue.push(w);
     564            reached.set(w, true);
     565            b_node_newly_reached=true;
     566          } else {
     567            b_node_newly_reached=false;
     568          }
     569        }
     570      } else {
     571        bfs_queue.push(s);
     572      }
     573    }
     574    BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
     575    operator++() {
     576      if (actual_edge.valid()) {
     577        ++actual_edge;
     578        if (actual_edge.valid()) {
     579          NodeIt w=G.bNode(actual_edge);
     580          if (!reached.get(w)) {
     581            bfs_queue.push(w);
     582            reached.set(w, true);
     583            b_node_newly_reached=true;
     584          } else {
     585            b_node_newly_reached=false;
     586          }
     587        }
     588      } else {
     589        bfs_queue.pop();
     590        if (!bfs_queue.empty()) {
     591          G.getFirst(actual_edge, bfs_queue.front());
     592          if (actual_edge.valid()) {
     593            NodeIt w=G.bNode(actual_edge);
     594            if (!reached.get(w)) {
     595              bfs_queue.push(w);
     596              reached.set(w, true);
     597              b_node_newly_reached=true;
     598            } else {
     599              b_node_newly_reached=false;
     600            }
     601          }
     602        }
     603      }
     604      return *this;
     605    }
     606    bool finished() const { return bfs_queue.empty(); }
     607    operator OutEdgeIt () const { return actual_edge; }
     608    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     609    bool isANodeExamined() const { return !(actual_edge.valid()); }
     610    NodeIt aNode() const { return bfs_queue.front(); }
     611    NodeIt bNode() const { return G.bNode(actual_edge); }
     612    const ReachedMap& getReachedMap() const { return reached; }
     613    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
     614 };
     615
     616
     617  template <typename GraphWrapper, typename ReachedMap>
     618  class BfsIterator5 {
     619    typedef typename GraphWrapper::NodeIt NodeIt;
     620    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
     621    GraphWrapper gw;
     622    std::queue<NodeIt> bfs_queue;
     623    ReachedMap reached;
     624    bool b_node_newly_reached;
     625    OutEdgeIt actual_edge;
     626  public:
     627    BfsIterator5(GraphWrapper _gw) :
     628      gw(_gw), reached(_gw.getGraph()) { }
     629    void pushAndSetReached(NodeIt s) {
     630      reached.set(s, true);
     631      if (bfs_queue.empty()) {
     632        bfs_queue.push(s);
     633        gw.getFirst(actual_edge, s);
     634        if (actual_edge.valid()) {
     635          NodeIt w=gw.bNode(actual_edge);
     636          if (!reached.get(w)) {
     637            bfs_queue.push(w);
     638            reached.set(w, true);
     639            b_node_newly_reached=true;
     640          } else {
     641            b_node_newly_reached=false;
     642          }
     643        }
     644      } else {
     645        bfs_queue.push(s);
     646      }
     647    }
     648    BfsIterator5<GraphWrapper, ReachedMap>&
     649    operator++() {
     650      if (actual_edge.valid()) {
     651        ++actual_edge;
     652        if (actual_edge.valid()) {
     653          NodeIt w=gw.bNode(actual_edge);
     654          if (!reached.get(w)) {
     655            bfs_queue.push(w);
     656            reached.set(w, true);
     657            b_node_newly_reached=true;
     658          } else {
     659            b_node_newly_reached=false;
     660          }
     661        }
     662      } else {
     663        bfs_queue.pop();
     664        if (!bfs_queue.empty()) {
     665          gw.getFirst(actual_edge, bfs_queue.front());
     666          if (actual_edge.valid()) {
     667            NodeIt w=gw.bNode(actual_edge);
     668            if (!reached.get(w)) {
     669              bfs_queue.push(w);
     670              reached.set(w, true);
     671              b_node_newly_reached=true;
     672            } else {
     673              b_node_newly_reached=false;
     674            }
     675          }
     676        }
     677      }
     678      return *this;
     679    }
     680    bool finished() const { return bfs_queue.empty(); }
     681    operator OutEdgeIt () const { return actual_edge; }
     682    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     683    bool isANodeExamined() const { return !(actual_edge.valid()); }
     684    NodeIt aNode() const { return bfs_queue.front(); }
     685    NodeIt bNode() const { return gw.bNode(actual_edge); }
     686    const ReachedMap& getReachedMap() const { return reached; }
     687    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
     688 };
     689
     690
     691
    469692} // namespace marci
    470693
  • src/work/edmonds_karp.hh

    r69 r75  
    33
    44#include <algorithm>
     5#include <list>
     6#include <iterator>
    57
    68#include <bfs_iterator.hh>
     
    810namespace marci {
    911
    10   template<typename Graph, typename T, typename FlowMap, typename CapacityMap>
     12  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    1113  class ResGraph {
    1214    typedef typename Graph::NodeIt NodeIt;
     
    2729
    2830    class EdgeIt {
    29       friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
     31      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
    3032    protected:
    31       const ResGraph<Graph, T, FlowMap, CapacityMap>* resG;
     33      const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
    3234      OldSymEdgeIt sym;
    3335    public:
    3436      EdgeIt() { }
    3537      //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
    36       T free() const {
     38      Number free() const {
    3739        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
    3840          return (resG->capacity.get(sym)-resG->flow.get(sym));
     
    4244      }
    4345      bool valid() const { return sym.valid(); }
    44       void augment(T a) const {
     46      void augment(Number a) const {
    4547        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
    4648          resG->flow.set(sym, resG->flow.get(sym)+a);
     49          //resG->flow[sym]+=a;
    4750        } else {
    4851          resG->flow.set(sym, resG->flow.get(sym)-a);
     52          //resG->flow[sym]-=a;
    4953        }
    5054      }
     
    5256
    5357    class OutEdgeIt : public EdgeIt {
    54       friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
     58      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
    5559    public:
    5660      OutEdgeIt() { }
    5761      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
    5862    private:
    59       OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, NodeIt v) {
     63      OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
    6064        resG=&_resG;
    6165        sym=resG->G.template first<OldSymEdgeIt>(v);
     
    6670        ++sym;
    6771        while( sym.valid() && !(free()>0) ) { ++sym; }
     72        return *this;
     73      }
     74    };
     75
     76    void getFirst(OutEdgeIt& e, NodeIt v) const {
     77      e=OutEdgeIt(*this, v);
     78    }
     79    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
     80   
     81    template< typename It >
     82    It first() const {
     83      It e;     
     84      getFirst(e);
     85      return e;
     86    }
     87
     88    template< typename It >
     89    It first(NodeIt v) const {
     90      It e;
     91      getFirst(e, v);
     92      return e;
     93    }
     94
     95    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
     96    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
     97
     98    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
     99    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
     100
     101    int id(NodeIt v) const { return G.id(v); }
     102
     103    template <typename S>
     104    class NodeMap {
     105      typename Graph::NodeMap<S> node_map;
     106    public:
     107      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
     108      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
     109      void set(NodeIt nit, S a) { node_map.set(nit, a); }
     110      S get(NodeIt nit) const { return node_map.get(nit); }
     111      S& operator[](NodeIt nit) { return node_map[nit]; }
     112      const S& operator[](NodeIt nit) const { return node_map[nit]; }
     113    };
     114
     115  };
     116
     117
     118  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     119  class ResGraph2 {
     120    typedef typename Graph::NodeIt NodeIt;
     121    typedef typename Graph::EachNodeIt EachNodeIt;
     122    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
     123    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
     124    typedef typename Graph::InEdgeIt OldInEdgeIt;
     125   
     126    const Graph& G;
     127    FlowMap& flow;
     128    const CapacityMap& capacity;
     129  public:
     130    ResGraph2(const Graph& _G, FlowMap& _flow,
     131             const CapacityMap& _capacity) :
     132      G(_G), flow(_flow), capacity(_capacity) { }
     133
     134    class EdgeIt;
     135    class OutEdgeIt;
     136    friend class EdgeIt;
     137    friend class OutEdgeIt;
     138
     139    class EdgeIt {
     140      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
     141    protected:
     142      const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
     143      //OldSymEdgeIt sym;
     144      OldOutEdgeIt out;
     145      OldInEdgeIt in;
     146      bool out_or_in; //1, iff out
     147    public:
     148      EdgeIt() : out_or_in(1) { }
     149      Number free() const {
     150        if (out_or_in) {
     151          return (resG->capacity.get(out)-resG->flow.get(out));
     152        } else {
     153          return (resG->flow.get(in));
     154        }
     155      }
     156      bool valid() const {
     157        return out_or_in && out.valid() || in.valid(); }
     158      void augment(Number a) const {
     159        if (out_or_in) {
     160          resG->flow.set(out, resG->flow.get(out)+a);
     161        } else {
     162          resG->flow.set(in, resG->flow.get(in)-a);
     163        }
     164      }
     165    };
     166
     167    class OutEdgeIt : public EdgeIt {
     168      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
     169    public:
     170      OutEdgeIt() { }
     171    private:
     172      OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
     173        resG=&_resG;
     174        out=resG->G.template first<OldOutEdgeIt>(v);
     175        while( out.valid() && !(free()>0) ) { ++out; }
     176        if (!out.valid()) {
     177          out_or_in=0;
     178          in=resG->G.template first<OldInEdgeIt>(v);
     179          while( in.valid() && !(free()>0) ) { ++in; }
     180        }
     181      }
     182    public:
     183      OutEdgeIt& operator++() {
     184        if (out_or_in) {
     185          NodeIt v=resG->G.aNode(out);
     186          ++out;
     187          while( out.valid() && !(free()>0) ) { ++out; }
     188          if (!out.valid()) {
     189            out_or_in=0;
     190            in=resG->G.template first<OldInEdgeIt>(v);
     191            while( in.valid() && !(free()>0) ) { ++in; }
     192          }
     193        } else {
     194          ++in;
     195          while( in.valid() && !(free()>0) ) { ++in; }
     196        }
    68197        return *this;
    69198      }
     
    89218    }
    90219
    91     NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
    92     NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
    93 
    94     NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
    95     NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
     220    NodeIt tail(EdgeIt e) const {
     221      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
     222    NodeIt head(EdgeIt e) const {
     223      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
     224
     225    NodeIt aNode(OutEdgeIt e) const {
     226      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
     227    NodeIt bNode(OutEdgeIt e) const {
     228      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
    96229
    97230    int id(NodeIt v) const { return G.id(v); }
     
    101234      typename Graph::NodeMap<S> node_map;
    102235    public:
    103       NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
    104       NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
     236      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
     237      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
    105238      void set(NodeIt nit, S a) { node_map.set(nit, a); }
    106239      S get(NodeIt nit) const { return node_map.get(nit); }
    107240    };
    108 
    109241  };
    110242
    111   template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
     243  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     244  class ResGraph3 {
     245    typedef typename Graph::NodeIt NodeIt;
     246    typedef typename Graph::EachNodeIt EachNodeIt;
     247    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
     248    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
     249    typedef typename Graph::InEdgeIt OldInEdgeIt;
     250   
     251    const Graph& G;
     252    FlowMap& flow;
     253    const CapacityMap& capacity;
     254  public:
     255    ResGraph3(const Graph& _G, FlowMap& _flow,
     256             const CapacityMap& _capacity) :
     257      G(_G), flow(_flow), capacity(_capacity) { }
     258
     259    class EdgeIt;
     260    class OutEdgeIt;
     261    friend class EdgeIt;
     262    friend class OutEdgeIt;
     263
     264    class EdgeIt {
     265      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
     266    protected:
     267      //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
     268      const Graph* G;
     269      FlowMap* flow;
     270      const CapacityMap* capacity;
     271      //OldSymEdgeIt sym;
     272      OldOutEdgeIt out;
     273      OldInEdgeIt in;
     274      bool out_or_in; //1, iff out
     275    public:
     276      EdgeIt() : out_or_in(1) { }
     277      Number free() const {
     278        if (out_or_in) {
     279          return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
     280        } else {
     281          return (/*resG->*/flow->get(in));
     282        }
     283      }
     284      bool valid() const {
     285        return out_or_in && out.valid() || in.valid(); }
     286      void augment(Number a) const {
     287        if (out_or_in) {
     288          /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
     289        } else {
     290          /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
     291        }
     292      }
     293    };
     294
     295    class OutEdgeIt : public EdgeIt {
     296      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
     297    public:
     298      OutEdgeIt() { }
     299    private:
     300      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) {
     301        G=&_G;
     302        flow=&_flow;
     303        capacity=&_capacity;
     304        out=/*resG->*/G->template first<OldOutEdgeIt>(v);
     305        while( out.valid() && !(free()>0) ) { ++out; }
     306        if (!out.valid()) {
     307          out_or_in=0;
     308          in=/*resG->*/G->template first<OldInEdgeIt>(v);
     309          while( in.valid() && !(free()>0) ) { ++in; }
     310        }
     311      }
     312    public:
     313      OutEdgeIt& operator++() {
     314        if (out_or_in) {
     315          NodeIt v=/*resG->*/G->aNode(out);
     316          ++out;
     317          while( out.valid() && !(free()>0) ) { ++out; }
     318          if (!out.valid()) {
     319            out_or_in=0;
     320            in=/*resG->*/G->template first<OldInEdgeIt>(v);
     321            while( in.valid() && !(free()>0) ) { ++in; }
     322          }
     323        } else {
     324          ++in;
     325          while( in.valid() && !(free()>0) ) { ++in; }
     326        }
     327        return *this;
     328      }
     329    };
     330
     331    void getFirst(OutEdgeIt& e, NodeIt v) const {
     332      e=OutEdgeIt(G, v, flow, capacity);
     333    }
     334    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
     335   
     336    template< typename It >
     337    It first() const {
     338      It e;
     339      getFirst(e);
     340      return e;
     341    }
     342
     343    template< typename It >
     344    It first(NodeIt v) const {
     345      It e;
     346      getFirst(e, v);
     347      return e;
     348    }
     349
     350    NodeIt tail(EdgeIt e) const {
     351      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
     352    NodeIt head(EdgeIt e) const {
     353      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
     354
     355    NodeIt aNode(OutEdgeIt e) const {
     356      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
     357    NodeIt bNode(OutEdgeIt e) const {
     358      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
     359
     360    int id(NodeIt v) const { return G.id(v); }
     361
     362    template <typename S>
     363    class NodeMap {
     364      typename Graph::NodeMap<S> node_map;
     365    public:
     366      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
     367      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
     368      void set(NodeIt nit, S a) { node_map.set(nit, a); }
     369      S get(NodeIt nit) const { return node_map.get(nit); }
     370    };
     371
     372  };
     373
     374
     375  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    112376  class MaxFlow {
    113377    typedef typename Graph::NodeIt NodeIt;
     
    121385    FlowMap& flow;
    122386    const CapacityMap& capacity;
    123     typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph;
     387    typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
    124388    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    125389    typedef typename AugGraph::EdgeIt AugEdgeIt;
     390
     391    //AugGraph res_graph;   
     392    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
     393    //typename AugGraph::NodeMap<AugEdgeIt> pred;
     394    //typename AugGraph::NodeMap<int> free;
    126395  public:
    127     MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
     396    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
     397      G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //, 
     398      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
     399      { }
    128400    bool augment() {
    129401      AugGraph res_graph(G, flow, capacity);
     
    131403     
    132404      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    133       BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
     405      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
    134406      res_bfs.pushAndSetReached(s);
    135407       
    136408      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
    137       //filled with invalid iterators
     409      //filled up with invalid iterators
     410      //pred.set(s, AugEdgeIt());
    138411     
    139412      typename AugGraph::NodeMap<int> free(res_graph);
     
    159432      if (_augment) {
    160433        NodeIt n=t;
    161         T augment_value=free.get(t);
     434        Number augment_value=free.get(t);
    162435        while (pred.get(n).valid()) {
    163436          AugEdgeIt e=pred.get(n);
     
    172445      while (augment()) { }
    173446    }
    174     T flowValue() {
    175       T a=0;
     447    Number flowValue() {
     448      Number a=0;
    176449      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
    177450        a+=flow.get(i);
     
    181454  };
    182455
     456
     457/*
     458  template <typename Graph>
     459  class IteratorBoolNodeMap {
     460    typedef typename Graph::NodeIt NodeIt;
     461    typedef typename Graph::EachNodeIt EachNodeIt;
     462    class BoolItem {
     463    public:
     464      bool value;
     465      NodeIt prev;
     466      NodeIt next;
     467      BoolItem() : value(false), prev(), next() {}
     468    };
     469    NodeIt first_true;
     470    //NodeIt last_true;
     471    NodeIt first_false;
     472    //NodeIt last_false;
     473    const Graph& G;
     474    typename Graph::NodeMap<BoolItem> container;
     475  public:
     476    typedef bool ValueType;
     477    typedef NodeIt KeyType;
     478    IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {
     479      //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
     480      //BoolItem b=container.get(e);
     481      //b.me=e;
     482      //container.set(b);
     483      //}
     484      G.getFirst(first_false);
     485      NodeIt e_prev;
     486      for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
     487        container[e].prev=e_prev;
     488        if (e_prev.valid()) container[e_prev].next=e;
     489        e_prev=e;
     490      }
     491    }
     492    //NodeMap(const Graph& _G, T a) :
     493    //  G(_G), container(G.node_id, a) { }
     494    //FIXME
     495    void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
     496    T get(NodeIt nit) const { return container[G.id(nit)]; }
     497    //void resize() { container.resize(G.node_id); }
     498    //void resize(T a) { container.resize(G.node_id, a); }
     499  };
     500*/
     501
     502 
     503  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     504  class MaxFlow2 {
     505    typedef typename Graph::NodeIt NodeIt;
     506    typedef typename Graph::EdgeIt EdgeIt;
     507    typedef typename Graph::EachEdgeIt EachEdgeIt;
     508    typedef typename Graph::OutEdgeIt OutEdgeIt;
     509    typedef typename Graph::InEdgeIt InEdgeIt;
     510    const Graph& G;
     511    std::list<NodeIt>& S;
     512    std::list<NodeIt>& T;
     513    FlowMap& flow;
     514    const CapacityMap& capacity;
     515    typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
     516    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
     517    typedef typename AugGraph::EdgeIt AugEdgeIt;
     518    typename Graph::NodeMap<bool> SMap;
     519    typename Graph::NodeMap<bool> TMap;
     520  public:
     521    MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
     522      for(typename std::list<NodeIt>::const_iterator i=S.begin();
     523          i!=S.end(); ++i) {
     524        SMap.set(*i, true);
     525      }
     526      for (typename std::list<NodeIt>::const_iterator i=T.begin();
     527           i!=T.end(); ++i) {
     528        TMap.set(*i, true);
     529      }
     530    }
     531    bool augment() {
     532      AugGraph res_graph(G, flow, capacity);
     533      bool _augment=false;
     534      NodeIt reached_t_node;
     535     
     536      typedef typename AugGraph::NodeMap<bool> ReachedMap;
     537      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
     538      for(typename std::list<NodeIt>::const_iterator i=S.begin();
     539          i!=S.end(); ++i) {
     540        res_bfs.pushAndSetReached(*i);
     541      }
     542      //res_bfs.pushAndSetReached(s);
     543       
     544      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
     545      //filled up with invalid iterators
     546     
     547      typename AugGraph::NodeMap<int> free(res_graph);
     548       
     549      //searching for augmenting path
     550      while ( !res_bfs.finished() ) {
     551        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
     552        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
     553          NodeIt v=res_graph.tail(e);
     554          NodeIt w=res_graph.head(e);
     555          pred.set(w, e);
     556          if (pred.get(v).valid()) {
     557            free.set(w, std::min(free.get(v), e.free()));
     558          } else {
     559            free.set(w, e.free());
     560          }
     561          if (TMap.get(res_graph.head(e))) {
     562            _augment=true;
     563            reached_t_node=res_graph.head(e);
     564            break;
     565          }
     566        }
     567       
     568        ++res_bfs;
     569      } //end of searching augmenting path
     570
     571      if (_augment) {
     572        NodeIt n=reached_t_node;
     573        Number augment_value=free.get(reached_t_node);
     574        while (pred.get(n).valid()) {
     575          AugEdgeIt e=pred.get(n);
     576          e.augment(augment_value);
     577          n=res_graph.tail(e);
     578        }
     579      }
     580
     581      return _augment;
     582    }
     583    void run() {
     584      while (augment()) { }
     585    }
     586    Number flowValue() {
     587      Number a=0;
     588      for(typename std::list<NodeIt>::const_iterator i=S.begin();
     589          i!=S.end(); ++i) {
     590        for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
     591          a+=flow.get(e);
     592        }
     593        for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
     594          a-=flow.get(e);
     595        }
     596      }
     597      return a;
     598    }
     599  };
     600
     601
     602
    183603} // namespace marci
    184604
  • src/work/list_graph.hh

    r69 r75  
    4545      NodeMap(const ListGraph& _G, T a) :
    4646        G(_G), container(G.node_id, a) { }
    47       void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
    48       T get(NodeIt nit) const { return container[G.id(nit)]; }
     47      void set(NodeIt n, T a) { container[/*G.id(n)*/n.node->id]=a; }
     48      T get(NodeIt n) const { return container[/*G.id(n)*/n.node->id]; }
     49      T& operator[](NodeIt n) { return container[/*G.id(n)*/n.node->id]; }
     50      const T& operator[](NodeIt n) const { return container[/*G.id(n)*/n.node->id]; }
    4951      void resize() { container.resize(G.node_id); }
    5052      void resize(T a) { container.resize(G.node_id, a); }
     
    6163      EdgeMap(const ListGraph& _G, T a) :
    6264        G(_G), container(G.edge_id, a) { }
    63       void set(EdgeIt eit, T a) { container[G.id(eit)]=a; }
    64       T get(EdgeIt eit) const { return container[G.id(eit)]; }
     65      void set(EdgeIt e, T a) { container[/*G.id(e)*/e.edge->id]=a; }
     66      T get(EdgeIt e) const { return container[/*G.id(e)*/e.edge->id]; }
     67      T& operator[](EdgeIt e) { return container[/*G.id(e)*/e.edge->id]; }
     68      const T& operator[](EdgeIt e) const { return container[/*G.id(e)*/e.edge->id]; }
    6569      void resize() { container.resize(G.edge_id); }
    6670      void resize(T a) { container.resize(G.edge_id, a); }
     
    7781    class node_item {
    7882      friend class ListGraph;
     83      template <typename T> friend class NodeMap;
     84     
    7985      friend class NodeIt;
    8086      friend class EachNodeIt;
     
    100106    class edge_item {
    101107      friend class ListGraph;
     108      template <typename T> friend class EdgeMap;
     109
    102110      friend class NodeIt;
    103111      friend class EachNodeIt;
     
    255263    /* for experimental purpose */
    256264
    257     void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); }
    258     void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); }
    259     void getFirst(OutEdgeIt& e, NodeIt v) const { e=OutEdgeIt(v); }
    260     void getFirst(InEdgeIt& e, NodeIt v) const { e=InEdgeIt(v); }
    261     void getFirst(SymEdgeIt& e, NodeIt v) const { e=SymEdgeIt(v); }
     265    EachNodeIt& getFirst(EachNodeIt& v) const {
     266      v=EachNodeIt(*this); return v; }
     267    EachEdgeIt& getFirst(EachEdgeIt& e) const {
     268      e=EachEdgeIt(*this); return e; }
     269    OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const {
     270      e=OutEdgeIt(v); return e; }
     271    InEdgeIt& getFirst(InEdgeIt& e, NodeIt v) const {
     272      e=InEdgeIt(v); return e; }
     273    SymEdgeIt& getFirst(SymEdgeIt& e, NodeIt v) const {
     274      e=SymEdgeIt(v); return e; }
    262275    //void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); }
    263276    //void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); }
     
    334347    class NodeIt {
    335348      friend class ListGraph;
     349      template <typename T> friend class NodeMap;
    336350
    337351      friend class EdgeIt;
     
    368382    class EdgeIt {
    369383      friend class ListGraph;
     384      template <typename T> friend class EdgeMap;
    370385     
    371386      friend class NodeIt;
     
    414429    class OutEdgeIt : public EdgeIt {
    415430      friend class ListGraph;
    416       node_item* v;
    417     protected:
    418       OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
    419     public:
    420       OutEdgeIt() : EdgeIt(), v(0) { }
    421       OutEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
     431      //node_item* v;
     432    protected:
     433      OutEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
     434    public:
     435      OutEdgeIt() : EdgeIt()/*, v(0)*/ { }
     436      OutEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
    422437      OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
    423438    protected:
    424       NodeIt aNode() const { return NodeIt(v); }
    425       NodeIt bNode() const {
    426         return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }
     439      NodeIt aNode() const { return NodeIt(edge->_tail); }
     440      NodeIt bNode() const { return NodeIt(edge->_head); }
    427441    };
    428442   
    429443    class InEdgeIt : public EdgeIt {
    430444      friend class ListGraph;
    431       node_item* v;
    432     protected:
    433       InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_in_edge; }
    434     public:
    435       InEdgeIt() : EdgeIt(), v(0) { }
    436       InEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
     445      //node_item* v;
     446    protected:
     447      InEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
     448    public:
     449      InEdgeIt() : EdgeIt()/*, v(0)*/ { }
     450      InEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
    437451      InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
    438452    protected:
    439       NodeIt aNode() const { return NodeIt(v); }
    440       NodeIt bNode() const {
    441         return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }
     453      NodeIt aNode() const { return NodeIt(edge->_head); }
     454      NodeIt bNode() const { return NodeIt(edge->_tail); }
    442455    };
    443456
     
    445458      friend class ListGraph;
    446459      bool out_or_in; //1 iff out, 0 iff in
    447       node_item* v;
    448     protected:
    449       SymEdgeIt(const NodeIt& _v) : v(_v.node) {
     460      //node_item* v;
     461    protected:
     462      SymEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ {
    450463        out_or_in=1;
    451         edge=v->_first_out_edge;
    452         if (!edge) { edge=v->_first_in_edge; out_or_in=0; }
     464        edge=_v.node->_first_out_edge;
     465        if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
    453466      }
    454467    public:
    455       SymEdgeIt() : EdgeIt(), v(0) { }
    456       SymEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) {
     468      SymEdgeIt() : EdgeIt() /*, v(0)*/ { }
     469      SymEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ {
    457470        out_or_in=1;
    458         edge=v->_first_out_edge;
    459         if (!edge) { edge=v->_first_in_edge; out_or_in=0; }
     471        edge=_v.node->_first_out_edge;
     472        if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
    460473      }
    461474      SymEdgeIt& operator++() {
    462475        if (out_or_in) {
     476          node_item* v=edge->_tail;
    463477          edge=edge->_next_out;
    464478          if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
     
    469483      }
    470484    protected:
    471       NodeIt aNode() const { return NodeIt(v); }
     485      NodeIt aNode() const {
     486        return (out_or_in) ? NodeIt(edge->_tail) : NodeIt(edge->_head); }
    472487      NodeIt bNode() const {
    473         return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }
     488        return (out_or_in) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }
    474489    };
    475490
  • src/work/marci_graph_demo.cc

    r69 r75  
    9595  }
    9696  std::cout << std::endl;
    97 
     97/*
    9898  std::cout << "bfs from the first node" << std::endl;
    9999  bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
     
    109109  }
    110110  std::cout<<std::endl;
    111 
     111*/
    112112
    113113  std::cout << "augmenting path flow algorithm test..." << std::endl;
     
    174174  //flowG.setTail(v3_t, v2);
    175175  //flowG.setHead(v3_t, s);
    176 
     176/*
    177177  for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
    178178    std::cout << node_name.get(i) << ": ";
     
    189189    std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
    190190  }
    191 
     191*/
    192192  /*
    193193  while (flowG.first<EachEdgeIt>().valid()) {
     
    220220  */
    221221
    222   std::cout << std::endl;
    223   //std::cout << "meg jo" << std::flush;
    224 
    225   ListGraph::EdgeMap<int> flow(flowG, 0);
    226   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
    227   max_flow_test.run();
    228 
    229   std::cout << "maximum flow: "<< std::endl;
    230   for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
    231     std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
    232   }
    233   std::cout<<std::endl;
    234   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     222  //std::cout << std::endl;
     223
     224
     225  {
     226    ListGraph::EdgeMap<int> flow(flowG, 0);
     227    MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
     228    max_flow_test.run();
     229   
     230    std::cout << "maximum flow: "<< std::endl;
     231    for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
     232      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
     233    }
     234    std::cout<<std::endl;
     235    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     236  }
     237
     238  {
     239    std::list<NodeIt> S;
     240    S.push_back(s); S.push_back(v3);
     241    std::list<NodeIt> T;
     242    T.push_back(t);
     243
     244    ListGraph::EdgeMap<int> flow(flowG, 0);
     245    MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap);
     246    max_flow_test.run();
     247   
     248    std::cout << "maximum flow: "<< std::endl;
     249    for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
     250      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
     251    }
     252    std::cout<<std::endl;
     253    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     254  }
    235255
    236256  return 0;
Note: See TracChangeset for help on using the changeset viewer.