src/work/edmonds_karp.hh
author alpar
Tue, 03 Feb 2004 13:29:49 +0000
changeset 54 acd0dc288149
child 59 41c7f9c09a12
permissions -rw-r--r--
.
marci@43
     1
#ifndef MARCI_MAX_FLOW_HH
marci@43
     2
#define MARCI_MAX_FLOW_HH
marci@43
     3
marci@43
     4
#include <algorithm>
marci@43
     5
marci@43
     6
#include <bfs_iterator.hh>
marci@43
     7
marci@43
     8
namespace marci {
marci@43
     9
marci@43
    10
  template<typename Graph, typename T>
marci@43
    11
  class ResGraph {
marci@43
    12
    typedef typename Graph::NodeIt NodeIt;
marci@43
    13
    typedef typename Graph::EachNodeIt EachNodeIt;
marci@43
    14
    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
marci@43
    15
    const Graph& G;
marci@43
    16
    typename Graph::EdgeMap<T>& flow;
marci@43
    17
    const typename Graph::EdgeMap<T>& capacity;
marci@43
    18
  public:
marci@43
    19
    ResGraph(const Graph& _G, typename Graph::EdgeMap<T>& _flow, 
marci@43
    20
	     const typename Graph::EdgeMap<T>& _capacity) : 
marci@43
    21
      G(_G), flow(_flow), capacity(_capacity) { }
marci@43
    22
marci@43
    23
    class EdgeIt; 
marci@43
    24
    class OutEdgeIt; 
marci@43
    25
    friend class EdgeIt; 
marci@43
    26
    friend class OutEdgeIt; 
marci@43
    27
marci@43
    28
    class EdgeIt {
marci@43
    29
      friend class ResGraph<Graph, T>;
marci@43
    30
    protected:
marci@43
    31
      const ResGraph<Graph, T>* resG;
marci@43
    32
      OldSymEdgeIt sym;
marci@43
    33
    public:
marci@43
    34
      EdgeIt() { } 
marci@43
    35
      //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
marci@43
    36
      T free() const { 
marci@43
    37
	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
marci@43
    38
	  return (resG->capacity.get(sym)-resG->flow.get(sym)); 
marci@43
    39
	} else { 
marci@43
    40
	  return (resG->flow.get(sym)); 
marci@43
    41
	}
marci@43
    42
      }
marci@43
    43
      bool valid() const { return sym.valid(); }
marci@43
    44
      void augment(const T a) const {
marci@43
    45
	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
marci@43
    46
	  resG->flow.set(sym, resG->flow.get(sym)+a);
marci@43
    47
	} else { 
marci@43
    48
	  resG->flow.set(sym, resG->flow.get(sym)-a);
marci@43
    49
	}
marci@43
    50
      }
marci@43
    51
    };
marci@43
    52
marci@43
    53
    class OutEdgeIt : public EdgeIt {
marci@43
    54
      friend class ResGraph<Graph, T>;
marci@43
    55
    public:
marci@43
    56
      OutEdgeIt() { }
marci@43
    57
      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
marci@43
    58
    private:
marci@43
    59
      OutEdgeIt(const ResGraph<Graph, T>& _resG, const NodeIt v) { 
marci@43
    60
      	resG=&_resG;
marci@43
    61
	sym=resG->G.template first<OldSymEdgeIt>(v);
marci@43
    62
	while( sym.valid() && !(free()>0) ) { ++sym; }
marci@43
    63
      }
marci@43
    64
    public:
marci@43
    65
      OutEdgeIt& operator++() { 
marci@43
    66
	++sym; 
marci@43
    67
	while( sym.valid() && !(free()>0) ) { ++sym; }
marci@43
    68
	return *this; 
marci@43
    69
      }
marci@43
    70
    };
marci@43
    71
marci@43
    72
    void getFirst(OutEdgeIt& e, const NodeIt v) const { 
marci@43
    73
      e=OutEdgeIt(*this, v); 
marci@43
    74
    }
marci@43
    75
    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
marci@43
    76
    
marci@43
    77
    template< typename It >
marci@43
    78
    It first() const { 
marci@43
    79
      It e;
marci@43
    80
      getFirst(e);
marci@43
    81
      return e; 
marci@43
    82
    }
marci@43
    83
marci@43
    84
    template< typename It >
marci@43
    85
    It first(const NodeIt v) const { 
marci@43
    86
      It e;
marci@43
    87
      getFirst(e, v);
marci@43
    88
      return e; 
marci@43
    89
    }
marci@43
    90
marci@43
    91
    NodeIt tail(const EdgeIt e) const { return G.aNode(e.sym); }
marci@43
    92
    NodeIt head(const EdgeIt e) const { return G.bNode(e.sym); }
marci@43
    93
marci@43
    94
    NodeIt aNode(const OutEdgeIt e) const { return G.aNode(e.sym); }
marci@43
    95
    NodeIt bNode(const OutEdgeIt e) const { return G.bNode(e.sym); }
marci@43
    96
marci@43
    97
    int id(const NodeIt v) const { return G.id(v); }
marci@43
    98
marci@43
    99
    template <typename ValueType>
