1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/athos/makefile Tue Jan 27 16:23:51 2004 +0000
1.3 @@ -0,0 +1,7 @@
1.4 +CXXFLAGS = -Wall -ansi -g
1.5 +CXX = g++-3.0
1.6 +
1.7 +pf_demo: pf_demo.cc ../marci_graph_traits.hh ../marci_list_graph.hh ../marci_property_vector.hh preflow_push.hh ../reverse_bfs.hh
1.8 + $(CXX) $(CXXFLAGS) -I. -I.. pf_demo.cc -o pf_demo
1.9 +
1.10 +
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/athos/pf_demo.cc Tue Jan 27 16:23:51 2004 +0000
2.3 @@ -0,0 +1,172 @@
2.4 +#include <iostream>
2.5 +#include <vector>
2.6 +#include <string>
2.7 +
2.8 +#include "marci_list_graph.hh"
2.9 +#include "marci_graph_traits.hh"
2.10 +#include "marci_property_vector.hh"
2.11 +#include "preflow_push.hh"
2.12 +
2.13 +using namespace marci;
2.14 +
2.15 +
2.16 +int main (int, char*[])
2.17 +{
2.18 + typedef graph_traits<list_graph>::node_iterator node_iterator;
2.19 + typedef graph_traits<list_graph>::edge_iterator edge_iterator;
2.20 + typedef graph_traits<list_graph>::each_node_iterator each_node_iterator;
2.21 + typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator;
2.22 + typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator;
2.23 + typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;
2.24 + typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;
2.25 +
2.26 + list_graph flow_test;
2.27 +
2.28 +
2.29 + //Ahuja könyv példája
2.30 + node_iterator s=flow_test.add_node();
2.31 + node_iterator v2=flow_test.add_node();
2.32 + node_iterator v3=flow_test.add_node();
2.33 + node_iterator v4=flow_test.add_node();
2.34 + node_iterator v5=flow_test.add_node();
2.35 + node_iterator t=flow_test.add_node();
2.36 +
2.37 + node_property_vector<list_graph, std::string> node_name(flow_test);
2.38 + node_name.put(s, "s");
2.39 + node_name.put(v2, "v2");
2.40 + node_name.put(v3, "v3");
2.41 + node_name.put(v4, "v4");
2.42 + node_name.put(v5, "v5");
2.43 + node_name.put(t, "t");
2.44 +
2.45 +
2.46 + edge_iterator s_v2=flow_test.add_edge(s, v2);
2.47 + edge_iterator s_v3=flow_test.add_edge(s, v3);
2.48 +
2.49 + edge_iterator v2_v4=flow_test.add_edge(v2, v4);
2.50 + edge_iterator v2_v5=flow_test.add_edge(v2, v5);
2.51 +
2.52 + edge_iterator v3_v5=flow_test.add_edge(v3, v5);
2.53 +
2.54 + edge_iterator v4_t=flow_test.add_edge(v4, t);
2.55 + edge_iterator v5_t=flow_test.add_edge(v5, t);
2.56 +
2.57 + //Kis modositas
2.58 + edge_iterator v2_s=flow_test.add_edge(v2, s);
2.59 +
2.60 + edge_property_vector<list_graph, int> cap(flow_test);
2.61 + cap.put(s_v2, 10);
2.62 + cap.put(s_v3, 10);
2.63 + cap.put(v2_v4, 5);
2.64 + cap.put(v2_v5, 8);
2.65 + cap.put(v3_v5, 5);
2.66 + cap.put(v4_t, 8);
2.67 + cap.put(v5_t, 8);
2.68 +
2.69 + //Kis modositas
2.70 + cap.put(v2_s, 100);
2.71 +
2.72 + //Kis modositas
2.73 + //edge_iterator t_s=flow_test.add_edge(t, s);
2.74 + //cap.put(t_s, 20);
2.75 +
2.76 +
2.77 + /*
2.78 + //Marci példája
2.79 + node_iterator s=flow_test.add_node();
2.80 + node_iterator v1=flow_test.add_node();
2.81 + node_iterator v2=flow_test.add_node();
2.82 + node_iterator v3=flow_test.add_node();
2.83 + node_iterator v4=flow_test.add_node();
2.84 + node_iterator t=flow_test.add_node();
2.85 +
2.86 + node_property_vector<list_graph, std::string> node_name(flow_test);
2.87 + node_name.put(s, "s");
2.88 + node_name.put(v1, "v1");
2.89 + node_name.put(v2, "v2");
2.90 + node_name.put(v3, "v3");
2.91 + node_name.put(v4, "v4");
2.92 + node_name.put(t, "t");
2.93 +
2.94 + edge_iterator s_v1=flow_test.add_edge(s, v1);
2.95 + edge_iterator s_v2=flow_test.add_edge(s, v2);
2.96 + edge_iterator v1_v2=flow_test.add_edge(v1, v2);
2.97 + edge_iterator v2_v1=flow_test.add_edge(v2, v1);
2.98 + edge_iterator v1_v3=flow_test.add_edge(v1, v3);
2.99 + edge_iterator v3_v2=flow_test.add_edge(v3, v2);
2.100 + edge_iterator v2_v4=flow_test.add_edge(v2, v4);
2.101 + edge_iterator v4_v3=flow_test.add_edge(v4, v3);
2.102 + edge_iterator v3_t=flow_test.add_edge(v3, t);
2.103 + edge_iterator v4_t=flow_test.add_edge(v4, t);
2.104 +
2.105 + edge_property_vector<list_graph, int> cap(flow_test);
2.106 + cap.put(s_v1, 16);
2.107 + cap.put(s_v2, 13);
2.108 + cap.put(v1_v2, 10);
2.109 + cap.put(v2_v1, 4);
2.110 + cap.put(v1_v3, 12);
2.111 + cap.put(v3_v2, 9);
2.112 + cap.put(v2_v4, 14);
2.113 + cap.put(v4_v3, 7);
2.114 + cap.put(v3_t, 20);
2.115 + cap.put(v4_t, 4);
2.116 + */
2.117 + /*Egyszerű példa
2.118 + node_iterator s=flow_test.add_node();
2.119 + node_iterator v1=flow_test.add_node();
2.120 + node_iterator v2=flow_test.add_node();
2.121 + node_iterator t=flow_test.add_node();
2.122 +
2.123 + node_property_vector<list_graph, std::string> node_name(flow_test);
2.124 + node_name.put(s, "s");
2.125 + node_name.put(v1, "v1");
2.126 + node_name.put(v2, "v2");
2.127 + node_name.put(t, "t");
2.128 +
2.129 + edge_iterator s_v1=flow_test.add_edge(s, v1);
2.130 + edge_iterator v1_v2=flow_test.add_edge(v1, v2);
2.131 + edge_iterator v2_t=flow_test.add_edge(v2, t);
2.132 +
2.133 + edge_property_vector<list_graph, int> cap(flow_test);
2.134 +
2.135 + cap.put(s_v1, 16);
2.136 + cap.put(v1_v2, 10);
2.137 + cap.put(v2_t, 4);
2.138 + */
2.139 +
2.140 + std::cout << "preflow-push algorithm test..." << std::endl;
2.141 + std::cout << "on directed graph graph" << std::endl; //<< flow_test;
2.142 + std::cout << "names and capacity values" << std::endl;
2.143 + for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
2.144 + std::cout << node_name.get(i) << ": ";
2.145 + std::cout << "out edges: ";
2.146 + for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
2.147 + std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
2.148 + std::cout << "in edges: ";
2.149 + for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)
2.150 + std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
2.151 + std::cout << std::endl;
2.152 + }
2.153 +
2.154 +
2.155 + //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
2.156 + // std::cout << i << " ";
2.157 + //}
2.158 +
2.159 + preflow_push<list_graph, int> preflow_push_test(flow_test, s, t, cap);
2.160 + cout << preflow_push_test.run()<<endl;
2.161 +
2.162 + //cap.put(v5_t, 9);
2.163 + //cout << preflow_push_test.run()<<endl;
2.164 +
2.165 + return 0;
2.166 +}
2.167 +
2.168 +
2.169 +
2.170 +
2.171 +
2.172 +
2.173 +
2.174 +
2.175 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/athos/preflow_push.hh Tue Jan 27 16:23:51 2004 +0000
3.3 @@ -0,0 +1,411 @@
3.4 +#ifndef PREFLOW_PUSH_HH
3.5 +#define PREFLOW_PUSH_HH
3.6 +
3.7 +#include <algorithm>
3.8 +#include <list>
3.9 +#include <vector>
3.10 +//#include "pf_hiba.hh"
3.11 +//#include <marci_list_graph.hh>
3.12 +#include <marci_graph_traits.hh>
3.13 +#include "reverse_bfs.hh"
3.14 +
3.15 +using namespace std;
3.16 +
3.17 +namespace marci {
3.18 +
3.19 + template <typename graph_type, typename T>
3.20 + class preflow_push {
3.21 +
3.22 + //Hasznos typedef-ek
3.23 + typedef graph_traits<graph_type>::node_iterator node_iterator;
3.24 + typedef graph_traits<graph_type>::edge_iterator edge_iterator;
3.25 + typedef graph_traits<graph_type>::each_node_iterator each_node_iterator;
3.26 + typedef graph_traits<graph_type>::each_edge_iterator each_edge_iterator;
3.27 + typedef graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
3.28 + typedef graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
3.29 + typedef graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
3.30 +
3.31 + //---------------------------------------------
3.32 + //Parameters of the algorithm
3.33 + //---------------------------------------------
3.34 + //Fully examine an active node until excess becomes 0
3.35 + enum node_examination_t {examine_full, examine_to_relabel};
3.36 + //No more implemented yet:, examine_only_one_edge};
3.37 + node_examination_t node_examination;
3.38 + //Which implementation to be used
3.39 + enum implementation_t {impl_fifo, impl_highest_label};
3.40 + //No more implemented yet:};
3.41 + implementation_t implementation;
3.42 + //---------------------------------------------
3.43 + //Parameters of the algorithm
3.44 + //---------------------------------------------
3.45 +
3.46 + private:
3.47 + //input
3.48 + graph_type& G;
3.49 + node_iterator s;
3.50 + node_iterator t;
3.51 + edge_property_vector<graph_type, T> &capacity;
3.52 + //output
3.53 + edge_property_vector<graph_type, T> preflow;
3.54 + T maxflow_value;
3.55 +
3.56 + //auxiliary variables for computation
3.57 + int number_of_nodes;
3.58 + node_property_vector<graph_type, int> level;
3.59 + node_property_vector<graph_type, T> excess;
3.60 +
3.61 + //Number of nodes on each level
3.62 + vector<int> num_of_nodes_on_level;
3.63 +
3.64 + //For the FIFO implementation
3.65 + list<node_iterator> fifo_nodes;
3.66 + //For 'highest label' implementation
3.67 + int highest_active;
3.68 + //int second_highest_active;
3.69 + vector< list<node_iterator> > active_nodes;
3.70 +
3.71 + public:
3.72 +
3.73 + //Constructing the object using the graph, source, sink and capacity vector
3.74 + preflow_push(
3.75 + graph_type& _G,
3.76 + node_iterator _s,
3.77 + node_iterator _t,
3.78 + edge_property_vector<graph_type, T>& _capacity)
3.79 + : G(_G), s(_s), t(_t),
3.80 + capacity(_capacity),
3.81 + preflow(_G),
3.82 + //Counting the number of nodes
3.83 + number_of_nodes(number_of(G.first_node())),
3.84 + level(_G),
3.85 + excess(_G)//,
3.86 + // Default constructor: active_nodes()
3.87 + {
3.88 + //Simplest parameter settings
3.89 + node_examination = examine_full;//examine_to_relabel;//
3.90 + //Which implementation to be usedexamine_full
3.91 + implementation = impl_highest_label;//impl_fifo;
3.92 +
3.93 + //
3.94 + num_of_nodes_on_level.resize(2*number_of_nodes-1);
3.95 + num_of_nodes_on_level.clear();
3.96 +
3.97 + switch(implementation){
3.98 + case impl_highest_label :{
3.99 + active_nodes.resize(2*number_of_nodes-1);
3.100 + active_nodes.clear();
3.101 + break;
3.102 + }
3.103 + default:
3.104 + break;
3.105 + }
3.106 +
3.107 + }
3.108 +
3.109 + //Returns the value of a maximal flow
3.110 + T run();
3.111 +
3.112 + edge_property_vector<graph_type, T> getmaxflow(){
3.113 + return preflow;
3.114 + }
3.115 +
3.116 +
3.117 + private:
3.118 + //For testing purposes only
3.119 + //Lists the node_properties
3.120 + void write_property_vector(node_property_vector<graph_type, T> a,
3.121 + char* prop_name="property"){
3.122 + for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
3.123 + cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl;
3.124 + }
3.125 + cout<<endl;
3.126 + }
3.127 +
3.128 + //Modifies the excess of the node and makes sufficient changes
3.129 + void modify_excess(const node_iterator& a ,T v){
3.130 + T old_value=excess.get(a);
3.131 + excess.put(a,old_value+v);
3.132 + }
3.133 +
3.134 + //This private procedure is supposed to modify the preflow on edge j
3.135 + //by value v (which can be positive or negative as well)
3.136 + //and maintain the excess on the head and tail
3.137 + //Here we do not check whether this is possible or not
3.138 + void modify_preflow(edge_iterator j, const T& v){
3.139 +
3.140 + //Auxiliary variable
3.141 + T old_value;
3.142 +
3.143 + //Modifiyng the edge
3.144 + old_value=preflow.get(j);
3.145 + preflow.put(j,old_value+v);
3.146 +
3.147 +
3.148 + //Modifiyng the head
3.149 + modify_excess(G.head(j),v);
3.150 +
3.151 + //Modifiyng the tail
3.152 + modify_excess(G.tail(j),-v);
3.153 +
3.154 + }
3.155 +
3.156 + //Gives the active node to work with
3.157 + //(depending on the implementation to be used)
3.158 + node_iterator get_active_node(){
3.159 + //cout<<highest_active<<endl;
3.160 +
3.161 + switch(implementation) {
3.162 + case impl_highest_label : {
3.163 +
3.164 + //First need to find the highest label for which there"s an active node
3.165 + while( highest_active>=0 && active_nodes[highest_active].empty() ){
3.166 + --highest_active;
3.167 + }
3.168 +
3.169 + if( highest_active>=0) {
3.170 + node_iterator a=active_nodes[highest_active].front();
3.171 + active_nodes[highest_active].pop_front();
3.172 + return a;
3.173 + }
3.174 + else {
3.175 + return node_iterator();
3.176 + }
3.177 +
3.178 + break;
3.179 +
3.180 + }
3.181 + case impl_fifo : {
3.182 +
3.183 + if( ! fifo_nodes.empty() ) {
3.184 + node_iterator a=fifo_nodes.front();
3.185 + fifo_nodes.pop_front();
3.186 + return a;
3.187 + }
3.188 + else {
3.189 + return node_iterator();
3.190 + }
3.191 + break;
3.192 + }
3.193 + }
3.194 + //
3.195 + return node_iterator();
3.196 + }
3.197 +
3.198 + //Puts node 'a' among the active nodes
3.199 + void make_active(const node_iterator& a){
3.200 + //s and t never become active
3.201 + if (a!=s && a!= t){
3.202 + switch(implementation){
3.203 + case impl_highest_label :
3.204 + active_nodes[level.get(a)].push_back(a);
3.205 + break;
3.206 + case impl_fifo :
3.207 + fifo_nodes.push_back(a);
3.208 + break;
3.209 + }
3.210 +
3.211 + }
3.212 +
3.213 + //Update highest_active label
3.214 + if (highest_active<level.get(a)){
3.215 + highest_active=level.get(a);
3.216 + }
3.217 +
3.218 + }
3.219 +
3.220 + //Changes the level of node a and make sufficent changes
3.221 + void change_level_to(node_iterator a, int new_value){
3.222 + int seged = level.get(a);
3.223 + level.put(a,new_value);
3.224 + --num_of_nodes_on_level[seged];
3.225 + ++num_of_nodes_on_level[new_value];
3.226 + }
3.227 +
3.228 + //Collection of things useful (or necessary) to do before running
3.229 + void preprocess(){
3.230 +
3.231 + //---------------------------------------
3.232 + //Initialize parameters
3.233 + //---------------------------------------
3.234 +
3.235 + //Setting starting preflow, level and excess values to zero
3.236 + //This can be important, if the algorithm is run more then once
3.237 + for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
3.238 + level.put(i,0);
3.239 + excess.put(i,0);
3.240 + for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j)
3.241 + preflow.put(j, 0);
3.242 + }
3.243 + num_of_nodes_on_level[0]=number_of_nodes;
3.244 + highest_active=0;
3.245 + //---------------------------------------
3.246 + //Initialize parameters
3.247 + //---------------------------------------
3.248 +
3.249 +
3.250 + //------------------------------------
3.251 + //This is the only part that uses BFS
3.252 + //------------------------------------
3.253 + //Setting starting level values using reverse bfs
3.254 + reverse_bfs<graph_type> rev_bfs(G,t);
3.255 + rev_bfs.run();
3.256 + //write_property_vector(rev_bfs.dist,"rev_bfs");
3.257 + for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
3.258 + change_level_to(i,rev_bfs.dist(i));
3.259 + //level.put(i,rev_bfs.dist.get(i));
3.260 + }
3.261 + //------------------------------------
3.262 + //This is the only part that uses BFS
3.263 + //------------------------------------
3.264 +
3.265 +
3.266 + //Starting level of s
3.267 + change_level_to(s,number_of_nodes);
3.268 + //level.put(s,number_of_nodes);
3.269 +
3.270 +
3.271 + //we push as much preflow from s as possible to start with
3.272 + for(out_edge_iterator j=G.first_out_edge(s); j.valid(); ++j){
3.273 + modify_preflow(j,capacity.get(j) );
3.274 + make_active(G.head(j));
3.275 + int lev=level.get(G.head(j));
3.276 + if(highest_active<lev){
3.277 + highest_active=lev;
3.278 + }
3.279 + }
3.280 + //cout<<highest_active<<endl;
3.281 + }
3.282 +
3.283 +
3.284 + //If the preflow is less than the capacity on the given edge
3.285 + //then it is an edge in the residual graph
3.286 + bool is_admissible_forward_edge(out_edge_iterator j, int& new_level){
3.287 + if (capacity.get(j)>preflow.get(j)){
3.288 + if(level.get(G.tail(j))==level.get(G.head(j))+1){
3.289 + return true;
3.290 + }
3.291 + else{
3.292 + if (level.get(G.head(j)) < new_level)
3.293 + new_level=level.get(G.head(j));
3.294 + }
3.295 + }
3.296 + return false;
3.297 + }
3.298 +
3.299 + //If the preflow is greater than 0 on the given edge
3.300 + //then the edge reversd is an edge in the residual graph
3.301 + bool is_admissible_backward_edge(in_edge_iterator j, int& new_level){
3.302 + if (0<preflow.get(j)){
3.303 + if(level.get(G.tail(j))==level.get(G.head(j))-1){
3.304 + return true;
3.305 + }
3.306 + else{
3.307 + if (level.get(G.tail(j)) < new_level)
3.308 + new_level=level.get(G.tail(j));
3.309 + }
3.310 +
3.311 + }
3.312 + return false;
3.313 + }
3.314 +
3.315 +
3.316 + }; //class preflow_push
3.317 +
3.318 + template<typename graph_type, typename T>
3.319 + T preflow_push<graph_type, T>::run() {
3.320 +
3.321 + preprocess();
3.322 +
3.323 + T e,v;
3.324 + node_iterator a;
3.325 + while (a=get_active_node(), a.valid()){
3.326 + //cout<<G.id(a)<<endl;
3.327 + //write_property_vector(excess,"excess");
3.328 + //write_property_vector(level,"level");
3.329 +
3.330 + //Initial value for the new level for the active node we are dealing with
3.331 + int new_level=2*number_of_nodes;
3.332 +
3.333 + bool go_to_next_node=false;
3.334 + e = excess.get(a);
3.335 + while (!go_to_next_node){
3.336 +
3.337 + //Out edges from node a
3.338 + {
3.339 + out_edge_iterator j=G.first_out_edge(a);
3.340 + while (j.valid() && e){
3.341 +
3.342 + if (is_admissible_forward_edge(j,new_level)){
3.343 + v=min(e,capacity.get(j) - preflow.get(j));
3.344 + e -= v;
3.345 + //New node might become active
3.346 + if (excess.get(G.head(j))==0){
3.347 + make_active(G.head(j));
3.348 + }
3.349 + modify_preflow(j,v);
3.350 + }
3.351 + ++j;
3.352 + }
3.353 + }
3.354 + //In edges to node a
3.355 + {
3.356 + in_edge_iterator j=G.first_in_edge(a);
3.357 + while (j.valid() && e){
3.358 + if (is_admissible_backward_edge(j,new_level)){
3.359 + v=min(e,preflow.get(j));
3.360 + e -= v;
3.361 + //New node might become active
3.362 + if (excess.get(G.tail(j))==0){
3.363 + make_active(G.tail(j));
3.364 + }
3.365 + modify_preflow(j,-v);
3.366 + }
3.367 + ++j;
3.368 + }
3.369 + }
3.370 +
3.371 + //cout<<G.id(a)<<" "<<new_level<<endl;
3.372 +
3.373 + if (0==e){
3.374 + //Saturating push
3.375 + go_to_next_node=true;
3.376 + }
3.377 + else{//If there is still excess in node a
3.378 +
3.379 + //Level remains empty
3.380 + if (num_of_nodes_on_level[level.get(a)]==1){
3.381 + change_level_to(a,number_of_nodes);
3.382 + //go_to_next_node=True;
3.383 + }
3.384 + else{
3.385 + change_level_to(a,new_level+1);
3.386 + //increase_level(a);
3.387 + }
3.388 +
3.389 +
3.390 +
3.391 +
3.392 + switch(node_examination){
3.393 + case examine_to_relabel:
3.394 + make_active(a);
3.395 +
3.396 + go_to_next_node = true;
3.397 + break;
3.398 + default:
3.399 + break;
3.400 + }
3.401 +
3.402 +
3.403 +
3.404 + }//if (0==e)
3.405 + }
3.406 + }
3.407 + maxflow_value = excess.get(t);
3.408 + return maxflow_value;
3.409 + }//run
3.410 +
3.411 +
3.412 +}//namespace marci
3.413 +
3.414 +#endif //PREFLOW_PUSH_HH