1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/alpar/f_ed_ka.h Mon Feb 16 10:57:01 2004 +0000
1.3 @@ -0,0 +1,113 @@
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 marci {
1.18 + template <typename Graph, typename FlowMap, typename CapacityMap>
1.19 + typename FlowMap::ValueType 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::EdgeIt EdgeIt;
1.27 + typedef typename Graph::EachEdgeIt EachEdgeIt;
1.28 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.29 + typedef typename Graph::InEdgeIt InEdgeIt;
1.30 + typedef typename FlowMap::ValueType T;
1.31 +
1.32 + T flow_val = 0;
1.33 + T aug_val;
1.34 +
1.35 + for(EachEdgeIt e(G);G.valid(e);G.next(e))
1.36 + f.set(e,0);
1.37 +
1.38 + std::queue<NodeIt> bfs_queue;
1.39 + typename Graph::NodeMap<int> visited(G); //0: unvisited,
1.40 + //1: reached by a forward edge
1.41 + //2: reached by a backward edge
1.42 + //3: it is node s
1.43 + typename Graph::NodeMap<EdgeIt> tree(G);
1.44 +
1.45 + NodeIt gn; //FIXME: it might be too global for some people...
1.46 +
1.47 + augment:
1.48 +
1.49 + for(NodeIt n(G);G.valid(n);G.next(n))
1.50 + visited.set(n,0);
1.51 +
1.52 + visited.set(s,3);
1.53 +
1.54 + //There must be a better way to do this:
1.55 + while(!bfs_queue.empty()) bfs_queue.pop();
1.56 +
1.57 + bfs_queue.push(s);
1.58 +
1.59 + while(!bfs_queue.empty() && !visited.get(t))
1.60 + {
1.61 + NodeIt n(bfs_queue.front());
1.62 + for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
1.63 + if(f.get(e)<c.get(e) && //FIXME: <
1.64 + !visited.get(G.bNode(e)))
1.65 + {
1.66 + tree.set(G.bNode(e),e);
1.67 + visited.set(G.bNode(e),1);
1.68 + }
1.69 + for(InEdgeIt e(G,n);G.valid(e);G.next(e))
1.70 + if(f.get(e)>0 && //FIXME: >
1.71 + !visited.get(G.bNode(e)))
1.72 + {
1.73 + tree.set(G.bNode(e),e);
1.74 + visited.set(G.bNode(e),2);
1.75 + }
1.76 + }
1.77 +
1.78 + if(!visited.get(t)) return flow_val;
1.79 +
1.80 + // Augmenting value computation
1.81 + aug_val = visited.get(t)==2 ?
1.82 + c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t));
1.83 + //FIXME: I would need 'G.opposite(e,n)'
1.84 + gn = visited.get(t)==2 ? G.from(tree.get(t)) : G.to(tree.get(t));
1.85 + while(gn!=s) if(visited.get(gn)==2)
1.86 + {
1.87 + //FIXME: nonstandars. gcc extension!
1.88 + aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn));
1.89 + gn=G.from(tree.get(gn));
1.90 + }
1.91 + else {
1.92 + //FIXME: nonstandars. gcc extension!
1.93 + aug_val <?= f.get(tree.get(gn));
1.94 + gn=G.from(tree.get(gn));
1.95 + }
1.96 +
1.97 + // The augmentation itself
1.98 + gn = t;
1.99 + while(gn!=s) if(visited.get(gn)==2)
1.100 + {
1.101 + f.set(tree.get(gn),f.get(tree.get(gn))+aug_val);
1.102 + gn=G.from(tree.get(gn));
1.103 + }
1.104 + else {
1.105 + f.set(tree.get(gn),f.get(tree.get(gn))-aug_val);
1.106 + gn=G.from(tree.get(gn));
1.107 + }
1.108 +
1.109 + flow_val+=aug_val;
1.110 +
1.111 + goto augment; // Vivat goto forever!
1.112 + }
1.113 +
1.114 +} // namespace marci
1.115 +
1.116 +#endif //EDMONDS_KARP_HH