1.1 --- a/src/work/alpar/f_ed_ka.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,119 +0,0 @@
1.4 -// -*- mode:c++ -*-
1.5 -
1.6 -#ifndef EDMONDS_KARP_HH
1.7 -#define EDMONDS_KARP_HH
1.8 -
1.9 -#include <queue>
1.10 -
1.11 -//#include <marci_property_vector.hh>
1.12 -
1.13 -#include <algorithm>
1.14 -
1.15 -//#include <bfs_iterator.hh>
1.16 -
1.17 -namespace lemon {
1.18 - template <typename Graph, typename FlowMap, typename CapacityMap>
1.19 - typename FlowMap::Value maxFlow(Graph &G,
1.20 - FlowMap &f,
1.21 - CapacityMap &c,
1.22 - typename Graph::NodeIt s,
1.23 - typename Graph::NodeIt t)
1.24 - {
1.25 - typedef typename Graph::NodeIt NodeIt;
1.26 - typedef typename Graph::EachNodeIt EachNodeIt;
1.27 - typedef typename Graph::EdgeIt EdgeIt;
1.28 - typedef typename Graph::EachEdgeIt EachEdgeIt;
1.29 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.30 - typedef typename Graph::InEdgeIt InEdgeIt;
1.31 - typedef typename FlowMap::Value T;
1.32 -
1.33 - T flow_val = 0;
1.34 - T aug_val;
1.35 -
1.36 - for(EachEdgeIt e(G);G.valid(e);G.goNext(e))
1.37 - f.set(e,0);
1.38 -
1.39 - std::queue<NodeIt> bfs_queue;
1.40 - typename Graph::NodeMap<int> visited(G); //0: unvisited,
1.41 - //1: reached by a forward edge
1.42 - //2: reached by a backward edge
1.43 - //3: it is node s
1.44 - typename Graph::NodeMap<EdgeIt> tree(G);
1.45 -
1.46 - NodeIt gn; //FIXME: it might be too global for some people...
1.47 -
1.48 - augment:
1.49 -
1.50 - for(EachNodeIt n(G);G.valid(n);G.goNext(n))
1.51 - visited.set(n,0);
1.52 -
1.53 - visited.set(s,3);
1.54 -
1.55 - //There must be a better way to do this:
1.56 - while(!bfs_queue.empty()) bfs_queue.pop();
1.57 -
1.58 - bfs_queue.push(s);
1.59 -
1.60 - while(!bfs_queue.empty() && !visited.get(t))
1.61 - {
1.62 - NodeIt n(bfs_queue.front());
1.63 - bfs_queue.pop();
1.64 - for(OutEdgeIt e(G,n);G.valid(e);G.goNext(e))
1.65 - if(f.get(e)<c.get(e) && //FIXME: <
1.66 - !visited.get(G.bNode(e)))
1.67 - {
1.68 - NodeIt nn(G.bNode(e)); //It improves nothing
1.69 - tree.set(nn,e);
1.70 - visited.set(nn,1);
1.71 - bfs_queue.push(nn);
1.72 - }
1.73 - for(InEdgeIt e(G,n);G.valid(e);G.goNext(e))
1.74 - if(f.get(e)>0 && //FIXME: >
1.75 - !visited.get(G.bNode(e)))
1.76 - {
1.77 - NodeIt nn(G.bNode(e));
1.78 - tree.set(nn,e);
1.79 - visited.set(nn,2);
1.80 - bfs_queue.push(nn);
1.81 - }
1.82 - }
1.83 -
1.84 - if(!visited.get(t)) return flow_val;
1.85 -
1.86 - // Augmenting value computation
1.87 - aug_val = visited.get(t)==1 ?
1.88 - c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t));
1.89 - //FIXME: I would need 'G.opposite(e,n)'
1.90 - gn = visited.get(t)==1 ? G.source(tree.get(t)) : G.target(tree.get(t));
1.91 - while(gn!=s) if(visited.get(gn)==1)
1.92 - {
1.93 - //FIXME: nonstandard gcc extension!
1.94 - aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn));
1.95 - gn=G.source(tree.get(gn));
1.96 - }
1.97 - else {
1.98 - //FIXME: nonstandard gcc extension!
1.99 - aug_val <?= f.get(tree.get(gn));
1.100 - gn=G.target(tree.get(gn));
1.101 - }
1.102 -
1.103 - // The augmentation itself
1.104 - gn = t;
1.105 - while(gn!=s) if(visited.get(gn)==1)
1.106 - {
1.107 - f.set(tree.get(gn),f.get(tree.get(gn))+aug_val);
1.108 - gn=G.source(tree.get(gn));
1.109 - }
1.110 - else {
1.111 - f.set(tree.get(gn),f.get(tree.get(gn))-aug_val);
1.112 - gn=G.target(tree.get(gn));
1.113 - }
1.114 -
1.115 - flow_val+=aug_val;
1.116 -
1.117 - goto augment; // Vivat goto forever!
1.118 - }
1.119 -
1.120 -} // namespace lemon
1.121 -
1.122 -#endif //EDMONDS_KARP_HH