marci@43
   100
    class NodeMap {
marci@43
   101
      //const ResGraph<Graph, T>& G; 
marci@43
   102
      typename Graph::NodeMap<ValueType> node_map; 
marci@43
   103
    public:
marci@43
   104
      NodeMap(const ResGraph<Graph, T>& _G) : node_map(_G.G)/*: G(_G)*/ { }
marci@43
   105
      NodeMap(const ResGraph<Graph, T>& _G, const ValueType a) : node_map(_G.G, a) /*: G(_G)*/ { }
marci@43
   106
      void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); }
marci@43
   107
      ValueType get(const NodeIt nit) const { return node_map.get(nit); }
marci@43
   108
    };
marci@43
   109
marci@43
   110
  };
marci@43
   111
marci@43
   112
  template <typename Graph, typename T>
marci@43
   113
  struct max_flow_type {
marci@43
   114
    typedef typename Graph::NodeIt NodeIt;
marci@43
   115
    typedef typename Graph::EdgeIt EdgeIt;
marci@43
   116
    typedef typename Graph::EachEdgeIt EachEdgeIt;
marci@43
   117
    typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@43
   118
    typedef typename Graph::InEdgeIt InEdgeIt;
marci@43
   119
    const Graph& G;
marci@43
   120
    NodeIt s;
marci@43
   121
    NodeIt t;
marci@43
   122
    typename Graph::EdgeMap<T> flow;
marci@43
   123
    const typename Graph::EdgeMap<T>& capacity;
marci@43
   124
marci@43
   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) { }
marci@43
   126
    void run() {
marci@43
   127
      typedef ResGraph<Graph, T> AugGraph;
marci@43
   128
      AugGraph res_graph(G, flow, capacity);
marci@43
   129
marci@43
   130
      bool augment;
marci@43
   131
      do {
marci@43
   132
	augment=false;
marci@43
   133
marci@43
   134
	typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
marci@43
   135
	typedef typename AugGraph::EdgeIt AugEdgeIt;
marci@43
   136
	typedef std::queue<AugOutEdgeIt> BfsQueue;
marci@43
   137
	BfsQueue bfs_queue;
marci@43
   138
	bfs_queue.push(res_graph.template first<AugOutEdgeIt>(s));
marci@43
   139
marci@43
   140
	typedef typename AugGraph::NodeMap<bool> ReachedMap;
marci@43
   141
	ReachedMap reached(res_graph, false);
marci@43
   142
	reached.set(s, true); 
marci@43
   143
	
marci@43
   144
	bfs_iterator1< AugGraph, ReachedMap > 
marci@43
   145
	res_bfs(res_graph, bfs_queue, reached);
marci@43
   146
marci@43
   147
	typedef typename AugGraph::NodeMap<AugEdgeIt> PredMap;
marci@43
   148
	PredMap pred(res_graph);
marci@43
   149
	//typename AugGraph::EdgeIt a; //invalid
marci@43
   150
	//a.makeInvalid();
marci@43
   151
	//pred.set(s, a);
marci@43
   152
marci@43
   153
	typedef typename AugGraph::NodeMap<int> FreeMap;
marci@43
   154
	FreeMap free(res_graph);
marci@43
   155
	
marci@43
   156
	//searching for augmenting path
marci@43
   157
	while ( res_bfs.valid() ) { 
marci@43
   158
	  //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
marci@43
   159
	  if (res_bfs.newly_reached()) {
marci@43
   160
	    AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
marci@43
   161
	    NodeIt v=res_graph.tail(e);
marci@43
   162
	    NodeIt w=res_graph.head(e);
marci@43
   163
	    //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
marci@43
   164
	    pred.set(w, e);
marci@43
   165
	    if (pred.get(v).valid()) {
marci@43
   166
	      free.set(w, std::min(free.get(v), e.free()));
marci@43
   167
	      //std::cout <<" nem elso csucs: ";
marci@43
   168
	      //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
marci@43
   169
	    } else {
marci@43
   170
	      free.set(w, e.free()); 
marci@43
   171
	      //std::cout <<" elso csucs: ";
marci@43
   172
	      //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
marci@43
   173
	    }
marci@43
   174
	    //std::cout<<std::endl;
marci@43
   175
	  }
marci@43
   176
	
marci@43
   177
	  if (res_graph.head(res_bfs)==t) break;
marci@43
   178
	  ++res_bfs;
marci@43
   179
	} //end searching augmenting path
marci@43
   180
	if (reached.get(t)) {
marci@43
   181
	  augment=true;
marci@43
   182
	  NodeIt n=t;
marci@43
   183
	  T augment_value=free.get(t);
marci@43
   184
	  std::cout<<"augmentation: ";
marci@43
   185
	  while (pred.get(n).valid()) { 
marci@43
   186
	    AugEdgeIt e=pred.get(n);
marci@43
   187
	    e.augment(augment_value); 
marci@43
   188
	    std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
marci@43
   189
	    n=res_graph.tail(e);
marci@43
   190
	  }
marci@43
   191
	  std::cout<<std::endl;
marci@43
   192
	}
marci@43
   193
marci@43
   194
	std::cout << "actual flow: "<< std::endl;
marci@43
   195
	for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
marci@43
   196
	  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@43
   197
	}
marci@43
   198
	std::cout<<std::endl;
marci@43
   199
marci@43
   200
      } while (augment);
marci@43
   201
    }
marci@43
   202
  };
marci@43
   203
marci@43
   204
} // namespace marci
marci@43
   205
marci@43
   206
#endif //MARCI_MAX_FLOW_HH