COIN-OR::LEMON - Graph Library

Changeset 330:7ac0d4e8a31c in lemon-0.x


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.

Location:
src/work
Files:
2 added
6 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/minlengthpaths.h

    r329 r330  
    3838    typedef ConstMap<Edge,int> ConstMap;
    3939
    40     typedef ResGraphWrapper<const Graph,int,EdgeIntMap,ConstMap> ResGraphType;
     40    typedef ResGraphWrapper<const Graph,int,ConstMap,EdgeIntMap> ResGraphType;
    4141
    4242
     
    9393
    9494      //We need a residual graph, in which some of the edges are reversed
    95       ResGraphType res_graph(G, reversed, const1map);
     95      ResGraphType res_graph(G, const1map, reversed);
    9696
    9797      //Initialize the copy of the Dijkstra potential to zero
  • src/work/jacint/preflow.h

    r278 r330  
    4444
    4545  template <typename Graph, typename T,
    46     typename FlowMap=typename Graph::EdgeMap<T>,
    47     typename CapMap=typename Graph::EdgeMap<T> >
     46            typename CapMap=typename Graph::EdgeMap<T>,
     47            typename FlowMap=typename Graph::EdgeMap<T> >
    4848  class Preflow {
    4949   
     
    5757    Node s;
    5858    Node t;
     59    const CapMap& capacity; 
    5960    FlowMap& flow;
    60     const CapMap& capacity; 
    6161    T value;
    6262
     
    6464    Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
    6565            FlowMap& _flow ) :
    66       G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) {}
    67 
     66      G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow) {}
    6867
    6968    void run() {
  • 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);
  • src/work/marci/edmonds_karp_demo.cc

    r317 r330  
    105105
    106106    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    107       max_flow_test(G, s, t, flow, cap);
     107      max_flow_test(G, s, t, cap, flow);
    108108    int i=0;
    109109    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
     
    133133
    134134    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    135       max_flow_test(G, s, t, flow, cap);
     135      max_flow_test(G, s, t, cap, flow);
    136136    int i=0;
    137137    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
     
    161161
    162162    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    163       max_flow_test(G, s, t, flow, cap);
     163      max_flow_test(G, s, t, cap, flow);
    164164    int i=0;
    165165    while (max_flow_test.augmentOnBlockingFlow2()) {
     
    189189
    190190    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    191       max_flow_test(G, s, t, flow, cap);
     191      max_flow_test(G, s, t, cap, flow);
    192192    int i=0;
    193193    while (max_flow_test.augmentOnShortestPath()) {
  • src/work/marci/graph_wrapper.h

    r323 r330  
    897897 
    898898
    899   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     899  template<typename Graph, typename Number,
     900           typename CapacityMap, typename FlowMap>
    900901  class ResGraphWrapper : public GraphWrapper<Graph> {
    901902  protected:
     
    903904//    typedef typename Graph::InEdgeIt GraphInEdgeIt;
    904905//    typedef typename Graph::Edge GraphEdge;
     906    const CapacityMap* capacity;
    905907    FlowMap* flow;
    906     const CapacityMap* capacity;
    907908  public:
    908909
    909     ResGraphWrapper(Graph& _graph, FlowMap& _flow,
    910                     const CapacityMap& _capacity) :
    911       GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
     910    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
     911                    FlowMap& _flow) :
     912      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
    912913
    913914    class Edge;
     
    919920    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    920921    class Edge : public Graph::Edge {
    921       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     922      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    922923    protected:
    923924      bool forward; //true, iff forward
     
    941942    };
    942943//     class Edge {
    943 //       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     944//       friend class ResGraphWrapper<Graph, Number,lksd FlowMap, CapacityMap>;
    944945//     protected:
    945946//       bool out_or_in; //true, iff out
     
    968969//     };
    969970    class OutEdgeIt {
    970       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     971      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    971972    protected:
    972973      typename Graph::OutEdgeIt out;
     
    979980      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
    980981//the unique invalid iterator
    981       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
     982      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
    982983        forward=true;
    983984        resG.graph->first(out, v);
     
    10011002    };
    10021003//     class OutEdgeIt : public Edge {
    1003 //       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     1004//       friend class ResGraphWrapper<Graph, Number, FkklowMap, CapacityMap>;
    10041005//     public:
    10051006//       OutEdgeIt() { }
     
    10071008//       OutEdgeIt(const Edge& e) : Edge(e) { }
    10081009//       OutEdgeIt(const Invalid& i) : Edge(i) { }
    1009 //       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
     1010//       OutEdgeIt(const ResGraphWrapper<Graph, Number, FdfvlowMap, CapacityMap>& resG, Node v) : Edge() {
    10101011//      resG.graph->first(out, v);
    10111012//      while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
     
    10391040
    10401041    class InEdgeIt {
    1041       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     1042      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    10421043    protected:
    10431044      typename Graph::OutEdgeIt out;
     
    10501051      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
    10511052//the unique invalid iterator
    1052       InEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
     1053      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
    10531054        forward=true;
    10541055        resG.graph->first(in, v);
     
    10731074
    10741075    class EdgeIt {
    1075       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     1076      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    10761077    protected:
    10771078      typename Graph::EdgeIt e;
     
    10801081      EdgeIt() { }
    10811082      EdgeIt(const Invalid& i) : e(i), forward(false) { }
    1082       EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) {
     1083      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
    10831084        forward=true;
    10841085        resG.graph->first(e);
     
    10951096    };
    10961097//     class EdgeIt : public Edge {
    1097 //       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     1098//       friend class ResGraphWrapper<Graph, Number, FflowMap, CapacityMap>;
    10981099//       NodeIt v;
    10991100//     public:
     
    11011102//       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
    11021103//       EdgeIt(const Invalid& i) : Edge(i) { }
    1103 //       EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
     1104//       EdgeIt(const ResGraphWrapper<Graph, Number, FlfowMap, CapacityMap>& resG) : Edge() {
    11041105//      resG.graph->first(v);
    11051106//      if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
     
    13181319//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
    13191320//     public:
    1320 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
     1321//       NodeMap(const ResGraphWrapper<Graph, Number, FlovwMap, CapacityMap>& _G)
    13211322//      : Graph::NodeMap<T>(_G.gw) { }
    1322 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
     1323//       NodeMap(const ResGraphWrapper<Graph, Number, FlowvMap, CapacityMap>& _G,
    13231324//            T a) : Graph::NodeMap<T>(_G.gw, a) { }
    13241325//     };
     
    13381339      typename Graph::EdgeMap<T> forward_map, backward_map;
    13391340    public:
    1340       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
    1341       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
     1341      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
     1342      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
    13421343      void set(Edge e, T a) {
    13431344        if (e.forward)
  • src/work/marci/makefile

    r317 r330  
    1313
    1414LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
    15 BINARIES = edmonds_karp_demo iterator_bfs_demo
     15BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test
    1616#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
    1717
Note: See TracChangeset for help on using the changeset viewer.