COIN-OR::LEMON - Graph Library

Changeset 466:cd40ecf4d2a9 in lemon-0.x


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

preflow, maxflow comp

Location:
src/work
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/preflow.h

    r465 r466  
    6060    typedef typename std::vector<Node> VecNode;
    6161
    62     const Graph& G;
     62    const Graph* g;
    6363    Node s;
    6464    Node t;
     
    8080    Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
    8181            FlowMap& _flow) :
    82       G(_G), s(_s), t(_t), capacity(&_capacity),
     82      g(&_G), s(_s), t(_t), capacity(&_capacity),
    8383      flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
    8484
     
    110110      VecStack active(n);
    111111     
    112       NNMap left(G,INVALID);
    113       NNMap right(G,INVALID);
     112      NNMap left(*g, INVALID);
     113      NNMap right(*g, INVALID);
    114114      VecNode level_list(n,INVALID);
    115115      //List of the nodes in level i<n, set to n.
    116116
    117117      NodeIt v;
    118       for(G.first(v); G.valid(v); G.next(v)) level.set(v,n);
     118      for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
    119119      //setting each node to level n
    120120     
     
    124124          //counting the excess
    125125          NodeIt v;
    126           for(G.first(v); G.valid(v); G.next(v)) {
     126          for(g->first(v); g->valid(v); g->next(v)) {
    127127            T exc=0;
    128128         
    129129            InEdgeIt e;
    130             for(G.first(e,v); G.valid(e); G.next(e)) exc+=(*flow)[e];
     130            for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
    131131            OutEdgeIt f;
    132             for(G.first(f,v); G.valid(f); G.next(f)) exc-=(*flow)[f];
     132            for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
    133133           
    134134            excess.set(v,exc);   
     
    146146         
    147147          InEdgeIt e;
    148           for(G.first(e,t); G.valid(e); G.next(e)) exc+=(*flow)[e];
     148          for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
    149149          OutEdgeIt f;
    150           for(G.first(f,t); G.valid(f); G.next(f)) exc-=(*flow)[f];
     150          for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
    151151         
    152152          excess.set(t,exc);   
     
    217217             
    218218        InEdgeIt e;
    219         for(G.first(e,v); G.valid(e); G.next(e)) {
     219        for(g->first(e,v); g->valid(e); g->next(e)) {
    220220          if ( (*capacity)[e] == (*flow)[e] ) continue;
    221           Node u=G.tail(e);
     221          Node u=g->tail(e);
    222222          if ( level[u] >= n ) {
    223223            bfs_queue.push(u);
     
    228228       
    229229        OutEdgeIt f;
    230         for(G.first(f,v); G.valid(f); G.next(f)) {
     230        for(g->first(f,v); g->valid(f); g->next(f)) {
    231231          if ( 0 == (*flow)[f] ) continue;
    232           Node u=G.head(f);
     232          Node u=g->head(f);
    233233          if ( level[u] >= n ) {
    234234            bfs_queue.push(u);
     
    270270    void actMinCut(_CutMap& M) {
    271271      NodeIt v;
    272       for(G.first(v); G.valid(v); G.next(v))
    273         if ( level[v] < n ) M.set(v,false);
    274         else M.set(v,true);
     272      for(g->first(v); g->valid(v); g->next(v))
     273      if ( level[v] < n ) {
     274        M.set(v,false);
     275      } else {
     276        M.set(v,true);
     277      }
    275278    }
    276279
     
    293296
    294297        OutEdgeIt e;
    295         for(G.first(e,w) ; G.valid(e); G.next(e)) {
    296           Node v=G.head(e);
     298        for(g->first(e,w) ; g->valid(e); g->next(e)) {
     299          Node v=g->head(e);
    297300          if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
    298301            queue.push(v);
     
    302305
    303306        InEdgeIt f;
    304         for(G.first(f,w) ; G.valid(f); G.next(f)) {
    305           Node v=G.tail(f);
     307        for(g->first(f,w) ; g->valid(f); g->next(f)) {
     308          Node v=g->tail(f);
    306309          if (!M[v] && (*flow)[f] > 0 ) {
    307310            queue.push(v);
     
    323326
    324327      NodeIt v;
    325       for(G.first(v) ; G.valid(v); G.next(v)) {
     328      for(g->first(v) ; g->valid(v); g->next(v)) {
    326329        M.set(v, true);
    327330      }
     
    338341
    339342        InEdgeIt e;
    340         for(G.first(e,w) ; G.valid(e); G.next(e)) {
    341           Node v=G.tail(e);
     343        for(g->first(e,w) ; g->valid(e); g->next(e)) {
     344          Node v=g->tail(e);
    342345          if (M[v] && (*flow)[e] < (*capacity)[e] ) {
    343346            queue.push(v);
     
    347350       
    348351        OutEdgeIt f;
    349         for(G.first(f,w) ; G.valid(f); G.next(f)) {
    350           Node v=G.head(f);
     352        for(g->first(f,w) ; g->valid(f); g->next(f)) {
     353          Node v=g->head(f);
    351354          if (M[v] && (*flow)[f] > 0 ) {
    352355            queue.push(v);
     
    386389         
    387390      OutEdgeIt e;
    388       for(G.first(e,w); G.valid(e); G.next(e)) {
     391      for(g->first(e,w); g->valid(e); g->next(e)) {
    389392           
    390393        if ( (*flow)[e] == (*capacity)[e] ) continue;
    391         Node v=G.head(e);           
     394        Node v=g->head(e);           
    392395           
    393396        if( lev > level[v] ) { //Push is allowed now
     
    419422      if ( exc > 0 ) { 
    420423        InEdgeIt e;
    421         for(G.first(e,w); G.valid(e); G.next(e)) {
     424        for(g->first(e,w); g->valid(e); g->next(e)) {
    422425         
    423426          if( (*flow)[e] == 0 ) continue;
    424           Node v=G.tail(e);
     427          Node v=g->tail(e);
    425428         
    426429          if( lev > level[v] ) { //Push is allowed now
     
    475478           
    476479            InEdgeIt e;
    477             for(G.first(e,v); G.valid(e); G.next(e)) {
    478               Node w=G.tail(e);
     480            for(g->first(e,v); g->valid(e); g->next(e)) {
     481              Node w=g->tail(e);
    479482              if ( level[w] == n && w != s ) {
    480483                bfs_queue.push(w);
    481484                Node first=level_list[l];
    482                 if ( G.valid(first) ) left.set(first,w);
     485                if ( g->valid(first) ) left.set(first,w);
    483486                right.set(w,first);
    484487                level_list[l]=w;
     
    490493          //the starting flow
    491494          OutEdgeIt e;
    492           for(G.first(e,s); G.valid(e); G.next(e))
     495          for(g->first(e,s); g->valid(e); g->next(e))
    493496            {
    494497              T c=(*capacity)[e];
    495498              if ( c == 0 ) continue;
    496               Node w=G.head(e);
     499              Node w=g->head(e);
    497500              if ( level[w] < n ) {       
    498501                if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
     
    519522           
    520523            InEdgeIt e;
    521             for(G.first(e,v); G.valid(e); G.next(e)) {
     524            for(g->first(e,v); g->valid(e); g->next(e)) {
    522525              if ( (*capacity)[e] == (*flow)[e] ) continue;
    523               Node w=G.tail(e);
     526              Node w=g->tail(e);
    524527              if ( level[w] == n && w != s ) {
    525528                bfs_queue.push(w);
    526529                Node first=level_list[l];
    527                 if ( G.valid(first) ) left.set(first,w);
     530                if ( g->valid(first) ) left.set(first,w);
    528531                right.set(w,first);
    529532                level_list[l]=w;
     
    533536           
    534537            OutEdgeIt f;
    535             for(G.first(f,v); G.valid(f); G.next(f)) {
     538            for(g->first(f,v); g->valid(f); g->next(f)) {
    536539              if ( 0 == (*flow)[f] ) continue;
    537               Node w=G.head(f);
     540              Node w=g->head(f);
    538541              if ( level[w] == n && w != s ) {
    539542                bfs_queue.push(w);
    540543                Node first=level_list[l];
    541                 if ( G.valid(first) ) left.set(first,w);
     544                if ( g->valid(first) ) left.set(first,w);
    542545                right.set(w,first);
    543546                level_list[l]=w;
     
    550553          //the starting flow
    551554          OutEdgeIt e;
    552           for(G.first(e,s); G.valid(e); G.next(e))
     555          for(g->first(e,s); g->valid(e); g->next(e))
    553556            {
    554557              T rem=(*capacity)[e]-(*flow)[e];
    555558              if ( rem == 0 ) continue;
    556               Node w=G.head(e);
     559              Node w=g->head(e);
    557560              if ( level[w] < n ) {       
    558561                if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
     
    563566         
    564567          InEdgeIt f;
    565           for(G.first(f,s); G.valid(f); G.next(f))
     568          for(g->first(f,s); g->valid(f); g->next(f))
    566569            {
    567570              if ( (*flow)[f] == 0 ) continue;
    568               Node w=G.tail(f);
     571              Node w=g->tail(f);
    569572              if ( level[w] < n ) {       
    570573                if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
     
    590593     
    591594      //unlacing starts
    592       if ( G.valid(right_n) ) {
    593         if ( G.valid(left_n) ) {
     595      if ( g->valid(right_n) ) {
     596        if ( g->valid(left_n) ) {
    594597          right.set(left_n, right_n);
    595598          left.set(right_n, left_n);
     
    599602        }
    600603      } else {
    601         if ( G.valid(left_n) ) {
     604        if ( g->valid(left_n) ) {
    602605          right.set(left_n, INVALID);
    603606        } else {
     
    607610      //unlacing ends
    608611               
    609       if ( !G.valid(level_list[lev]) ) {
     612      if ( !g->valid(level_list[lev]) ) {
    610613             
    611614        //gapping starts
    612615        for (int i=lev; i!=k ; ) {
    613616          Node v=level_list[++i];
    614           while ( G.valid(v) ) {
     617          while ( g->valid(v) ) {
    615618            level.set(v,n);
    616619            v=right[v];
     
    638641          if ( k < newlevel ) ++k;      //now k=newlevel
    639642          Node first=level_list[newlevel];
    640           if ( G.valid(first) ) left.set(first,w);
     643          if ( g->valid(first) ) left.set(first,w);
    641644          right.set(w,first);
    642645          left.set(w,INVALID);
  • src/work/marci/edmonds_karp.h

    r409 r466  
    1111#include <graph_wrapper.h>
    1212#include <maps.h>
     13#include <for_each_macros.h>
    1314
    1415namespace hugo {
    15 
    16 //   template<typename Graph, typename Number, typename CapacityMap, typename FlowMap>
    17 //   class ResGraph {
    18 //   public:
    19 //     typedef typename Graph::Node Node;
    20 //     typedef typename Graph::NodeIt NodeIt;
    21 //   private:
    22 //     typedef typename Graph::SymEdgeIt OldSymEdgeIt;
    23 //     const Graph& G;
    24 //     const CapacityMap& capacity;
    25 //     FlowMap& flow;
    26 //   public:
    27 //     ResGraph(const Graph& _G, const CapacityMap& _capacity, FlowMap& _flow) :
    28 //       G(_G), capacity(_capacity), flow(_flow) { }
    29 
    30 //     class Edge;
    31 //     class OutEdgeIt;
    32 //     friend class Edge;
    33 //     friend class OutEdgeIt;
    34 
    35 //     class Edge {
    36 //       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
    37 //     protected:
    38 //       const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
    39 //       OldSymEdgeIt sym;
    40 //     public:
    41 //       Edge() { }
    42 //       //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
    43 //       Number free() const {
    44 //      if (resG->G.aNode(sym)==resG->G.tail(sym)) {
    45 //        return (resG->capacity.get(sym)-resG->flow.get(sym));
    46 //      } else {
    47 //        return (resG->flow.get(sym));
    48 //      }
    49 //       }
    50 //       bool valid() const { return sym.valid(); }
    51 //       void augment(Number a) const {
    52 //      if (resG->G.aNode(sym)==resG->G.tail(sym)) {
    53 //        resG->flow.set(sym, resG->flow.get(sym)+a);
    54 //        //resG->flow[sym]+=a;
    55 //      } else {
    56 //        resG->flow.set(sym, resG->flow.get(sym)-a);
    57 //        //resG->flow[sym]-=a;
    58 //      }
    59 //       }
    60 //     };
    61 
    62 //     class OutEdgeIt : public Edge {
    63 //       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
    64 //     public:
    65 //       OutEdgeIt() { }
    66 //       //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
    67 //     private:
    68 //       OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
    69 //              resG=&_resG;
    70 //      sym=resG->G.template first<OldSymEdgeIt>(v);
    71 //      while( sym.valid() && !(free()>0) ) { ++sym; }
    72 //       }
    73 //     public:
    74 //       OutEdgeIt& operator++() {
    75 //      ++sym;
    76 //      while( sym.valid() && !(free()>0) ) { ++sym; }
    77 //      return *this;
    78 //       }
    79 //     };
    80 
    81 //     void /*getF*/first(OutEdgeIt& e, Node v) const {
    82 //       e=OutEdgeIt(*this, v);
    83 //     }
    84 //     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
    85    
    86 //     template< typename It >
    87 //     It first() const {
    88 //       It e;     
    89 //       /*getF*/first(e);
    90 //       return e;
    91 //     }
    92 
    93 //     template< typename It >
    94 //     It first(Node v) const {
    95 //       It e;
    96 //       /*getF*/first(e, v);
    97 //       return e;
    98 //     }
    99 
    100 //     Node tail(Edge e) const { return G.aNode(e.sym); }
    101 //     Node head(Edge e) const { return G.bNode(e.sym); }
    102 
    103 //     Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
    104 //     Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
    105 
    106 //     int id(Node v) const { return G.id(v); }
    107 
    108 //     template <typename S>
    109 //     class NodeMap {
    110 //       typename Graph::NodeMap<S> node_map;
    111 //     public:
    112 //       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
    113 //       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
    114 //       void set(Node nit, S a) { node_map.set(nit, a); }
    115 //       S get(Node nit) const { return node_map.get(nit); }
    116 //       S& operator[](Node nit) { return node_map[nit]; }
    117 //       const S& operator[](Node nit) const { return node_map[nit]; }
    118 //     };
    119 
    120 //   };
    121 
    122 
    123 //   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    124 //   class ResGraph2 {
    125 //   public:
    126 //     typedef typename Graph::Node Node;
    127 //     typedef typename Graph::NodeIt NodeIt;
    128 //   private:
    129 //     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
    130 //     typedef typename Graph::OutEdgeIt OldOutEdgeIt;
    131 //     typedef typename Graph::InEdgeIt OldInEdgeIt;
    132    
    133 //     const Graph& G;
    134 //     FlowMap& flow;
    135 //     const CapacityMap& capacity;
    136 //   public:
    137 //     ResGraph2(const Graph& _G, FlowMap& _flow,
    138 //           const CapacityMap& _capacity) :
    139 //       G(_G), flow(_flow), capacity(_capacity) { }
    140 
    141 //     class Edge;
    142 //     class OutEdgeIt;
    143 //     friend class Edge;
    144 //     friend class OutEdgeIt;
    145 
    146 //     class Edge {
    147 //       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
    148 //     protected:
    149 //       const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
    150 //       //OldSymEdgeIt sym;
    151 //       OldOutEdgeIt out;
    152 //       OldInEdgeIt in;
    153 //       bool out_or_in; //true, iff out
    154 //     public:
    155 //       Edge() : out_or_in(true) { }
    156 //       Number free() const {
    157 //      if (out_or_in) {
    158 //        return (resG->capacity.get(out)-resG->flow.get(out));
    159 //      } else {
    160 //        return (resG->flow.get(in));
    161 //      }
    162 //       }
    163 //       bool valid() const {
    164 //      return out_or_in && out.valid() || in.valid(); }
    165 //       void augment(Number a) const {
    166 //      if (out_or_in) {
    167 //        resG->flow.set(out, resG->flow.get(out)+a);
    168 //      } else {
    169 //        resG->flow.set(in, resG->flow.get(in)-a);
    170 //      }
    171 //       }
    172 //     };
    173 
    174 //     class OutEdgeIt : public Edge {
    175 //       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
    176 //     public:
    177 //       OutEdgeIt() { }
    178 //     private:
    179 //       OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
    180 //              resG=&_resG;
    181 //      out=resG->G.template first<OldOutEdgeIt>(v);
    182 //      while( out.valid() && !(free()>0) ) { ++out; }
    183 //      if (!out.valid()) {
    184 //        out_or_in=0;
    185 //        in=resG->G.template first<OldInEdgeIt>(v);
    186 //        while( in.valid() && !(free()>0) ) { ++in; }
    187 //      }
    188 //       }
    189 //     public:
    190 //       OutEdgeIt& operator++() {
    191 //      if (out_or_in) {
    192 //        Node v=resG->G.aNode(out);
    193 //        ++out;
    194 //        while( out.valid() && !(free()>0) ) { ++out; }
    195 //        if (!out.valid()) {
    196 //          out_or_in=0;
    197 //          in=resG->G.template first<OldInEdgeIt>(v);
    198 //          while( in.valid() && !(free()>0) ) { ++in; }
    199 //        }
    200 //      } else {
    201 //        ++in;
    202 //        while( in.valid() && !(free()>0) ) { ++in; }
    203 //      }
    204 //      return *this;
    205 //       }
    206 //     };
    207 
    208 //     void /*getF*/first(OutEdgeIt& e, Node v) const {
    209 //       e=OutEdgeIt(*this, v);
    210 //     }
    211 //     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
    212    
    213 //     template< typename It >
    214 //     It first() const {
    215 //       It e;
    216 //       /*getF*/first(e);
    217 //       return e;
    218 //     }
    219 
    220 //     template< typename It >
    221 //     It first(Node v) const {
    222 //       It e;
    223 //       /*getF*/first(e, v);
    224 //       return e;
    225 //     }
    226 
    227 //     Node tail(Edge e) const {
    228 //       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
    229 //     Node head(Edge e) const {
    230 //       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
    231 
    232 //     Node aNode(OutEdgeIt e) const {
    233 //       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
    234 //     Node bNode(OutEdgeIt e) const {
    235 //       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
    236 
    237 //     int id(Node v) const { return G.id(v); }
    238 
    239 //     template <typename S>
    240 //     class NodeMap {
    241 //       typename Graph::NodeMap<S> node_map;
    242 //     public:
    243 //       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
    244 //       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
    245 //       void set(Node nit, S a) { node_map.set(nit, a); }
    246 //       S get(Node nit) const { return node_map.get(nit); }
    247 //     };
    248 //   };
    249 
    25016
    25117  template <typename Graph, typename Number,
     
    26632    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
    26733    typedef typename ResGW::Edge ResGWEdge;
     34    //typedef typename ResGW::template NodeMap<bool> ReachedMap;
     35    typedef typename Graph::template NodeMap<bool> ReachedMap;
     36    ReachedMap level;
     37    //reached is called level because of compatibility with preflow
    26838  public:
    26939
    27040    MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity,
    27141            FlowMap& _flow) :
    272       g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow) { }
     42      g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow), level(_g) { }
    27343
    27444    bool augmentOnShortestPath() {
     
    27646      bool _augment=false;
    27747     
    278       BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
    279         bfs(res_graph);
     48      //ReachedMap level(res_graph);
     49      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     50      BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
    28051      bfs.pushAndSetReached(s);
    28152       
     
    343114      ResGW res_graph(*g, *capacity, *flow);
    344115
    345       BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
    346         bfs(res_graph);
     116      //ReachedMap level(res_graph);
     117      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     118      BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
    347119
    348120      bfs.pushAndSetReached(s);
     
    455227
    456228      //bfs for distances on the residual graph
    457       BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
    458         bfs(res_graph);
     229      //ReachedMap level(res_graph);
     230      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     231      BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
    459232      bfs.pushAndSetReached(s);
    460233      typename ResGW::template NodeMap<int>
     
    561334
    562335      ResGW res_graph(*g, *capacity, *flow);
    563 
    564       BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
    565         bfs(res_graph);
     336     
     337      //ReachedMap level(res_graph);
     338      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     339      BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
    566340
    567341      bfs.pushAndSetReached(s);
Note: See TracChangeset for help on using the changeset viewer.