COIN-OR::LEMON - Graph Library

Changeset 59:41c7f9c09a12 in lemon-0.x for src/work/edmonds_karp.hh


Ignore:
Timestamp:
02/04/04 13:46:33 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@74
Message:

.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.hh

    r43 r59  
    1 #ifndef MARCI_MAX_FLOW_HH
    2 #define MARCI_MAX_FLOW_HH
     1#ifndef EDMONDS_KARP_HH
     2#define EDMONDS_KARP_HH
    33
    44#include <algorithm>
     
    88namespace marci {
    99
    10   template<typename Graph, typename T>
     10  template<typename Graph, typename T, typename FlowMap, typename CapacityMap>
    1111  class ResGraph {
    1212    typedef typename Graph::NodeIt NodeIt;
     
    1414    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
    1515    const Graph& G;
    16     typename Graph::EdgeMap<T>& flow;
    17     const typename Graph::EdgeMap<T>& capacity;
     16    FlowMap& flow;
     17    const CapacityMap& capacity;
    1818  public:
    19     ResGraph(const Graph& _G, typename Graph::EdgeMap<T>& _flow,
    20              const typename Graph::EdgeMap<T>& _capacity) :
     19    ResGraph(const Graph& _G, FlowMap& _flow,
     20             const CapacityMap& _capacity) :
    2121      G(_G), flow(_flow), capacity(_capacity) { }
    2222
     
    2727
    2828    class EdgeIt {
    29       friend class ResGraph<Graph, T>;
     29      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
    3030    protected:
    31       const ResGraph<Graph, T>* resG;
     31      const ResGraph<Graph, T, FlowMap, CapacityMap>* resG;
    3232      OldSymEdgeIt sym;
    3333    public:
     
    5252
    5353    class OutEdgeIt : public EdgeIt {
    54       friend class ResGraph<Graph, T>;
     54      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
    5555    public:
    5656      OutEdgeIt() { }
    5757      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
    5858    private:
    59       OutEdgeIt(const ResGraph<Graph, T>& _resG, const NodeIt v) {
     59      OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, const NodeIt v) {
    6060        resG=&_resG;
    6161        sym=resG->G.template first<OldSymEdgeIt>(v);
     
    9999    template <typename ValueType>
    100100    class NodeMap {
    101       //const ResGraph<Graph, T>& G;
    102101      typename Graph::NodeMap<ValueType> node_map;
    103102    public:
    104       NodeMap(const ResGraph<Graph, T>& _G) : node_map(_G.G)/*: G(_G)*/ { }
    105       NodeMap(const ResGraph<Graph, T>& _G, const ValueType a) : node_map(_G.G, a) /*: G(_G)*/ { }
     103      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
     104      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, const ValueType a) : node_map(_G.G, a) { }
    106105      void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); }
    107106      ValueType get(const NodeIt nit) const { return node_map.get(nit); }
     
    110109  };
    111110
    112   template <typename Graph, typename T>
    113   struct max_flow_type {
     111  template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
     112  class MaxFlow {
    114113    typedef typename Graph::NodeIt NodeIt;
    115114    typedef typename Graph::EdgeIt EdgeIt;
     
    118117    typedef typename Graph::InEdgeIt InEdgeIt;
    119118    const Graph& G;
    120     NodeIt s;
    121     NodeIt t;
    122     typename Graph::EdgeMap<T> flow;
    123     const typename Graph::EdgeMap<T>& capacity;
    124 
    125     max_flow_type(const Graph& _G, NodeIt _s, NodeIt _t, const typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
     119    const NodeIt s;
     120    const NodeIt t;
     121    FlowMap& flow;
     122    const CapacityMap& capacity;
     123    typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph;
     124    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
     125    typedef typename AugGraph::EdgeIt AugEdgeIt;
     126  public:
     127    MaxFlow(const Graph& _G, const NodeIt _s, const NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
     128    bool augment() {
     129      AugGraph res_graph(G, flow, capacity);
     130      bool _augment=false;
     131     
     132      typedef typename AugGraph::NodeMap<bool> ReachedMap;
     133      BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
     134      res_bfs.pushAndSetReached(s);
     135       
     136      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
     137      //filled with invalid iterators
     138     
     139      typename AugGraph::NodeMap<int> free(res_graph);
     140       
     141      //searching for augmenting path
     142      while ( !res_bfs.finished() ) {
     143        //std::queue<AugOutEdgeIt> bfs_copy(res_bfs.getBfsQueue());
     144        //while (!bfs_copy.empty()) {
     145        //  AugOutEdgeIt e=bfs_copy.front();
     146        //  bfs_copy.pop();
     147        //  if (e.valid()) {
     148        //    std::cout<<"queue:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<" ";
     149        //  } else {
     150        //    std::cout<<"queue:"<<res_graph.aNode(e)<<"->"<<" ";
     151        //  }
     152        //}
     153        //std::cout<<std::endl;
     154        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
     155        //if (e.valid()) {
     156        //  std::cout<<"actual:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<std::endl;
     157        //} else {
     158        //  std::cout<<"actual:"<<res_graph.aNode(e)<<"->"<<std::endl;
     159        //}
     160        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
     161          NodeIt v=res_graph.tail(e);
     162          NodeIt w=res_graph.head(e);
     163          //std::cout<<v<<"->"<<w<<std::endl;
     164          pred.set(w, e);
     165          if (pred.get(v).valid()) {
     166            free.set(w, std::min(free.get(v), e.free()));
     167          } else {
     168            free.set(w, e.free());
     169          }
     170          if (res_graph.head(e)==t) { _augment=true; break; }
     171        }
     172       
     173        ++res_bfs;
     174      } //end of searching augmenting path
     175
     176      if (_augment) {
     177        NodeIt n=t;
     178        T augment_value=free.get(t);
     179        //std::cout<<"augmentation: ";
     180        while (pred.get(n).valid()) {
     181          AugEdgeIt e=pred.get(n);
     182          e.augment(augment_value);
     183          //std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
     184          n=res_graph.tail(e);
     185        }
     186        //std::cout<<std::endl;
     187      }
     188      //std::cout << "actual flow: "<< std::endl;
     189      //for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
     190      //std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     191      //}
     192      //std::cout<<std::endl;
     193
     194      return _augment;
     195    }
    126196    void run() {
    127       typedef ResGraph<Graph, T> AugGraph;
    128       AugGraph res_graph(G, flow, capacity);
    129 
    130       bool augment;
    131       do {
    132         augment=false;
    133 
    134         typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    135         typedef typename AugGraph::EdgeIt AugEdgeIt;
    136         typedef std::queue<AugOutEdgeIt> BfsQueue;
    137         BfsQueue bfs_queue;
    138         bfs_queue.push(res_graph.template first<AugOutEdgeIt>(s));
    139 
    140         typedef typename AugGraph::NodeMap<bool> ReachedMap;
    141         ReachedMap reached(res_graph, false);
    142         reached.set(s, true);
    143        
    144         bfs_iterator1< AugGraph, ReachedMap >
    145         res_bfs(res_graph, bfs_queue, reached);
    146 
    147         typedef typename AugGraph::NodeMap<AugEdgeIt> PredMap;
    148         PredMap pred(res_graph);
    149         //typename AugGraph::EdgeIt a; //invalid
    150         //a.makeInvalid();
    151         //pred.set(s, a);
    152 
    153         typedef typename AugGraph::NodeMap<int> FreeMap;
    154         FreeMap free(res_graph);
    155        
    156         //searching for augmenting path
    157         while ( res_bfs.valid() ) {
    158           //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
    159           if (res_bfs.newly_reached()) {
    160             AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
    161             NodeIt v=res_graph.tail(e);
    162             NodeIt w=res_graph.head(e);
    163             //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
    164             pred.set(w, e);
    165             if (pred.get(v).valid()) {
    166               free.set(w, std::min(free.get(v), e.free()));
    167               //std::cout <<" nem elso csucs: ";
    168               //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
    169             } else {
    170               free.set(w, e.free());
    171               //std::cout <<" elso csucs: ";
    172               //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
    173             }
    174             //std::cout<<std::endl;
    175           }
    176        
    177           if (res_graph.head(res_bfs)==t) break;
    178           ++res_bfs;
    179         } //end searching augmenting path
    180         if (reached.get(t)) {
    181           augment=true;
    182           NodeIt n=t;
    183           T augment_value=free.get(t);
    184           std::cout<<"augmentation: ";
    185           while (pred.get(n).valid()) {
    186             AugEdgeIt e=pred.get(n);
    187             e.augment(augment_value);
    188             std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
    189             n=res_graph.tail(e);
    190           }
    191           std::cout<<std::endl;
    192         }
    193 
    194         std::cout << "actual flow: "<< std::endl;
    195         for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
    196           std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    197         }
    198         std::cout<<std::endl;
    199 
    200       } while (augment);
     197      while (augment()) { }
    201198    }
    202199  };
     
    204201} // namespace marci
    205202
    206 #endif //MARCI_MAX_FLOW_HH
     203#endif //EDMONDS_KARP_HH
Note: See TracChangeset for help on using the changeset viewer.