COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 466:cd40ecf4d2a9 in lemon-0.x for src/work/marci/edmonds_karp.h


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

preflow, maxflow comp

File:
1 edited

Legend:

Unmodified
Added
Removed

  • 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.