1.1 --- a/src/work/dijkstra.hh Fri Jan 30 14:55:10 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,192 +0,0 @@
1.4 -/*
1.5 - *dijkstra
1.6 - *by jacint
1.7 - *Performs Dijkstra's algorithm from node s.
1.8 - *
1.9 - *Constructor:
1.10 - *
1.11 - *dijkstra(graph_type& G, node_iterator s, edge_property_vector& distance)
1.12 - *
1.13 - *
1.14 - *
1.15 - *Member functions:
1.16 - *
1.17 - *void run()
1.18 - *
1.19 - * The following function should be used after run() was already run.
1.20 - *
1.21 - *
1.22 - *T dist(node_iterator v) : returns the distance from s to v.
1.23 - * It is 0 if v is not reachable from s.
1.24 - *
1.25 - *
1.26 - *edge_iterator pred(node_iterator v)
1.27 - * Returns the last edge of a shortest s-v path.
1.28 - * Returns an invalid iterator if v=s or v is not
1.29 - * reachable from s.
1.30 - *
1.31 - *
1.32 - *bool reach(node_iterator v) : true if v is reachable from s
1.33 - *
1.34 - *
1.35 - *
1.36 - *
1.37 - *
1.38 - *Problems:
1.39 - *
1.40 - *Heap implementation is needed, because the priority queue of stl
1.41 - *does not have a mathod for key-decrease, so we had to use here a
1.42 - *g\'any solution.
1.43 - *
1.44 - *The implementation of infinity would be desirable, see after line 100.
1.45 - */
1.46 -
1.47 -#ifndef DIJKSTRA_HH
1.48 -#define DIJKSTRA_HH
1.49 -
1.50 -#include <queue>
1.51 -#include <algorithm>
1.52 -
1.53 -#include <marci_graph_traits.hh>
1.54 -#include <marci_property_vector.hh>
1.55 -
1.56 -
1.57 -namespace std {
1.58 - namespace marci {
1.59 -
1.60 -
1.61 -
1.62 -
1.63 -
1.64 - template <typename graph_type, typename T>
1.65 - class dijkstra{
1.66 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.67 - typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
1.68 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.69 - typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
1.70 - typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
1.71 -
1.72 -
1.73 - graph_type& G;
1.74 - node_iterator s;
1.75 - node_property_vector<graph_type, edge_iterator> predecessor;
1.76 - node_property_vector<graph_type, T> distance;
1.77 - edge_property_vector<graph_type, T> length;
1.78 - node_property_vector<graph_type, bool> reached;
1.79 -
1.80 - public :
1.81 -
1.82 - /*
1.83 - The distance of all the nodes is 0.
1.84 - */
1.85 - dijkstra(graph_type& _G, node_iterator _s, edge_property_vector<graph_type, T>& _length) :
1.86 - G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { }
1.87 -
1.88 -
1.89 -
1.90 - /*By Misi.*/
1.91 - struct node_dist_comp
1.92 - {
1.93 - node_property_vector<graph_type, T> &d;
1.94 - node_dist_comp(node_property_vector<graph_type, T> &_d) : d(_d) {}
1.95 -
1.96 - bool operator()(const node_iterator& u, const node_iterator& v) const
1.97 - { return d.get(u) < d.get(v); }
1.98 - };
1.99 -
1.100 -
1.101 -
1.102 - void run() {
1.103 -
1.104 - node_property_vector<graph_type, bool> scanned(G, false);
1.105 - std::priority_queue<node_iterator, vector<node_iterator>, node_dist_comp>
1.106 - heap(( node_dist_comp(distance) ));
1.107 -
1.108 - heap.push(s);
1.109 - reached.put(s, true);
1.110 -
1.111 - while (!heap.empty()) {
1.112 -
1.113 - node_iterator v=heap.top();
1.114 - heap.pop();
1.115 -
1.116 -
1.117 - if (!scanned.get(v)) {
1.118 -
1.119 - for(out_edge_iterator e=G.first_out_edge(v); e.valid(); ++e) {
1.120 - node_iterator w=G.head(e);
1.121 -
1.122 - if (!scanned.get(w)) {
1.123 - if (!reached.get(w)) {
1.124 - reached.put(w,true);
1.125 - distance.put(w, distance.get(v)-length.get(e));
1.126 - predecessor.put(w,e);
1.127 - } else if (distance.get(v)-length.get(e)>distance.get(w)) {
1.128 - distance.put(w, distance.get(v)-length.get(e));
1.129 - predecessor.put(w,e);
1.130 - }
1.131 -
1.132 - heap.push(w);
1.133 -
1.134 - }
1.135 -
1.136 - }
1.137 - scanned.put(v,true);
1.138 -
1.139 - } // if (!scanned.get(v))
1.140 -
1.141 -
1.142 -
1.143 - } // while (!heap.empty())
1.144 -
1.145 -
1.146 - } //void run()
1.147 -
1.148 -
1.149 -
1.150 -
1.151 -
1.152 - /*
1.153 - *Returns the distance of the node v.
1.154 - *It is 0 for the root and for the nodes not
1.155 - *reachable form the root.
1.156 - */
1.157 - T dist(node_iterator v) {
1.158 - return -distance.get(v);
1.159 - }
1.160 -
1.161 -
1.162 -
1.163 - /*
1.164 - * Returns the last edge of a shortest s-v path.
1.165 - * Returns an invalid iterator if v=root or v is not
1.166 - * reachable from the root.
1.167 - */
1.168 - edge_iterator pred(node_iterator v) {
1.169 - if (v!=s) { return predecessor.get(v);}
1.170 - else {return edge_iterator();}
1.171 - }
1.172 -
1.173 -
1.174 -
1.175 - bool reach(node_iterator v) {
1.176 - return reached.get(v);
1.177 - }
1.178 -
1.179 -
1.180 -
1.181 -
1.182 -
1.183 -
1.184 -
1.185 -
1.186 -
1.187 - };// class dijkstra
1.188 -
1.189 -
1.190 -
1.191 - } // namespace marci
1.192 -}
1.193 -#endif //DIJKSTRA_HH
1.194 -
1.195 -
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/jacint/dijkstra.hh Fri Jan 30 14:56:11 2004 +0000
2.3 @@ -0,0 +1,192 @@
2.4 +/*
2.5 + *dijkstra
2.6 + *by jacint
2.7 + *Performs Dijkstra's algorithm from node s.
2.8 + *
2.9 + *Constructor:
2.10 + *
2.11 + *dijkstra(graph_type& G, node_iterator s, edge_property_vector& distance)
2.12 + *
2.13 + *
2.14 + *
2.15 + *Member functions:
2.16 + *
2.17 + *void run()
2.18 + *
2.19 + * The following function should be used after run() was already run.
2.20 + *
2.21 + *
2.22 + *T dist(node_iterator v) : returns the distance from s to v.
2.23 + * It is 0 if v is not reachable from s.
2.24 + *
2.25 + *
2.26 + *edge_iterator pred(node_iterator v)
2.27 + * Returns the last edge of a shortest s-v path.
2.28 + * Returns an invalid iterator if v=s or v is not
2.29 + * reachable from s.
2.30 + *
2.31 + *
2.32 + *bool reach(node_iterator v) : true if v is reachable from s
2.33 + *
2.34 + *
2.35 + *
2.36 + *
2.37 + *
2.38 + *Problems:
2.39 + *
2.40 + *Heap implementation is needed, because the priority queue of stl
2.41 + *does not have a mathod for key-decrease, so we had to use here a
2.42 + *g\'any solution.
2.43 + *
2.44 + *The implementation of infinity would be desirable, see after line 100.
2.45 + */
2.46 +
2.47 +#ifndef DIJKSTRA_HH
2.48 +#define DIJKSTRA_HH
2.49 +
2.50 +#include <queue>
2.51 +#include <algorithm>
2.52 +
2.53 +#include <marci_graph_traits.hh>
2.54 +#include <marci_property_vector.hh>
2.55 +
2.56 +
2.57 +namespace std {
2.58 + namespace marci {
2.59 +
2.60 +
2.61 +
2.62 +
2.63 +
2.64 + template <typename graph_type, typename T>
2.65 + class dijkstra{
2.66 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
2.67 + typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
2.68 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
2.69 + typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
2.70 + typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
2.71 +
2.72 +
2.73 + graph_type& G;
2.74 + node_iterator s;
2.75 + node_property_vector<graph_type, edge_iterator> predecessor;
2.76 + node_property_vector<graph_type, T> distance;
2.77 + edge_property_vector<graph_type, T> length;
2.78 + node_property_vector<graph_type, bool> reached;
2.79 +
2.80 + public :
2.81 +
2.82 + /*
2.83 + The distance of all the nodes is 0.
2.84 + */
2.85 + dijkstra(graph_type& _G, node_iterator _s, edge_property_vector<graph_type, T>& _length) :
2.86 + G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { }
2.87 +
2.88 +
2.89 +
2.90 + /*By Misi.*/
2.91 + struct node_dist_comp
2.92 + {
2.93 + node_property_vector<graph_type, T> &d;
2.94 + node_dist_comp(node_property_vector<graph_type, T> &_d) : d(_d) {}
2.95 +
2.96 + bool operator()(const node_iterator& u, const node_iterator& v) const
2.97 + { return d.get(u) < d.get(v); }
2.98 + };
2.99 +
2.100 +
2.101 +
2.102 + void run() {
2.103 +
2.104 + node_property_vector<graph_type, bool> scanned(G, false);
2.105 + std::priority_queue<node_iterator, vector<node_iterator>, node_dist_comp>
2.106 + heap(( node_dist_comp(distance) ));
2.107 +
2.108 + heap.push(s);
2.109 + reached.put(s, true);
2.110 +
2.111 + while (!heap.empty()) {
2.112 +
2.113 + node_iterator v=heap.top();
2.114 + heap.pop();
2.115 +
2.116 +
2.117 + if (!scanned.get(v)) {
2.118 +
2.119 + for(out_edge_iterator e=G.first_out_edge(v); e.valid(); ++e) {
2.120 + node_iterator w=G.head(e);
2.121 +
2.122 + if (!scanned.get(w)) {
2.123 + if (!reached.get(w)) {
2.124 + reached.put(w,true);
2.125 + distance.put(w, distance.get(v)-length.get(e));
2.126 + predecessor.put(w,e);
2.127 + } else if (distance.get(v)-length.get(e)>distance.get(w)) {
2.128 + distance.put(w, distance.get(v)-length.get(e));
2.129 + predecessor.put(w,e);
2.130 + }
2.131 +
2.132 + heap.push(w);
2.133 +
2.134 + }
2.135 +
2.136 + }
2.137 + scanned.put(v,true);
2.138 +
2.139 + } // if (!scanned.get(v))
2.140 +
2.141 +
2.142 +
2.143 + } // while (!heap.empty())
2.144 +
2.145 +
2.146 + } //void run()
2.147 +
2.148 +
2.149 +
2.150 +
2.151 +
2.152 + /*
2.153 + *Returns the distance of the node v.
2.154 + *It is 0 for the root and for the nodes not
2.155 + *reachable form the root.
2.156 + */
2.157 + T dist(node_iterator v) {
2.158 + return -distance.get(v);
2.159 + }
2.160 +
2.161 +
2.162 +
2.163 + /*
2.164 + * Returns the last edge of a shortest s-v path.
2.165 + * Returns an invalid iterator if v=root or v is not
2.166 + * reachable from the root.
2.167 + */
2.168 + edge_iterator pred(node_iterator v) {
2.169 + if (v!=s) { return predecessor.get(v);}
2.170 + else {return edge_iterator();}
2.171 + }
2.172 +
2.173 +
2.174 +
2.175 + bool reach(node_iterator v) {
2.176 + return reached.get(v);
2.177 + }
2.178 +
2.179 +
2.180 +
2.181 +
2.182 +
2.183 +
2.184 +
2.185 +
2.186 +
2.187 + };// class dijkstra
2.188 +
2.189 +
2.190 +
2.191 + } // namespace marci
2.192 +}
2.193 +#endif //DIJKSTRA_HH
2.194 +
2.195 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/jacint/reverse_bfs.hh Fri Jan 30 14:56:11 2004 +0000
3.3 @@ -0,0 +1,94 @@
3.4 +/*
3.5 +reverse_bfs
3.6 +by jacint
3.7 +Performs a bfs on the out edges. It does not count predecessors,
3.8 +only the distances, but one can easily modify it to know the pred as well.
3.9 +
3.10 +Constructor:
3.11 +
3.12 +reverse_bfs(graph_type& G, node_iterator t)
3.13 +
3.14 +
3.15 +
3.16 +Member functions:
3.17 +
3.18 +void run(): runs a reverse bfs from t
3.19 +
3.20 + The following function should be used after run() was already run.
3.21 +
3.22 +int dist(node_iterator v) : returns the distance from v to t. It is the number of nodes if t is not reachable from v.
3.23 +
3.24 +*/
3.25 +#ifndef REVERSE_BFS_HH
3.26 +#define REVERSE_BFS_HH
3.27 +
3.28 +#include <queue>
3.29 +
3.30 +#include <marci_graph_traits.hh>
3.31 +#include <marci_property_vector.hh>
3.32 +
3.33 +
3.34 +
3.35 +namespace marci {
3.36 +
3.37 + template <typename graph_type>
3.38 + class reverse_bfs {
3.39 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
3.40 + //typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
3.41 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
3.42 + typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
3.43 +
3.44 +
3.45 + graph_type& G;
3.46 + node_iterator t;
3.47 +// node_property_vector<graph_type, edge_iterator> pred;
3.48 + node_property_vector<graph_type, int> distance;
3.49 +
3.50 +
3.51 + public :
3.52 +
3.53 + /*
3.54 + The distance of the nodes is n, except t for which it is 0.
3.55 + */
3.56 + reverse_bfs(graph_type& _G, node_iterator _t) : G(_G), t(_t), distance(G, number_of(G.first_node())) {
3.57 + distance.put(t,0);
3.58 + }
3.59 +
3.60 + void run() {
3.61 +
3.62 + node_property_vector<graph_type, bool> reached(G, false);
3.63 + reached.put(t, true);
3.64 +
3.65 + std::queue<node_iterator> bfs_queue;
3.66 + bfs_queue.push(t);
3.67 +
3.68 + while (!bfs_queue.empty()) {
3.69 +
3.70 + node_iterator v=bfs_queue.front();
3.71 + bfs_queue.pop();
3.72 +
3.73 + for(in_edge_iterator e=G.first_in_edge(v); e.valid(); ++e) {
3.74 + node_iterator w=G.tail(e);
3.75 + if (!reached.get(w)) {
3.76 + bfs_queue.push(w);
3.77 + distance.put(w, distance.get(v)+1);
3.78 + reached.put(w, true);
3.79 + }
3.80 + }
3.81 + }
3.82 + }
3.83 +
3.84 +
3.85 +
3.86 + int dist(node_iterator v) {
3.87 + return distance.get(v);
3.88 + }
3.89 +
3.90 +
3.91 + };
3.92 +
3.93 +} // namespace marci
3.94 +
3.95 +#endif //REVERSE_BFS_HH
3.96 +
3.97 +
4.1 --- a/src/work/preflow_push_hl.hh Fri Jan 30 14:55:10 2004 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,320 +0,0 @@
4.4 -/*
4.5 -preflow_push_hl.hh
4.6 -by jacint.
4.7 -Runs the highest label variant of the preflow push algorithm with
4.8 -running time O(n^2\sqrt(m)).
4.9 -
4.10 -Member functions:
4.11 -
4.12 -void run() : runs the algorithm
4.13 -
4.14 - The following functions should be used after run() was already run.
4.15 -
4.16 -T maxflow() : returns the value of a maximum flow
4.17 -
4.18 -T flowonedge(edge_iterator e) : for a fixed maximum flow x it returns x(e)
4.19 -
4.20 -edge_property_vector<graph_type, T> allflow() : returns the fixed maximum flow x
4.21 -
4.22 -node_property_vector<graph_type, bool> mincut() : returns a
4.23 - characteristic vector of a minimum cut. (An empty level
4.24 - in the algorithm gives a minimum cut.)
4.25 -*/
4.26 -
4.27 -#ifndef PREFLOW_PUSH_HL_HH
4.28 -#define PREFLOW_PUSH_HL_HH
4.29 -
4.30 -#include <algorithm>
4.31 -#include <vector>
4.32 -#include <stack>
4.33 -
4.34 -#include <marci_graph_traits.hh>
4.35 -#include <marci_property_vector.hh>
4.36 -#include <reverse_bfs.hh>
4.37 -
4.38 -namespace marci {
4.39 -
4.40 - template <typename graph_type, typename T>
4.41 - class preflow_push_hl {
4.42 -
4.43 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
4.44 - typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
4.45 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
4.46 - typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
4.47 - typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
4.48 - typedef typename graph_traits<graph_type>::each_edge_iterator each_edge_iterator;
4.49 -
4.50 -
4.51 - graph_type& G;
4.52 - node_iterator s;
4.53 - node_iterator t;
4.54 - edge_property_vector<graph_type, T> flow;
4.55 - edge_property_vector<graph_type, T>& capacity;
4.56 - T value;
4.57 - node_property_vector<graph_type, bool> mincutvector;
4.58 -
4.59 -
4.60 - public:
4.61 -
4.62 - preflow_push_hl(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { }
4.63 -
4.64 -
4.65 -
4.66 -
4.67 - /*
4.68 - The run() function runs the highest label preflow-push,
4.69 - running time: O(n^2\sqrt(m))
4.70 - */
4.71 - void run() {
4.72 -
4.73 - node_property_vector<graph_type, int> level(G); //level of node
4.74 - node_property_vector<graph_type, T> excess(G); //excess of node
4.75 -
4.76 - int n=number_of(G.first_node()); //number of nodes
4.77 - int b=n;
4.78 - /*b is a bound on the highest level of an active node. In the beginning it is at most n-2.*/
4.79 -
4.80 - std::vector<std::stack<node_iterator> > stack(2*n-1); //Stack of the active nodes in level i.
4.81 -
4.82 -
4.83 -
4.84 -
4.85 - /*Reverse_bfs from t, to find the starting level.*/
4.86 -
4.87 - reverse_bfs<list_graph> bfs(G, t);
4.88 - bfs.run();
4.89 - for(each_node_iterator v=G.first_node(); v.valid(); ++v) {
4.90 - level.put(v, bfs.dist(v));
4.91 - //std::cout << "the level of " << v << " is " << bfs.dist(v);
4.92 - }
4.93 -
4.94 - /*The level of s is fixed to n*/
4.95 - level.put(s,n);
4.96 -
4.97 -
4.98 -
4.99 -
4.100 -
4.101 - /* Starting flow. It is everywhere 0 at the moment. */
4.102 -
4.103 - for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i)
4.104 - {
4.105 - node_iterator w=G.head(i);
4.106 - flow.put(i, capacity.get(i));
4.107 - stack[bfs.dist(w)].push(w);
4.108 - excess.put(w, capacity.get(i));
4.109 - }
4.110 -
4.111 -
4.112 - /*
4.113 - End of preprocessing
4.114 - */
4.115 -
4.116 -
4.117 -
4.118 - /*
4.119 - Push/relabel on the highest level active nodes.
4.120 - */
4.121 -
4.122 - /*While there exists active node.*/
4.123 - while (b) {
4.124 -
4.125 - /*We decrease the bound if there is no active node of level b.*/
4.126 - if (stack[b].empty()) {
4.127 - --b;
4.128 - } else {
4.129 -
4.130 - node_iterator w=stack[b].top(); //w is the highest label active node.
4.131 - stack[b].pop(); //We delete w from the stack.
4.132 -
4.133 - int newlevel=2*n-2; //In newlevel we maintain the next level of w.
4.134 -
4.135 - for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
4.136 - node_iterator v=G.head(e);
4.137 - /*e is the edge wv.*/
4.138 -
4.139 - if (flow.get(e)<capacity.get(e)) {
4.140 - /*e is an edge of the residual graph */
4.141 -
4.142 - if(level.get(w)==level.get(v)+1) {
4.143 - /*Push is allowed now*/
4.144 -
4.145 - if (capacity.get(e)-flow.get(e) > excess.get(w)) {
4.146 - /*A nonsaturating push.*/
4.147 -
4.148 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
4.149 - /*v becomes active.*/
4.150 -
4.151 - flow.put(e, flow.get(e)+excess.get(w));
4.152 - excess.put(v, excess.get(v)+excess.get(w));
4.153 - excess.put(w,0);
4.154 - //std::cout << w << " " << v <<" elore elen nonsat pump " << std::endl;
4.155 - break;
4.156 - } else {
4.157 - /*A saturating push.*/
4.158 -
4.159 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
4.160 - /*v becomes active.*/
4.161 -
4.162 - excess.put(v, excess.get(v)+capacity.get(e)-flow.get(e));
4.163 - excess.put(w, excess.get(w)-capacity.get(e)+flow.get(e));
4.164 - flow.put(e, capacity.get(e));
4.165 - //std::cout << w<<" " <<v<<" elore elen sat pump " << std::endl;
4.166 - if (excess.get(w)==0) break;
4.167 - /*If w is not active any more, then we go on to the next node.*/
4.168 -
4.169 - } // if (capacity.get(e)-flow.get(e) > excess.get(w))
4.170 - } // if(level.get(w)==level.get(v)+1)
4.171 -
4.172 - else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
4.173 -
4.174 - } //if (flow.get(e)<capacity.get(e))
4.175 -
4.176 - } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e)
4.177 -
4.178 -
4.179 -
4.180 - for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
4.181 - node_iterator v=G.tail(e);
4.182 - /*e is the edge vw.*/
4.183 -
4.184 - if (excess.get(w)==0) break;
4.185 - /*It may happen, that w became inactive in the first for cycle.*/
4.186 - if(flow.get(e)>0) {
4.187 - /*e is an edge of the residual graph */
4.188 -
4.189 - if(level.get(w)==level.get(v)+1) {
4.190 - /*Push is allowed now*/
4.191 -
4.192 - if (flow.get(e) > excess.get(w)) {
4.193 - /*A nonsaturating push.*/
4.194 -
4.195 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
4.196 - /*v becomes active.*/
4.197 -
4.198 - flow.put(e, flow.get(e)-excess.get(w));
4.199 - excess.put(v, excess.get(v)+excess.get(w));
4.200 - excess.put(w,0);
4.201 - //std::cout << v << " " << w << " vissza elen nonsat pump " << std::endl;
4.202 - break;
4.203 - } else {
4.204 - /*A saturating push.*/
4.205 -
4.206 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
4.207 - /*v becomes active.*/
4.208 -
4.209 - excess.put(v, excess.get(v)+flow.get(e));
4.210 - excess.put(w, excess.get(w)-flow.get(e));
4.211 - flow.put(e,0);
4.212 - //std::cout << v <<" " << w << " vissza elen sat pump " << std::endl;
4.213 - if (excess.get(w)==0) { break;}
4.214 - } //if (flow.get(e) > excess.get(v))
4.215 - } //if(level.get(w)==level.get(v)+1)
4.216 -
4.217 - else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
4.218 -
4.219 -
4.220 - } //if (flow.get(e)>0)
4.221 -
4.222 - } //for
4.223 -
4.224 -
4.225 - if (excess.get(w)>0) {
4.226 - level.put(w,++newlevel);
4.227 - stack[newlevel].push(w);
4.228 - b=newlevel;
4.229 - //std::cout << "The new level of " << w << " is "<< newlevel <<std::endl;
4.230 - }
4.231 -
4.232 -
4.233 - } //else
4.234 -
4.235 - } //while(b)
4.236 -
4.237 - value = excess.get(t);
4.238 - /*Max flow value.*/
4.239 -
4.240 -
4.241 -
4.242 -
4.243 - } //void run()
4.244 -
4.245 -
4.246 -
4.247 -
4.248 -
4.249 - /*
4.250 - Returns the maximum value of a flow.
4.251 - */
4.252 -
4.253 - T maxflow() {
4.254 - return value;
4.255 - }
4.256 -
4.257 -
4.258 -
4.259 - /*
4.260 - For the maximum flow x found by the algorithm, it returns the flow value on edge e, i.e. x(e).
4.261 - */
4.262 -
4.263 - T flowonedge(edge_iterator e) {
4.264 - return flow.get(e);
4.265 - }
4.266 -
4.267 -
4.268 -
4.269 - /*
4.270 - Returns the maximum flow x found by the algorithm.
4.271 - */
4.272 -
4.273 - edge_property_vector<graph_type, T> allflow() {
4.274 - return flow;
4.275 - }
4.276 -
4.277 -
4.278 -
4.279 - /*
4.280 - Returns a minimum cut by using a reverse bfs from t in the residual graph.
4.281 - */
4.282 -
4.283 - node_property_vector<graph_type, bool> mincut() {
4.284 -
4.285 - std::queue<node_iterator> queue;
4.286 -
4.287 - mincutvector.put(t,false);
4.288 - queue.push(t);
4.289 -
4.290 - while (!queue.empty()) {
4.291 - node_iterator w=queue.front();
4.292 - queue.pop();
4.293 -
4.294 - for(in_edge_iterator e=G.first_in_edge(w) ; e.valid(); ++e) {
4.295 - node_iterator v=G.tail(e);
4.296 - if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) {
4.297 - queue.push(v);
4.298 - mincutvector.put(v, false);
4.299 - }
4.300 - } // for
4.301 -
4.302 - for(out_edge_iterator e=G.first_out_edge(w) ; e.valid(); ++e) {
4.303 - node_iterator v=G.head(e);
4.304 - if (mincutvector.get(v) && flow.get(e) > 0 ) {
4.305 - queue.push(v);
4.306 - mincutvector.put(v, false);
4.307 - }
4.308 - } // for
4.309 -
4.310 - }
4.311 -
4.312 - return mincutvector;
4.313 -
4.314 - }
4.315 -
4.316 -
4.317 - };
4.318 -}//namespace marci
4.319 -#endif
4.320 -
4.321 -
4.322 -
4.323 -
5.1 --- a/src/work/preflow_push_max_flow.hh Fri Jan 30 14:55:10 2004 +0000
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,315 +0,0 @@
5.4 -/*
5.5 -preflow_push_max_flow_hh
5.6 -by jacint.
5.7 -Runs a preflow push algorithm with the modification,
5.8 -that we do not push on nodes with level at least n.
5.9 -Moreover, if a level gets empty, we put all nodes above that
5.10 -level to level n. Hence, in the end, we arrive at a maximum preflow
5.11 -with value of a max flow value. An empty level gives a minimum cut.
5.12 -
5.13 -Member functions:
5.14 -
5.15 -void run() : runs the algorithm
5.16 -
5.17 - The following functions should be used after run() was already run.
5.18 -
5.19 -T maxflow() : returns the value of a maximum flow
5.20 -
5.21 -node_property_vector<graph_type, bool> mincut(): returns a
5.22 - characteristic vector of a minimum cut.
5.23 -*/
5.24 -
5.25 -#ifndef PREFLOW_PUSH_MAX_FLOW_HH
5.26 -#define PREFLOW_PUSH_MAX_FLOW_HH
5.27 -
5.28 -#include <algorithm>
5.29 -#include <vector>
5.30 -#include <stack>
5.31 -
5.32 -#include <marci_list_graph.hh>
5.33 -#include <marci_graph_traits.hh>
5.34 -#include <marci_property_vector.hh>
5.35 -#include <reverse_bfs.hh>
5.36 -
5.37 -
5.38 -namespace marci {
5.39 -
5.40 - template <typename graph_type, typename T>
5.41 - class preflow_push_max_flow {
5.42 -
5.43 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
5.44 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
5.45 - typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
5.46 - typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
5.47 -
5.48 - graph_type& G;
5.49 - node_iterator s;
5.50 - node_iterator t;
5.51 - edge_property_vector<graph_type, T>& capacity;
5.52 - T value;
5.53 - node_property_vector<graph_type, bool> mincutvector;
5.54 -
5.55 -
5.56 -
5.57 - public:
5.58 -
5.59 - preflow_push_max_flow(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { }
5.60 -
5.61 -
5.62 - /*
5.63 - The run() function runs a modified version of the highest label preflow-push, which only
5.64 - finds a maximum preflow, hence giving the value of a maximum flow.
5.65 - */
5.66 - void run() {
5.67 -
5.68 - edge_property_vector<graph_type, T> flow(G, 0); //the flow value, 0 everywhere
5.69 - node_property_vector<graph_type, int> level(G); //level of node
5.70 - node_property_vector<graph_type, T> excess(G); //excess of node
5.71 -
5.72 - int n=number_of(G.first_node()); //number of nodes
5.73 - int b=n-2;
5.74 - /*b is a bound on the highest level of an active node. In the beginning it is at most n-2.*/
5.75 -
5.76 - std::vector<int> numb(n); //The number of nodes on level i < n.
5.77 -
5.78 - std::vector<std::stack<node_iterator> > stack(2*n-1); //Stack of the active nodes in level i.
5.79 -
5.80 -
5.81 -
5.82 - /*Reverse_bfs from t, to find the starting level.*/
5.83 -
5.84 - reverse_bfs<list_graph> bfs(G, t);
5.85 - bfs.run();
5.86 - for(each_node_iterator v=G.first_node(); v.valid(); ++v)
5.87 - {
5.88 - int dist=bfs.dist(v);
5.89 - level.put(v, dist);
5.90 - ++numb[dist];
5.91 - }
5.92 -
5.93 - /*The level of s is fixed to n*/
5.94 - level.put(s,n);
5.95 -
5.96 -
5.97 - /* Starting flow. It is everywhere 0 at the moment. */
5.98 -
5.99 - for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i)
5.100 - {
5.101 - node_iterator w=G.head(i);
5.102 - flow.put(i, capacity.get(i));
5.103 - stack[bfs.dist(w)].push(w);
5.104 - excess.put(w, capacity.get(i));
5.105 - }
5.106 -
5.107 -
5.108 - /*
5.109 - End of preprocessing
5.110 - */
5.111 -
5.112 -
5.113 -
5.114 -
5.115 - /*
5.116 - Push/relabel on the highest level active nodes.
5.117 - */
5.118 -
5.119 - /*While there exists an active node.*/
5.120 - while (b) {
5.121 -
5.122 - /*We decrease the bound if there is no active node of level b.*/
5.123 - if (stack[b].empty()) {
5.124 - --b;
5.125 - } else {
5.126 -
5.127 - node_iterator w=stack[b].top(); //w is the highest label active node.
5.128 - stack[b].pop(); //We delete w from the stack.
5.129 -
5.130 - int newlevel=2*n-2; //In newlevel we maintain the next level of w.
5.131 -
5.132 - for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
5.133 - node_iterator v=G.head(e);
5.134 - /*e is the edge wv.*/
5.135 -
5.136 - if (flow.get(e)<capacity.get(e)) {
5.137 - /*e is an edge of the residual graph */
5.138 -
5.139 - if(level.get(w)==level.get(v)+1) {
5.140 - /*Push is allowed now*/
5.141 -
5.142 - if (capacity.get(e)-flow.get(e) > excess.get(w)) {
5.143 - /*A nonsaturating push.*/
5.144 -
5.145 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
5.146 - /*v becomes active.*/
5.147 -
5.148 - flow.put(e, flow.get(e)+excess.get(w));
5.149 - excess.put(v, excess.get(v)+excess.get(w));
5.150 - excess.put(w,0);
5.151 - //std::cout << w << " " << v <<" elore elen nonsat pump " << std::endl;
5.152 - break;
5.153 - } else {
5.154 - /*A saturating push.*/
5.155 -
5.156 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
5.157 - /*v becomes active.*/
5.158 -
5.159 - excess.put(v, excess.get(v)+capacity.get(e)-flow.get(e));
5.160 - excess.put(w, excess.get(w)-capacity.get(e)+flow.get(e));
5.161 - flow.put(e, capacity.get(e));
5.162 - //std::cout << w <<" " << v <<" elore elen sat pump " << std::endl;
5.163 - if (excess.get(w)==0) break;
5.164 - /*If w is not active any more, then we go on to the next node.*/
5.165 -
5.166 - } // if (capacity.get(e)-flow.get(e) > excess.get(w))
5.167 - } // if (level.get(w)==level.get(v)+1)
5.168 -
5.169 - else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
5.170 -
5.171 - } //if (flow.get(e)<capacity.get(e))
5.172 -
5.173 - } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e)
5.174 -
5.175 -
5.176 -
5.177 - for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
5.178 - node_iterator v=G.tail(e);
5.179 - /*e is the edge vw.*/
5.180 -
5.181 - if (excess.get(w)==0) break;
5.182 - /*It may happen, that w became inactive in the first 'for' cycle.*/
5.183 -
5.184 - if(flow.get(e)>0) {
5.185 - /*e is an edge of the residual graph */
5.186 -
5.187 - if(level.get(w)==level.get(v)+1) {
5.188 - /*Push is allowed now*/
5.189 -
5.190 - if (flow.get(e) > excess.get(w)) {
5.191 - /*A nonsaturating push.*/
5.192 -
5.193 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
5.194 - /*v becomes active.*/
5.195 -
5.196 - flow.put(e, flow.get(e)-excess.get(w));
5.197 - excess.put(v, excess.get(v)+excess.get(w));
5.198 - excess.put(w,0);
5.199 - //std::cout << v << " " << w << " vissza elen nonsat pump " << std::endl;
5.200 - break;
5.201 - } else {
5.202 - /*A saturating push.*/
5.203 -
5.204 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
5.205 - /*v becomes active.*/
5.206 -
5.207 - flow.put(e,0);
5.208 - excess.put(v, excess.get(v)+flow.get(e));
5.209 - excess.put(w, excess.get(w)-flow.get(e));
5.210 - //std::cout << v <<" " << w << " vissza elen sat pump " << std::endl;
5.211 - if (excess.get(w)==0) { break;}
5.212 - } //if (flow.get(e) > excess.get(v))
5.213 - } //if(level.get(w)==level.get(v)+1)
5.214 -
5.215 - else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
5.216 - //std::cout << "Leveldecrease of node " << w << " to " << newlevel << std::endl;
5.217 -
5.218 - } //if (flow.get(e)>0)
5.219 -
5.220 - } //for in-edge
5.221 -
5.222 -
5.223 -
5.224 -
5.225 - /*
5.226 - Relabel
5.227 - */
5.228 - if (excess.get(w)>0) {
5.229 - /*Now newlevel <= n*/
5.230 -
5.231 - int l=level.get(w); //l is the old level of w.
5.232 - --numb[l];
5.233 -
5.234 - if (newlevel == n) {
5.235 - level.put(w,n);
5.236 -
5.237 - } else {
5.238 -
5.239 - if (numb[l]) {
5.240 - /*If the level of w remains nonempty.*/
5.241 -
5.242 - level.put(w,++newlevel);
5.243 - ++numb[newlevel];
5.244 - stack[newlevel].push(w);
5.245 - b=newlevel;
5.246 - } else {
5.247 - /*If the level of w gets empty.*/
5.248 -
5.249 - for (each_node_iterator v=G.first_node() ; v.valid() ; ++v) {
5.250 - if (level.get(v) >= l ) {
5.251 - level.put(v,n);
5.252 - }
5.253 - }
5.254 -
5.255 - for (int i=l+1 ; i!=n ; ++i) numb[i]=0;
5.256 - } //if (numb[l])
5.257 -
5.258 - } // if (newlevel = n)
5.259 -
5.260 - } // if (excess.get(w)>0)
5.261 -
5.262 -
5.263 - } //else
5.264 -
5.265 - } //while(b)
5.266 -
5.267 - value=excess.get(t);
5.268 - /*Max flow value.*/
5.269 -
5.270 -
5.271 -
5.272 - /*
5.273 - We find an empty level, e. The nodes above this level give
5.274 - a minimum cut.
5.275 - */
5.276 -
5.277 - int e=1;
5.278 -
5.279 - while(e) {
5.280 - if(numb[e]) ++e;
5.281 - else break;
5.282 - }
5.283 - for (each_node_iterator v=G.first_node(); v.valid(); ++v) {
5.284 - if (level.get(v) > e) mincutvector.put(v, true);
5.285 - }
5.286 -
5.287 -
5.288 - } // void run()
5.289 -
5.290 -
5.291 -
5.292 - /*
5.293 - Returns the maximum value of a flow.
5.294 - */
5.295 -
5.296 - T maxflow() {
5.297 - return value;
5.298 - }
5.299 -
5.300 -
5.301 -
5.302 - /*
5.303 - Returns a minimum cut.
5.304 - */
5.305 -
5.306 - node_property_vector<graph_type, bool> mincut() {
5.307 - return mincutvector;
5.308 - }
5.309 -
5.310 -
5.311 - };
5.312 -}//namespace marci
5.313 -#endif
5.314 -
5.315 -
5.316 -
5.317 -
5.318 -
6.1 --- a/src/work/reverse_bfs.hh Fri Jan 30 14:55:10 2004 +0000
6.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
6.3 @@ -1,94 +0,0 @@
6.4 -/*
6.5 -reverse_bfs
6.6 -by jacint
6.7 -Performs a bfs on the out edges. It does not count predecessors,
6.8 -only the distances, but one can easily modify it to know the pred as well.
6.9 -
6.10 -Constructor:
6.11 -
6.12 -reverse_bfs(graph_type& G, node_iterator t)
6.13 -
6.14 -
6.15 -
6.16 -Member functions:
6.17 -
6.18 -void run(): runs a reverse bfs from t
6.19 -
6.20 - The following function should be used after run() was already run.
6.21 -
6.22 -int dist(node_iterator v) : returns the distance from v to t. It is the number of nodes if t is not reachable from v.
6.23 -
6.24 -*/
6.25 -#ifndef REVERSE_BFS_HH
6.26 -#define REVERSE_BFS_HH
6.27 -
6.28 -#include <queue>
6.29 -
6.30 -#include <marci_graph_traits.hh>
6.31 -#include <marci_property_vector.hh>
6.32 -
6.33 -
6.34 -
6.35 -namespace marci {
6.36 -
6.37 - template <typename graph_type>
6.38 - class reverse_bfs {
6.39 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
6.40 - //typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
6.41 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
6.42 - typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
6.43 -
6.44 -
6.45 - graph_type& G;
6.46 - node_iterator t;
6.47 -// node_property_vector<graph_type, edge_iterator> pred;
6.48 - node_property_vector<graph_type, int> distance;
6.49 -
6.50 -
6.51 - public :
6.52 -
6.53 - /*
6.54 - The distance of the nodes is n, except t for which it is 0.
6.55 - */
6.56 - reverse_bfs(graph_type& _G, node_iterator _t) : G(_G), t(_t), distance(G, number_of(G.first_node())) {
6.57 - distance.put(t,0);
6.58 - }
6.59 -
6.60 - void run() {
6.61 -
6.62 - node_property_vector<graph_type, bool> reached(G, false);
6.63 - reached.put(t, true);
6.64 -
6.65 - std::queue<node_iterator> bfs_queue;
6.66 - bfs_queue.push(t);
6.67 -
6.68 - while (!bfs_queue.empty()) {
6.69 -
6.70 - node_iterator v=bfs_queue.front();
6.71 - bfs_queue.pop();
6.72 -
6.73 - for(in_edge_iterator e=G.first_in_edge(v); e.valid(); ++e) {
6.74 - node_iterator w=G.tail(e);
6.75 - if (!reached.get(w)) {
6.76 - bfs_queue.push(w);
6.77 - distance.put(w, distance.get(v)+1);
6.78 - reached.put(w, true);
6.79 - }
6.80 - }
6.81 - }
6.82 - }
6.83 -
6.84 -
6.85 -
6.86 - int dist(node_iterator v) {
6.87 - return distance.get(v);
6.88 - }
6.89 -
6.90 -
6.91 - };
6.92 -
6.93 -} // namespace marci
6.94 -
6.95 -#endif //REVERSE_BFS_HH
6.96 -
6.97 -