COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 330:7ac0d4e8a31c in lemon-0.x for src/work/marci/edmonds_karp.h


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

In the resgraphwrapper interface, and in the constructor,
the order of FlowMap? and CapacityMap? is changed.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/work/marci/edmonds_karp.h

    r317 r330  
    1414namespace hugo {
    1515
    16   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    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     FlowMap& flow;
    25     const CapacityMap& capacity;
    26   public:
    27     ResGraph(const Graph& _G, FlowMap& _flow,
    28              const CapacityMap& _capacity) :
    29       G(_G), flow(_flow), capacity(_capacity) { }
    30 
    31     class Edge;
    32     class OutEdgeIt;
    33     friend class Edge;
    34     friend class OutEdgeIt;
    35 
    36     class Edge {
    37       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
    38     protected:
    39       const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
    40       OldSymEdgeIt sym;
    41     public:
    42       Edge() { }
    43       //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
    44       Number free() const {
    45         if (resG->G.aNode(sym)==resG->G.tail(sym)) {
    46           return (resG->capacity.get(sym)-resG->flow.get(sym));
    47         } else {
    48           return (resG->flow.get(sym));
    49         }
    50       }
    51       bool valid() const { return sym.valid(); }
    52       void augment(Number a) const {
    53         if (resG->G.aNode(sym)==resG->G.tail(sym)) {
    54           resG->flow.set(sym, resG->flow.get(sym)+a);
    55           //resG->flow[sym]+=a;
    56         } else {
    57           resG->flow.set(sym, resG->flow.get(sym)-a);
    58           //resG->flow[sym]-=a;
    59         }
    60       }
    61     };
    62 
    63     class OutEdgeIt : public Edge {
    64       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
    65     public:
    66       OutEdgeIt() { }
    67       //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
    68     private:
    69       OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
    70         resG=&_resG;
    71         sym=resG->G.template first<OldSymEdgeIt>(v);
    72         while( sym.valid() && !(free()>0) ) { ++sym; }
    73       }
    74     public:
    75       OutEdgeIt& operator++() {
    76         ++sym;
    77         while( sym.valid() && !(free()>0) ) { ++sym; }
    78         return *this;
    79       }
    80     };
    81 
    82     void /*getF*/first(OutEdgeIt& e, Node v) const {
    83       e=OutEdgeIt(*this, v);
    84     }
    85     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
     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); }
    8685   
    87     template< typename It >
    88     It first() const {
    89       It e;     
    90       /*getF*/first(e);
    91       return e;
    92     }
    93 
    94     template< typename It >
    95     It first(Node v) const {
    96       It e;
    97       /*getF*/first(e, v);
    98       return e;
    99     }
    100 
    101     Node tail(Edge e) const { return G.aNode(e.sym); }
    102     Node head(Edge e) const { return G.bNode(e.sym); }
    103 
    104     Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
    105     Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
    106 
    107     int id(Node v) const { return G.id(v); }
    108 
    109     template <typename S>
    110     class NodeMap {
    111       typename Graph::NodeMap<S> node_map;
    112     public:
    113       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
    114       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
    115       void set(Node nit, S a) { node_map.set(nit, a); }
    116       S get(Node nit) const { return node_map.get(nit); }
    117       S& operator[](Node nit) { return node_map[nit]; }
    118       const S& operator[](Node nit) const { return node_map[nit]; }
    119     };
    120 
    121   };
    122 
    123 
    124   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    125   class ResGraph2 {
    126   public:
    127     typedef typename Graph::Node Node;
    128     typedef typename Graph::NodeIt NodeIt;
    129   private:
    130     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
    131     typedef typename Graph::OutEdgeIt OldOutEdgeIt;
    132     typedef typename Graph::InEdgeIt OldInEdgeIt;
     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;
    133132   
    134     const Graph& G;
    135     FlowMap& flow;
    136     const CapacityMap& capacity;
    137   public:
    138     ResGraph2(const Graph& _G, FlowMap& _flow,
    139              const CapacityMap& _capacity) :
    140       G(_G), flow(_flow), capacity(_capacity) { }
    141 
    142     class Edge;
    143     class OutEdgeIt;
    144     friend class Edge;
    145     friend class OutEdgeIt;
    146 
    147     class Edge {
    148       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
    149     protected:
    150       const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
    151       //OldSymEdgeIt sym;
    152       OldOutEdgeIt out;
    153       OldInEdgeIt in;
    154       bool out_or_in; //true, iff out
    155     public:
    156       Edge() : out_or_in(true) { }
    157       Number free() const {
    158         if (out_or_in) {
    159           return (resG->capacity.get(out)-resG->flow.get(out));
    160         } else {
    161           return (resG->flow.get(in));
    162         }
    163       }
    164       bool valid() const {
    165         return out_or_in && out.valid() || in.valid(); }
    166       void augment(Number a) const {
    167         if (out_or_in) {
    168           resG->flow.set(out, resG->flow.get(out)+a);
    169         } else {
    170           resG->flow.set(in, resG->flow.get(in)-a);
    171         }
    172       }
    173     };
    174 
    175     class OutEdgeIt : public Edge {
    176       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
    177     public:
    178       OutEdgeIt() { }
    179     private:
    180       OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
    181         resG=&_resG;
    182         out=resG->G.template first<OldOutEdgeIt>(v);
    183         while( out.valid() && !(free()>0) ) { ++out; }
    184         if (!out.valid()) {
    185           out_or_in=0;
    186           in=resG->G.template first<OldInEdgeIt>(v);
    187           while( in.valid() && !(free()>0) ) { ++in; }
    188         }
    189       }
    190     public:
    191       OutEdgeIt& operator++() {
    192         if (out_or_in) {
    193           Node v=resG->G.aNode(out);
    194           ++out;
    195           while( out.valid() && !(free()>0) ) { ++out; }
    196           if (!out.valid()) {
    197             out_or_in=0;
    198             in=resG->G.template first<OldInEdgeIt>(v);
    199             while( in.valid() && !(free()>0) ) { ++in; }
    200           }
    201         } else {
    202           ++in;
    203           while( in.valid() && !(free()>0) ) { ++in; }
    204         }
    205         return *this;
    206       }
    207     };
    208 
    209     void /*getF*/first(OutEdgeIt& e, Node v) const {
    210       e=OutEdgeIt(*this, v);
    211     }
    212     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
     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); }
    213212   
    214     template< typename It >
    215     It first() const {
    216       It e;
    217       /*getF*/first(e);
    218       return e;
    219     }
    220 
    221     template< typename It >
    222     It first(Node v) const {
    223       It e;
    224       /*getF*/first(e, v);
    225       return e;
    226     }
    227 
    228     Node tail(Edge e) const {
    229       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
    230     Node head(Edge e) const {
    231       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
    232 
    233     Node aNode(OutEdgeIt e) const {
    234       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
    235     Node bNode(OutEdgeIt e) const {
    236       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
    237 
    238     int id(Node v) const { return G.id(v); }
    239 
    240     template <typename S>
    241     class NodeMap {
    242       typename Graph::NodeMap<S> node_map;
    243     public:
    244       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
    245       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
    246       void set(Node nit, S a) { node_map.set(nit, a); }
    247       S get(Node nit) const { return node_map.get(nit); }
    248     };
    249   };
    250 
    251 
    252   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     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
     250
     251  template <typename Graph, typename Number,
     252            typename CapacityMap, typename FlowMap>
    253253  class MaxFlow {
    254254  protected:
    … …  
    261261    Node s;
    262262    Node t;
     263    const CapacityMap* capacity;
    263264    FlowMap* flow;
    264     const CapacityMap* capacity;
    265     typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW;
     265    typedef ResGraphWrapper<const Graph, Number, CapacityMap, FlowMap> ResGW;
    266266    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
    267267    typedef typename ResGW::Edge ResGWEdge;
    268268  public:
    269269
    270     MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
    271       g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
     270    MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity,
     271            FlowMap& _flow) :
     272      g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow) { }
    272273
    273274    bool augmentOnShortestPath() {
    274       ResGW res_graph(*g, *flow, *capacity);
     275      ResGW res_graph(*g, *capacity, *flow);
    275276      bool _augment=false;
    276277     
    … …  
    337338      bool _augment=false;
    338339
    339       ResGW res_graph(*g, *flow, *capacity);
     340      ResGW res_graph(*g, *capacity, *flow);
    340341
    341342      BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
    … …  
    446447      bool _augment=false;
    447448
    448       ResGW res_graph(*g, *flow, *capacity);
     449      ResGW res_graph(*g, *capacity, *flow);
    449450
    450451      //bfs for distances on the residual graph
    … …  
    551552      bool _augment=false;
    552553
    553       ResGW res_graph(*g, *flow, *capacity);
     554      ResGW res_graph(*g, *capacity, *flow);
    554555
    555556      BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
Note: See TracChangeset for help on using the changeset viewer.