1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/edmonds_karp.hh Fri Jan 30 14:49:04 2004 +0000
1.3 @@ -0,0 +1,206 @@
1.4 +#ifndef MARCI_MAX_FLOW_HH
1.5 +#define MARCI_MAX_FLOW_HH
1.6 +
1.7 +#include <algorithm>
1.8 +
1.9 +#include <bfs_iterator.hh>
1.10 +
1.11 +namespace marci {
1.12 +
1.13 + template<typename Graph, typename T>
1.14 + class ResGraph {
1.15 + typedef typename Graph::NodeIt NodeIt;
1.16 + typedef typename Graph::EachNodeIt EachNodeIt;
1.17 + typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.18 + const Graph& G;
1.19 + typename Graph::EdgeMap<T>& flow;
1.20 + const typename Graph::EdgeMap<T>& capacity;
1.21 + public:
1.22 + ResGraph(const Graph& _G, typename Graph::EdgeMap<T>& _flow,
1.23 + const typename Graph::EdgeMap<T>& _capacity) :
1.24 + G(_G), flow(_flow), capacity(_capacity) { }
1.25 +
1.26 + class EdgeIt;
1.27 + class OutEdgeIt;
1.28 + friend class EdgeIt;
1.29 + friend class OutEdgeIt;
1.30 +
1.31 + class EdgeIt {
1.32 + friend class ResGraph<Graph, T>;
1.33 + protected:
1.34 + const ResGraph<Graph, T>* resG;
1.35 + OldSymEdgeIt sym;
1.36 + public:
1.37 + EdgeIt() { }
1.38 + //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
1.39 + T free() const {
1.40 + if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.41 + return (resG->capacity.get(sym)-resG->flow.get(sym));
1.42 + } else {
1.43 + return (resG->flow.get(sym));
1.44 + }
1.45 + }
1.46 + bool valid() const { return sym.valid(); }
1.47 + void augment(const T a) const {
1.48 + if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.49 + resG->flow.set(sym, resG->flow.get(sym)+a);
1.50 + } else {
1.51 + resG->flow.set(sym, resG->flow.get(sym)-a);
1.52 + }
1.53 + }
1.54 + };
1.55 +
1.56 + class OutEdgeIt : public EdgeIt {
1.57 + friend class ResGraph<Graph, T>;
1.58 + public:
1.59 + OutEdgeIt() { }
1.60 + //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
1.61 + private:
1.62 + OutEdgeIt(const ResGraph<Graph, T>& _resG, const NodeIt v) {
1.63 + resG=&_resG;
1.64 + sym=resG->G.template first<OldSymEdgeIt>(v);
1.65 + while( sym.valid() && !(free()>0) ) { ++sym; }
1.66 + }
1.67 + public:
1.68 + OutEdgeIt& operator++() {
1.69 + ++sym;
1.70 + while( sym.valid() && !(free()>0) ) { ++sym; }
1.71 + return *this;
1.72 + }
1.73 + };
1.74 +
1.75 + void getFirst(OutEdgeIt& e, const NodeIt v) const {
1.76 + e=OutEdgeIt(*this, v);
1.77 + }
1.78 + void getFirst(EachNodeIt& v) const { G.getFirst(v); }
1.79 +
1.80 + template< typename It >
1.81 + It first() const {
1.82 + It e;
1.83 + getFirst(e);
1.84 + return e;
1.85 + }
1.86 +
1.87 + template< typename It >
1.88 + It first(const NodeIt v) const {
1.89 + It e;
1.90 + getFirst(e, v);
1.91 + return e;
1.92 + }
1.93 +
1.94 + NodeIt tail(const EdgeIt e) const { return G.aNode(e.sym); }
1.95 + NodeIt head(const EdgeIt e) const { return G.bNode(e.sym); }
1.96 +
1.97 + NodeIt aNode(const OutEdgeIt e) const { return G.aNode(e.sym); }
1.98 + NodeIt bNode(const OutEdgeIt e) const { return G.bNode(e.sym); }
1.99 +
1.100 + int id(const NodeIt v) const { return G.id(v); }
1.101 +
1.102 + template <typename ValueType>
1.103 + class NodeMap {
1.104 + //const ResGraph<Graph, T>& G;
1.105 + typename Graph::NodeMap<ValueType> node_map;
1.106 + public:
1.107 + NodeMap(const ResGraph<Graph, T>& _G) : node_map(_G.G)/*: G(_G)*/ { }
1.108 + NodeMap(const ResGraph<Graph, T>& _G, const ValueType a) : node_map(_G.G, a) /*: G(_G)*/ { }
1.109 + void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); }
1.110 + ValueType get(const NodeIt nit) const { return node_map.get(nit); }
1.111 + };
1.112 +
1.113 + };
1.114 +
1.115 + template <typename Graph, typename T>
1.116 + struct max_flow_type {
1.117 + typedef typename Graph::NodeIt NodeIt;
1.118 + typedef typename Graph::EdgeIt EdgeIt;
1.119 + typedef typename Graph::EachEdgeIt EachEdgeIt;
1.120 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.121 + typedef typename Graph::InEdgeIt InEdgeIt;
1.122 + const Graph& G;
1.123 + NodeIt s;
1.124 + NodeIt t;
1.125 + typename Graph::EdgeMap<T> flow;
1.126 + const typename Graph::EdgeMap<T>& capacity;
1.127 +
1.128 + 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) { }
1.129 + void run() {
1.130 + typedef ResGraph<Graph, T> AugGraph;
1.131 + AugGraph res_graph(G, flow, capacity);
1.132 +
1.133 + bool augment;
1.134 + do {
1.135 + augment=false;
1.136 +
1.137 + typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.138 + typedef typename AugGraph::EdgeIt AugEdgeIt;
1.139 + typedef std::queue<AugOutEdgeIt> BfsQueue;
1.140 + BfsQueue bfs_queue;
1.141 + bfs_queue.push(res_graph.template first<AugOutEdgeIt>(s));
1.142 +
1.143 + typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.144 + ReachedMap reached(res_graph, false);
1.145 + reached.set(s, true);
1.146 +
1.147 + bfs_iterator1< AugGraph, ReachedMap >
1.148 + res_bfs(res_graph, bfs_queue, reached);
1.149 +
1.150 + typedef typename AugGraph::NodeMap<AugEdgeIt> PredMap;
1.151 + PredMap pred(res_graph);
1.152 + //typename AugGraph::EdgeIt a; //invalid
1.153 + //a.makeInvalid();
1.154 + //pred.set(s, a);
1.155 +
1.156 + typedef typename AugGraph::NodeMap<int> FreeMap;
1.157 + FreeMap free(res_graph);
1.158 +
1.159 + //searching for augmenting path
1.160 + while ( res_bfs.valid() ) {
1.161 + //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
1.162 + if (res_bfs.newly_reached()) {
1.163 + AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
1.164 + NodeIt v=res_graph.tail(e);
1.165 + NodeIt w=res_graph.head(e);
1.166 + //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
1.167 + pred.set(w, e);
1.168 + if (pred.get(v).valid()) {
1.169 + free.set(w, std::min(free.get(v), e.free()));
1.170 + //std::cout <<" nem elso csucs: ";
1.171 + //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
1.172 + } else {
1.173 + free.set(w, e.free());
1.174 + //std::cout <<" elso csucs: ";
1.175 + //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
1.176 + }
1.177 + //std::cout<<std::endl;
1.178 + }
1.179 +
1.180 + if (res_graph.head(res_bfs)==t) break;
1.181 + ++res_bfs;
1.182 + } //end searching augmenting path
1.183 + if (reached.get(t)) {
1.184 + augment=true;
1.185 + NodeIt n=t;
1.186 + T augment_value=free.get(t);
1.187 + std::cout<<"augmentation: ";
1.188 + while (pred.get(n).valid()) {
1.189 + AugEdgeIt e=pred.get(n);
1.190 + e.augment(augment_value);
1.191 + std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
1.192 + n=res_graph.tail(e);
1.193 + }
1.194 + std::cout<<std::endl;
1.195 + }
1.196 +
1.197 + std::cout << "actual flow: "<< std::endl;
1.198 + for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
1.199 + std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.200 + }
1.201 + std::cout<<std::endl;
1.202 +
1.203 + } while (augment);
1.204 + }
1.205 + };
1.206 +
1.207 +} // namespace marci
1.208 +
1.209 +#endif //MARCI_MAX_FLOW_HH