Elkezdtem atirni a preflow_push-t. Csinaltam egy backupot graph wrapper nelkul (without gw, azaz wogw)
1.1 --- a/src/work/athos/makefile Thu Apr 15 14:41:20 2004 +0000
1.2 +++ b/src/work/athos/makefile Thu Apr 15 17:03:44 2004 +0000
1.3 @@ -6,7 +6,7 @@
1.4 #BOOSTROOT ?= /home/marci/boost
1.5 INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,athos,akos,klao} #-I$(BOOSTROOT)
1.6 #LEDAINCLUDE ?= -I$(LEDAROOT)/incl
1.7 -CXXFLAGS = -g -W -Wall $(INCLUDEDIRS) -ansi -pedantic
1.8 +CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic
1.9
1.10 #LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
1.11 BINARIES = suurballe
2.1 --- a/src/work/athos/pf_demo.cc Thu Apr 15 14:41:20 2004 +0000
2.2 +++ b/src/work/athos/pf_demo.cc Thu Apr 15 17:03:44 2004 +0000
2.3 @@ -2,8 +2,8 @@
2.4 #include <vector>
2.5 #include <string>
2.6
2.7 -#include "list_graph.hh"
2.8 -#include "marci_graph_traits.hh"
2.9 +#include "list_graph.h"
2.10 +//#include "marci_graph_traits.hh"
2.11 //#include "marci_property_vector.hh"
2.12 #include "preflow_push.hh"
2.13
2.14 @@ -13,137 +13,88 @@
2.15 int main (int, char*[])
2.16 {
2.17
2.18 -
2.19 - typedef ListGraph::NodeIt NodeIt;
2.20 - typedef ListGraph::EdgeIt EdgeIt;
2.21 - /*
2.22 - typedef ListGraph::EachNodeIt EachNodeIt;
2.23 - typedef ListGraph::EachEdgeIt EachEdgeIt;
2.24 - typedef ListGraph::OutEdgeIt OutEdgeIt;
2.25 - typedef ListGraph::InEdgeIt InEdgeIt;
2.26 - typedef ListGraph::SymEdgeIt SymEdgeIt;
2.27 - */
2.28 - ListGraph flowG;
2.29 + typedef ListGraph::Node Node;
2.30 + typedef ListGraph::Edge Edge;
2.31 +
2.32 + ListGraph graph;
2.33
2.34 /*
2.35 //Marci példája
2.36
2.37
2.38 - NodeIt s=flowG.addNode();
2.39 - NodeIt v1=flowG.addNode();
2.40 - NodeIt v2=flowG.addNode();
2.41 - NodeIt v3=flowG.addNode();
2.42 - NodeIt v4=flowG.addNode();
2.43 - NodeIt t=flowG.addNode();
2.44 + NodeIt s=graph.addNode();
2.45 + NodeIt v1=graph.addNode();
2.46 + NodeIt v2=graph.addNode();
2.47 + NodeIt v3=graph.addNode();
2.48 + NodeIt v4=graph.addNode();
2.49 + NodeIt t=graph.addNode();
2.50
2.51
2.52 - EdgeIt s_v1=flowG.addEdge(s, v1);
2.53 - EdgeIt s_v2=flowG.addEdge(s, v2);
2.54 - EdgeIt v1_v2=flowG.addEdge(v1, v2);
2.55 - EdgeIt v2_v1=flowG.addEdge(v2, v1);
2.56 - EdgeIt v1_v3=flowG.addEdge(v1, v3);
2.57 - EdgeIt v3_v2=flowG.addEdge(v3, v2);
2.58 - EdgeIt v2_v4=flowG.addEdge(v2, v4);
2.59 - EdgeIt v4_v3=flowG.addEdge(v4, v3);
2.60 - EdgeIt v3_t=flowG.addEdge(v3, t);
2.61 - EdgeIt v4_t=flowG.addEdge(v4, t);
2.62 + EdgeIt s_v1=graph.addEdge(s, v1);
2.63 + EdgeIt s_v2=graph.addEdge(s, v2);
2.64 + EdgeIt v1_v2=graph.addEdge(v1, v2);
2.65 + EdgeIt v2_v1=graph.addEdge(v2, v1);
2.66 + EdgeIt v1_v3=graph.addEdge(v1, v3);
2.67 + EdgeIt v3_v2=graph.addEdge(v3, v2);
2.68 + EdgeIt v2_v4=graph.addEdge(v2, v4);
2.69 + EdgeIt v4_v3=graph.addEdge(v4, v3);
2.70 + EdgeIt v3_t=graph.addEdge(v3, t);
2.71 + EdgeIt v4_t=graph.addEdge(v4, t);
2.72
2.73 - ListGraph::EdgeMap<int> cap(flowG);
2.74 + ListGraph::EdgeMap<int> length(graph);
2.75
2.76 - cap.set(s_v1, 16);
2.77 - cap.set(s_v2, 13);
2.78 - cap.set(v1_v2, 10);
2.79 - cap.set(v2_v1, 4);
2.80 - cap.set(v1_v3, 12);
2.81 - cap.set(v3_v2, 9);
2.82 - cap.set(v2_v4, 14);
2.83 - cap.set(v4_v3, 7);
2.84 - cap.set(v3_t, 20);
2.85 - cap.set(v4_t, 4);
2.86 + length.set(s_v1, 16);
2.87 + length.set(s_v2, 13);
2.88 + length.set(v1_v2, 10);
2.89 + length.set(v2_v1, 4);
2.90 + length.set(v1_v3, 12);
2.91 + length.set(v3_v2, 9);
2.92 + length.set(v2_v4, 14);
2.93 + length.set(v4_v3, 7);
2.94 + length.set(v3_t, 20);
2.95 + length.set(v4_t, 4);
2.96 */
2.97
2.98
2.99 //Ahuja könyv példája
2.100
2.101 - NodeIt s=flowG.addNode();
2.102 - NodeIt v2=flowG.addNode();
2.103 - NodeIt v3=flowG.addNode();
2.104 - NodeIt v4=flowG.addNode();
2.105 - NodeIt v5=flowG.addNode();
2.106 - NodeIt t=flowG.addNode();
2.107 + Node s=graph.addNode();
2.108 + Node v2=graph.addNode();
2.109 + Node v3=graph.addNode();
2.110 + Node v4=graph.addNode();
2.111 + Node v5=graph.addNode();
2.112 + Node t=graph.addNode();
2.113
2.114 - EdgeIt s_v2=flowG.addEdge(s, v2);
2.115 - EdgeIt s_v3=flowG.addEdge(s, v3);
2.116 - EdgeIt v2_v4=flowG.addEdge(v2, v4);
2.117 - EdgeIt v2_v5=flowG.addEdge(v2, v5);
2.118 - EdgeIt v3_v5=flowG.addEdge(v3, v5);
2.119 - EdgeIt v4_t=flowG.addEdge(v4, t);
2.120 - EdgeIt v5_t=flowG.addEdge(v5, t);
2.121 + Edge s_v2=graph.addEdge(s, v2);
2.122 + Edge s_v3=graph.addEdge(s, v3);
2.123 + Edge v2_v4=graph.addEdge(v2, v4);
2.124 + Edge v2_v5=graph.addEdge(v2, v5);
2.125 + Edge v3_v5=graph.addEdge(v3, v5);
2.126 + Edge v4_t=graph.addEdge(v4, t);
2.127 + Edge v5_t=graph.addEdge(v5, t);
2.128
2.129 //Kis modositas
2.130 - //edge_iterator v2_s=flowG.add_edge(v2, s);
2.131 + //edge_iterator v2_s=graph.add_edge(v2, s);
2.132
2.133 - ListGraph::EdgeMap<int> cap(flowG);
2.134 + ListGraph::EdgeMap<int> length(graph);
2.135
2.136 - cap.set(s_v2, 10);
2.137 - cap.set(s_v3, 10);
2.138 - cap.set(v2_v4, 5);
2.139 - cap.set(v2_v5, 8);
2.140 - cap.set(v3_v5, 5);
2.141 - cap.set(v4_t, 8);
2.142 - cap.set(v5_t, 8);
2.143 + length.set(s_v2, 10);
2.144 + length.set(s_v3, 10);
2.145 + length.set(v2_v4, 5);
2.146 + length.set(v2_v5, 8);
2.147 + length.set(v3_v5, 5);
2.148 + length.set(v4_t, 8);
2.149 + length.set(v5_t, 8);
2.150
2.151 //Kis modositas
2.152 - //cap.put(v2_s, 100);
2.153 -
2.154 + //length.put(v2_s, 100);
2.155
2.156
2.157
2.158 - /*Egyszerű példa
2.159 - NodeIt s=flow_test.add_node();
2.160 - NodeIt v1=flow_test.add_node();
2.161 - NodeIt v2=flow_test.add_node();
2.162 - NodeIt t=flow_test.add_node();
2.163 -
2.164 - node_property_vector<list_graph, std::string> node_name(flow_test);
2.165 - node_name.put(s, "s");
2.166 - node_name.put(v1, "v1");
2.167 - node_name.put(v2, "v2");
2.168 - node_name.put(t, "t");
2.169 -
2.170 - edge_iterator s_v1=flow_test.add_edge(s, v1);
2.171 - edge_iterator v1_v2=flow_test.add_edge(v1, v2);
2.172 - edge_iterator v2_t=flow_test.add_edge(v2, t);
2.173 -
2.174 - edge_property_vector<list_graph, int> cap(flow_test);
2.175 -
2.176 - cap.put(s_v1, 16);
2.177 - cap.put(v1_v2, 10);
2.178 - cap.put(v2_t, 4);
2.179 - */
2.180 -
2.181 std::cout << "preflow-push algorithm test..." << std::endl;
2.182
2.183 - /*
2.184 - std::cout << "on directed graph graph" << std::endl; //<< flow_test;
2.185 - std::cout << "names and capacity values" << std::endl;
2.186 - for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) {
2.187 - std::cout << node_name.get(i) << ": ";
2.188 - std::cout << "out edges: ";
2.189 - for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
2.190 - std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
2.191 - std::cout << "in edges: ";
2.192 - for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)
2.193 - std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
2.194 - std::cout << std::endl;
2.195 - }
2.196 - */
2.197
2.198 - //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) {
2.199 - // std::cout << i << " ";
2.200 - //}
2.201 -
2.202 - preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap);
2.203 + preflow_push<ListGraph, int> preflow_push_test(graph, s, t, length);
2.204 cout << preflow_push_test.run()<<endl;
2.205
2.206 //cap.put(v5_t, 9);
2.207 @@ -151,12 +102,3 @@
2.208
2.209 return 0;
2.210 }
2.211 -
2.212 -
2.213 -
2.214 -
2.215 -
2.216 -
2.217 -
2.218 -
2.219 -
3.1 --- a/src/work/athos/preflow_push.hh Thu Apr 15 14:41:20 2004 +0000
3.2 +++ b/src/work/athos/preflow_push.hh Thu Apr 15 17:03:44 2004 +0000
3.3 @@ -1,43 +1,32 @@
3.4 -#ifndef PREFLOW_PUSH_HH
3.5 -#define PREFLOW_PUSH_HH
3.6 +#ifndef HUGO_PREFLOW_PUSH_HH
3.7 +#define HUGO_PREFLOW_PUSH_HH
3.8
3.9 -#include <algorithm>
3.10 +//#include <algorithm>
3.11 #include <list>
3.12 #include <vector>
3.13 +#include <queue>
3.14 //#include "pf_hiba.hh"
3.15 //#include <marci_list_graph.hh>
3.16 //#include <marci_graph_traits.hh>
3.17 -
3.18 -#include <reverse_bfs.hh>
3.19 +#include <invalid.h>
3.20 +#include <graph_wrapper.h>
3.21 +//#include <reverse_bfs.hh>
3.22
3.23 using namespace std;
3.24
3.25 namespace hugo {
3.26
3.27 - template <typename graph_type, typename T>
3.28 + template <typename Graph, typename T>
3.29 class preflow_push {
3.30
3.31 - //Hasznos typedef-ek
3.32 - typedef typename graph_type::NodeIt NodeIt;
3.33 - typedef typename graph_type::EdgeIt EdgeIt;
3.34 - typedef typename graph_type::EachNodeIt EachNodeIt;
3.35 - typedef typename graph_type::EachEdgeIt EachEdgeIt;
3.36 - typedef typename graph_type::OutEdgeIt OutEdgeIt;
3.37 - typedef typename graph_type::InEdgeIt InEdgeIt;
3.38 - typedef typename graph_type::SymEdgeIt SymEdgeIt;
3.39 + //Useful typedefs
3.40 + typedef typename Graph::Node Node;
3.41 + typedef typename Graph::NodeIt NodeIt;
3.42 + typedef typename Graph::Edge Edge;
3.43 + typedef typename Graph::OutEdgeIt OutEdgeIt;
3.44 + typedef typename Graph::InEdgeIt InEdgeIt;
3.45
3.46
3.47 -
3.48 - /*
3.49 - typedef graph_traits<graph_type>::node_iterator node_iterator;
3.50 - typedef graph_traits<graph_type>::EdgeIt EdgeIt;
3.51 - typedef graph_traits<graph_type>::each_node_iterator each_node_iterator;
3.52 - typedef graph_traits<graph_type>::each_EdgeIt each_EdgeIt;
3.53 - typedef graph_traits<graph_type>::out_EdgeIt out_EdgeIt;
3.54 - typedef graph_traits<graph_type>::InEdgeIt InEdgeIt;
3.55 - typedef graph_traits<graph_type>::sym_EdgeIt sym_EdgeIt;
3.56 - */
3.57 -
3.58 //---------------------------------------------
3.59 //Parameters of the algorithm
3.60 //---------------------------------------------
3.61 @@ -55,43 +44,41 @@
3.62
3.63 private:
3.64 //input
3.65 - graph_type& G;
3.66 - NodeIt s;
3.67 - NodeIt t;
3.68 - typename graph_type::EdgeMap<T> &capacity;
3.69 - //typename graph_type::EdgeMap<T> &capacity;
3.70 + Graph& G;
3.71 + Node s;
3.72 + Node t;
3.73 + typename Graph::EdgeMap<T> &capacity;
3.74 +
3.75 //output
3.76 - //typename graph_type::EdgeMap<T>
3.77 - typename graph_type::EdgeMap<T> preflow;
3.78 + typename Graph::EdgeMap<T> preflow;
3.79 T maxflow_value;
3.80
3.81 //auxiliary variables for computation
3.82 + //The number of the nodes
3.83 int number_of_nodes;
3.84 -
3.85 -
3.86 - typename graph_type::NodeMap<int> level;
3.87 - typename graph_type::NodeMap<T> excess;
3.88 - //node_property_vector<graph_type, int> level;
3.89 - //node_property_vector<graph_type, T> excess;
3.90 + //A nodemap for the level
3.91 + typename Graph::NodeMap<int> level;
3.92 + //A nodemap for the excess
3.93 + typename Graph::NodeMap<T> excess;
3.94
3.95 //Number of nodes on each level
3.96 vector<int> num_of_nodes_on_level;
3.97
3.98 //For the FIFO implementation
3.99 - list<NodeIt> fifo_nodes;
3.100 + list<Node> fifo_nodes;
3.101 //For 'highest label' implementation
3.102 int highest_active;
3.103 //int second_highest_active;
3.104 - vector< list<NodeIt> > active_nodes;
3.105 + vector< list<Node> > active_nodes;
3.106
3.107 public:
3.108
3.109 //Constructing the object using the graph, source, sink and capacity vector
3.110 preflow_push(
3.111 - graph_type& _G,
3.112 - NodeIt _s,
3.113 - NodeIt _t,
3.114 - typename graph_type::EdgeMap<T> & _capacity)
3.115 + Graph& _G,
3.116 + Node _s,
3.117 + Node _t,
3.118 + typename Graph::EdgeMap<T> & _capacity)
3.119 : G(_G), s(_s), t(_t),
3.120 capacity(_capacity),
3.121 preflow(_G),
3.122 @@ -114,8 +101,9 @@
3.123
3.124 switch(implementation){
3.125 case impl_highest_label :{
3.126 + active_nodes.clear();
3.127 active_nodes.resize(2*number_of_nodes-1);
3.128 - active_nodes.clear();
3.129 +
3.130 break;
3.131 }
3.132 default:
3.133 @@ -127,7 +115,7 @@
3.134 //Returns the value of a maximal flow
3.135 T run();
3.136
3.137 - typename graph_type::EdgeMap<T> getmaxflow(){
3.138 + typename Graph::EdgeMap<T> getmaxflow(){
3.139 return preflow;
3.140 }
3.141
3.142 @@ -135,33 +123,29 @@
3.143 private:
3.144 //For testing purposes only
3.145 //Lists the node_properties
3.146 - void write_property_vector(typename graph_type::NodeMap<T> a,
3.147 - //node_property_vector<graph_type, T> a,
3.148 + void write_property_vector(typename Graph::NodeMap<T> a,
3.149 + //node_property_vector<Graph, T> a,
3.150 char* prop_name="property"){
3.151 - for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
3.152 - cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl;
3.153 + for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
3.154 + cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl;
3.155 }
3.156 cout<<endl;
3.157 }
3.158
3.159 //Modifies the excess of the node and makes sufficient changes
3.160 - void modify_excess(const NodeIt& a ,T v){
3.161 - T old_value=excess.get(a);
3.162 - excess.set(a,old_value+v);
3.163 + void modify_excess(const Node& a ,T v){
3.164 + //T old_value=excess[a];
3.165 + excess[a] += v;
3.166 }
3.167
3.168 //This private procedure is supposed to modify the preflow on edge j
3.169 //by value v (which can be positive or negative as well)
3.170 //and maintain the excess on the head and tail
3.171 //Here we do not check whether this is possible or not
3.172 - void modify_preflow(EdgeIt j, const T& v){
3.173 + void modify_preflow(Edge j, const T& v){
3.174
3.175 - //Auxiliary variable
3.176 - T old_value;
3.177 -
3.178 //Modifiyng the edge
3.179 - old_value=preflow.get(j);
3.180 - preflow.set(j,old_value+v);
3.181 + preflow[j] += v;
3.182
3.183
3.184 //Modifiyng the head
3.185 @@ -174,13 +158,13 @@
3.186
3.187 //Gives the active node to work with
3.188 //(depending on the implementation to be used)
3.189 - NodeIt get_active_node(){
3.190 + Node get_active_node(){
3.191
3.192
3.193 switch(implementation) {
3.194 case impl_highest_label : {
3.195
3.196 - //First need to find the highest label for which there"s an active node
3.197 + //First need to find the highest label for which there's an active node
3.198 while( highest_active>=0 && active_nodes[highest_active].empty() ){
3.199 --highest_active;
3.200 }
3.201 @@ -188,13 +172,13 @@
3.202 if( highest_active>=0) {
3.203
3.204
3.205 - NodeIt a=active_nodes[highest_active].front();
3.206 + Node a=active_nodes[highest_active].front();
3.207 active_nodes[highest_active].pop_front();
3.208
3.209 return a;
3.210 }
3.211 else {
3.212 - return NodeIt();
3.213 + return INVALID;
3.214 }
3.215
3.216 break;
3.217 @@ -203,27 +187,27 @@
3.218 case impl_fifo : {
3.219
3.220 if( ! fifo_nodes.empty() ) {
3.221 - NodeIt a=fifo_nodes.front();
3.222 + Node a=fifo_nodes.front();
3.223 fifo_nodes.pop_front();
3.224 return a;
3.225 }
3.226 else {
3.227 - return NodeIt();
3.228 + return INVALID;
3.229 }
3.230 break;
3.231 }
3.232 }
3.233 //
3.234 - return NodeIt();
3.235 + return INVALID;
3.236 }
3.237
3.238 //Puts node 'a' among the active nodes
3.239 - void make_active(const NodeIt& a){
3.240 + void make_active(const Node& a){
3.241 //s and t never become active
3.242 if (a!=s && a!= t){
3.243 switch(implementation){
3.244 case impl_highest_label :
3.245 - active_nodes[level.get(a)].push_back(a);
3.246 + active_nodes[level[a]].push_back(a);
3.247 break;
3.248 case impl_fifo :
3.249 fifo_nodes.push_back(a);
3.250 @@ -233,15 +217,15 @@
3.251 }
3.252
3.253 //Update highest_active label
3.254 - if (highest_active<level.get(a)){
3.255 - highest_active=level.get(a);
3.256 + if (highest_active<level[a]){
3.257 + highest_active=level[a];
3.258 }
3.259
3.260 }
3.261
3.262 //Changes the level of node a and make sufficent changes
3.263 - void change_level_to(NodeIt a, int new_value){
3.264 - int seged = level.get(a);
3.265 + void change_level_to(Node a, int new_value){
3.266 + int seged = level[a];
3.267 level.set(a,new_value);
3.268 --num_of_nodes_on_level[seged];
3.269 ++num_of_nodes_on_level[new_value];
3.270 @@ -257,10 +241,10 @@
3.271
3.272 //Setting starting preflow, level and excess values to zero
3.273 //This can be important, if the algorithm is run more then once
3.274 - for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
3.275 + for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
3.276 level.set(i,0);
3.277 excess.set(i,0);
3.278 - for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j)
3.279 + for(OutEdgeIt j=G.template first<OutEdgeIt>(i); G.valid(j); G.next(j))
3.280 preflow.set(j, 0);
3.281 }
3.282 num_of_nodes_on_level[0]=number_of_nodes;
3.283 @@ -273,14 +257,47 @@
3.284 //------------------------------------
3.285 //This is the only part that uses BFS
3.286 //------------------------------------
3.287 +
3.288 + /*Reverse_bfs from t, to find the starting level.*/
3.289 + //Copyright: Jacint
3.290 + change_level_to(t,0);
3.291 +
3.292 + std::queue<Node> bfs_queue;
3.293 + bfs_queue.push(t);
3.294 +
3.295 + while (!bfs_queue.empty()) {
3.296 +
3.297 + Node v=bfs_queue.front();
3.298 + bfs_queue.pop();
3.299 + int l=level[v]+1;
3.300 +
3.301 + InEdgeIt e;
3.302 + for(G.first(e,v); G.valid(e); G.next(e)) {
3.303 + Node w=G.tail(e);
3.304 + if ( level[w] == number_of_nodes && w != s ) {
3.305 + bfs_queue.push(w);
3.306 + //Node first=level_list[l];
3.307 + //if ( G.valid(first) ) left.set(first,w);
3.308 + //right.set(w,first);
3.309 + //level_list[l]=w;
3.310 + change_level_to(w, l);
3.311 + //level.set(w, l);
3.312 + }
3.313 + }
3.314 + }
3.315 + change_level_to(s,number_of_nodes);
3.316 + //level.set(s,number_of_nodes);
3.317 +
3.318 + /*
3.319 //Setting starting level values using reverse bfs
3.320 - reverse_bfs<graph_type> rev_bfs(G,t);
3.321 + reverse_bfs<Graph> rev_bfs(G,t);
3.322 rev_bfs.run();
3.323 //write_property_vector(rev_bfs.dist,"rev_bfs");
3.324 - for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
3.325 + for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
3.326 change_level_to(i,rev_bfs.dist(i));
3.327 //level.put(i,rev_bfs.dist.get(i));
3.328 }
3.329 + */
3.330 //------------------------------------
3.331 //This is the only part that uses BFS
3.332 //------------------------------------
3.333 @@ -292,10 +309,10 @@
3.334
3.335
3.336 //we push as much preflow from s as possible to start with
3.337 - for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){
3.338 - modify_preflow(j,capacity.get(j) );
3.339 + for(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){
3.340 + modify_preflow(j,capacity[j] );
3.341 make_active(G.head(j));
3.342 - int lev=level.get(G.head(j));
3.343 + int lev=level[G.head(j)];
3.344 if(highest_active<lev){
3.345 highest_active=lev;
3.346 }
3.347 @@ -306,15 +323,15 @@
3.348
3.349 //If the preflow is less than the capacity on the given edge
3.350 //then it is an edge in the residual graph
3.351 - bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){
3.352 + bool is_admissible_forward_edge(Edge j, int& new_level){
3.353
3.354 - if (capacity.get(j)>preflow.get(j)){
3.355 - if(level.get(G.tail(j))==level.get(G.head(j))+1){
3.356 + if (capacity[j]>preflow[j]){
3.357 + if(level[G.tail(j)]==level[G.head(j)]+1){
3.358 return true;
3.359 }
3.360 else{
3.361 - if (level.get(G.head(j)) < new_level)
3.362 - new_level=level.get(G.head(j));
3.363 + if (level[G.head(j)] < new_level)
3.364 + new_level=level[G.head(j)];
3.365 }
3.366 }
3.367 return false;
3.368 @@ -322,16 +339,16 @@
3.369
3.370 //If the preflow is greater than 0 on the given edge
3.371 //then the edge reversd is an edge in the residual graph
3.372 - bool is_admissible_backward_edge(InEdgeIt j, int& new_level){
3.373 + bool is_admissible_backward_edge(Edge j, int& new_level){
3.374
3.375 - if (0<preflow.get(j)){
3.376 - if(level.get(G.tail(j))==level.get(G.head(j))-1){
3.377 + if (0<preflow[j]){
3.378 + if(level[G.tail(j)]==level[G.head(j)]-1){
3.379
3.380 return true;
3.381 }
3.382 else{
3.383 - if (level.get(G.tail(j)) < new_level)
3.384 - new_level=level.get(G.tail(j));
3.385 + if (level[G.tail(j)] < new_level)
3.386 + new_level=level[G.tail(j)];
3.387 }
3.388
3.389 }
3.390 @@ -341,59 +358,57 @@
3.391
3.392 }; //class preflow_push
3.393
3.394 - template<typename graph_type, typename T>
3.395 - T preflow_push<graph_type, T>::run() {
3.396 + template<typename Graph, typename T>
3.397 + T preflow_push<Graph, T>::run() {
3.398 +
3.399 + //We need a residual graph
3.400 + ResGraphType res_graph(G, preflow, capacity);
3.401
3.402 preprocess();
3.403 //write_property_vector(level,"level");
3.404 T e,v;
3.405 - NodeIt a;
3.406 - while (a=get_active_node(), a.valid()){
3.407 + Node a;
3.408 + while (a=get_active_node(), G.valid(a)){
3.409
3.410 - //cout<<G.id(a)<<endl;
3.411 - //write_property_vector(excess,"excess");
3.412 - //write_property_vector(level,"level");
3.413 + bool go_to_next_node=false;
3.414 + e = excess[a];
3.415 + while (!go_to_next_node){
3.416
3.417 -
3.418 - bool go_to_next_node=false;
3.419 - e = excess.get(a);
3.420 - while (!go_to_next_node){
3.421 //Initial value for the new level for the active node we are dealing with
3.422 int new_level=2*number_of_nodes;
3.423 - //write_property_vector(excess,"excess");
3.424 - //write_property_vector(level,"level");
3.425 - //cout<<G.id(a)<<endl;
3.426 +
3.427 +
3.428 //Out edges from node a
3.429 {
3.430 OutEdgeIt j=G.template first<OutEdgeIt>(a);
3.431 - while (j.valid() && e){
3.432 + while (G.valid(j) && e){
3.433
3.434 if (is_admissible_forward_edge(j,new_level)){
3.435 - v=min(e,capacity.get(j) - preflow.get(j));
3.436 + v=min(e,capacity[j] - preflow[j]);
3.437 e -= v;
3.438 //New node might become active
3.439 - if (excess.get(G.head(j))==0){
3.440 + if (excess[G.head(j)]==0){
3.441 make_active(G.head(j));
3.442 }
3.443 modify_preflow(j,v);
3.444 }
3.445 - ++j;
3.446 + G.next(j);
3.447 }
3.448 }
3.449 //In edges to node a
3.450 {
3.451 InEdgeIt j=G.template first<InEdgeIt>(a);
3.452 - while (j.valid() && e){
3.453 + while (G.valid(j) && e){
3.454 if (is_admissible_backward_edge(j,new_level)){
3.455 - v=min(e,preflow.get(j));
3.456 + v=min(e,preflow[j]);
3.457 e -= v;
3.458 //New node might become active
3.459 - if (excess.get(G.tail(j))==0){
3.460 + if (excess[G.tail(j)]==0){
3.461 make_active(G.tail(j));
3.462 }
3.463 modify_preflow(j,-v);
3.464 }
3.465 - ++j;
3.466 + G.next(j);
3.467 }
3.468 }
3.469
3.470 @@ -410,7 +425,7 @@
3.471 //change_level_to(a,new_level+1);
3.472
3.473 //Level remains empty
3.474 - if (num_of_nodes_on_level[level.get(a)]==1){
3.475 + if (num_of_nodes_on_level[level[a]]==1){
3.476 change_level_to(a,number_of_nodes);
3.477 //go_to_next_node=True;
3.478 }
3.479 @@ -437,7 +452,7 @@
3.480 }//if (0==e)
3.481 }
3.482 }
3.483 - maxflow_value = excess.get(t);
3.484 + maxflow_value = excess[t];
3.485 return maxflow_value;
3.486 }//run
3.487
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/athos/preflow_push_wogw.h Thu Apr 15 17:03:44 2004 +0000
4.3 @@ -0,0 +1,463 @@
4.4 +#ifndef HUGO_PREFLOW_PUSH_HH
4.5 +#define HUGO_PREFLOW_PUSH_HH
4.6 +
4.7 +//#include <algorithm>
4.8 +#include <list>
4.9 +#include <vector>
4.10 +#include <queue>
4.11 +//#include "pf_hiba.hh"
4.12 +//#include <marci_list_graph.hh>
4.13 +//#include <marci_graph_traits.hh>
4.14 +#include <invalid.h>
4.15 +//#include <reverse_bfs.hh>
4.16 +
4.17 +using namespace std;
4.18 +
4.19 +namespace hugo {
4.20 +
4.21 + template <typename Graph, typename T>
4.22 + class preflow_push {
4.23 +
4.24 + //Useful typedefs
4.25 + typedef typename Graph::Node Node;
4.26 + typedef typename Graph::NodeIt NodeIt;
4.27 + typedef typename Graph::Edge Edge;
4.28 + typedef typename Graph::OutEdgeIt OutEdgeIt;
4.29 + typedef typename Graph::InEdgeIt InEdgeIt;
4.30 +
4.31 +
4.32 + //---------------------------------------------
4.33 + //Parameters of the algorithm
4.34 + //---------------------------------------------
4.35 + //Fully examine an active node until excess becomes 0
4.36 + enum node_examination_t {examine_full, examine_to_relabel};
4.37 + //No more implemented yet:, examine_only_one_edge};
4.38 + node_examination_t node_examination;
4.39 + //Which implementation to be used
4.40 + enum implementation_t {impl_fifo, impl_highest_label};
4.41 + //No more implemented yet:};
4.42 + implementation_t implementation;
4.43 + //---------------------------------------------
4.44 + //Parameters of the algorithm
4.45 + //---------------------------------------------
4.46 +
4.47 + private:
4.48 + //input
4.49 + Graph& G;
4.50 + Node s;
4.51 + Node t;
4.52 + typename Graph::EdgeMap<T> &capacity;
4.53 +
4.54 + //output
4.55 + typename Graph::EdgeMap<T> preflow;
4.56 + T maxflow_value;
4.57 +
4.58 + //auxiliary variables for computation
4.59 + //The number of the nodes
4.60 + int number_of_nodes;
4.61 + //A nodemap for the level
4.62 + typename Graph::NodeMap<int> level;
4.63 + //A nodemap for the excess
4.64 + typename Graph::NodeMap<T> excess;
4.65 +
4.66 + //Number of nodes on each level
4.67 + vector<int> num_of_nodes_on_level;
4.68 +
4.69 + //For the FIFO implementation
4.70 + list<Node> fifo_nodes;
4.71 + //For 'highest label' implementation
4.72 + int highest_active;
4.73 + //int second_highest_active;
4.74 + vector< list<Node> > active_nodes;
4.75 +
4.76 + public:
4.77 +
4.78 + //Constructing the object using the graph, source, sink and capacity vector
4.79 + preflow_push(
4.80 + Graph& _G,
4.81 + Node _s,
4.82 + Node _t,
4.83 + typename Graph::EdgeMap<T> & _capacity)
4.84 + : G(_G), s(_s), t(_t),
4.85 + capacity(_capacity),
4.86 + preflow(_G),
4.87 + //Counting the number of nodes
4.88 + //number_of_nodes(count(G.first<EachNodeIt>())),
4.89 + number_of_nodes(G.nodeNum()),
4.90 +
4.91 + level(_G),
4.92 + excess(_G)//,
4.93 + // Default constructor: active_nodes()
4.94 + {
4.95 + //Simplest parameter settings
4.96 + node_examination = examine_full;//examine_to_relabel;//
4.97 + //Which implementation to be usedexamine_full
4.98 + implementation = impl_highest_label;//impl_fifo;
4.99 +
4.100 + //
4.101 + num_of_nodes_on_level.resize(2*number_of_nodes-1);
4.102 + num_of_nodes_on_level.clear();
4.103 +
4.104 + switch(implementation){
4.105 + case impl_highest_label :{
4.106 + active_nodes.clear();
4.107 + active_nodes.resize(2*number_of_nodes-1);
4.108 +
4.109 + break;
4.110 + }
4.111 + default:
4.112 + break;
4.113 + }
4.114 +
4.115 + }
4.116 +
4.117 + //Returns the value of a maximal flow
4.118 + T run();
4.119 +
4.120 + typename Graph::EdgeMap<T> getmaxflow(){
4.121 + return preflow;
4.122 + }
4.123 +
4.124 +
4.125 + private:
4.126 + //For testing purposes only
4.127 + //Lists the node_properties
4.128 + void write_property_vector(typename Graph::NodeMap<T> a,
4.129 + //node_property_vector<Graph, T> a,
4.130 + char* prop_name="property"){
4.131 + for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
4.132 + cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl;
4.133 + }
4.134 + cout<<endl;
4.135 + }
4.136 +
4.137 + //Modifies the excess of the node and makes sufficient changes
4.138 + void modify_excess(const Node& a ,T v){
4.139 + //T old_value=excess[a];
4.140 + excess[a] += v;
4.141 + }
4.142 +
4.143 + //This private procedure is supposed to modify the preflow on edge j
4.144 + //by value v (which can be positive or negative as well)
4.145 + //and maintain the excess on the head and tail
4.146 + //Here we do not check whether this is possible or not
4.147 + void modify_preflow(Edge j, const T& v){
4.148 +
4.149 + //Modifiyng the edge
4.150 + preflow[j] += v;
4.151 +
4.152 +
4.153 + //Modifiyng the head
4.154 + modify_excess(G.head(j),v);
4.155 +
4.156 + //Modifiyng the tail
4.157 + modify_excess(G.tail(j),-v);
4.158 +
4.159 + }
4.160 +
4.161 + //Gives the active node to work with
4.162 + //(depending on the implementation to be used)
4.163 + Node get_active_node(){
4.164 +
4.165 +
4.166 + switch(implementation) {
4.167 + case impl_highest_label : {
4.168 +
4.169 + //First need to find the highest label for which there's an active node
4.170 + while( highest_active>=0 && active_nodes[highest_active].empty() ){
4.171 + --highest_active;
4.172 + }
4.173 +
4.174 + if( highest_active>=0) {
4.175 +
4.176 +
4.177 + Node a=active_nodes[highest_active].front();
4.178 + active_nodes[highest_active].pop_front();
4.179 +
4.180 + return a;
4.181 + }
4.182 + else {
4.183 + return INVALID;
4.184 + }
4.185 +
4.186 + break;
4.187 +
4.188 + }
4.189 + case impl_fifo : {
4.190 +
4.191 + if( ! fifo_nodes.empty() ) {
4.192 + Node a=fifo_nodes.front();
4.193 + fifo_nodes.pop_front();
4.194 + return a;
4.195 + }
4.196 + else {
4.197 + return INVALID;
4.198 + }
4.199 + break;
4.200 + }
4.201 + }
4.202 + //
4.203 + return INVALID;
4.204 + }
4.205 +
4.206 + //Puts node 'a' among the active nodes
4.207 + void make_active(const Node& a){
4.208 + //s and t never become active
4.209 + if (a!=s && a!= t){
4.210 + switch(implementation){
4.211 + case impl_highest_label :
4.212 + active_nodes[level[a]].push_back(a);
4.213 + break;
4.214 + case impl_fifo :
4.215 + fifo_nodes.push_back(a);
4.216 + break;
4.217 + }
4.218 +
4.219 + }
4.220 +
4.221 + //Update highest_active label
4.222 + if (highest_active<level[a]){
4.223 + highest_active=level[a];
4.224 + }
4.225 +
4.226 + }
4.227 +
4.228 + //Changes the level of node a and make sufficent changes
4.229 + void change_level_to(Node a, int new_value){
4.230 + int seged = level[a];
4.231 + level.set(a,new_value);
4.232 + --num_of_nodes_on_level[seged];
4.233 + ++num_of_nodes_on_level[new_value];
4.234 + }
4.235 +
4.236 + //Collection of things useful (or necessary) to do before running
4.237 +
4.238 + void preprocess(){
4.239 +
4.240 + //---------------------------------------
4.241 + //Initialize parameters
4.242 + //---------------------------------------
4.243 +
4.244 + //Setting starting preflow, level and excess values to zero
4.245 + //This can be important, if the algorithm is run more then once
4.246 + for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
4.247 + level.set(i,0);
4.248 + excess.set(i,0);
4.249 + for(OutEdgeIt j=G.template first<OutEdgeIt>(i); G.valid(j); G.next(j))
4.250 + preflow.set(j, 0);
4.251 + }
4.252 + num_of_nodes_on_level[0]=number_of_nodes;
4.253 + highest_active=0;
4.254 + //---------------------------------------
4.255 + //Initialize parameters
4.256 + //---------------------------------------
4.257 +
4.258 +
4.259 + //------------------------------------
4.260 + //This is the only part that uses BFS
4.261 + //------------------------------------
4.262 +
4.263 + /*Reverse_bfs from t, to find the starting level.*/
4.264 + //Copyright: Jacint
4.265 + change_level_to(t,0);
4.266 +
4.267 + std::queue<Node> bfs_queue;
4.268 + bfs_queue.push(t);
4.269 +
4.270 + while (!bfs_queue.empty()) {
4.271 +
4.272 + Node v=bfs_queue.front();
4.273 + bfs_queue.pop();
4.274 + int l=level[v]+1;
4.275 +
4.276 + InEdgeIt e;
4.277 + for(G.first(e,v); G.valid(e); G.next(e)) {
4.278 + Node w=G.tail(e);
4.279 + if ( level[w] == number_of_nodes && w != s ) {
4.280 + bfs_queue.push(w);
4.281 + //Node first=level_list[l];
4.282 + //if ( G.valid(first) ) left.set(first,w);
4.283 + //right.set(w,first);
4.284 + //level_list[l]=w;
4.285 + change_level_to(w, l);
4.286 + //level.set(w, l);
4.287 + }
4.288 + }
4.289 + }
4.290 + change_level_to(s,number_of_nodes);
4.291 + //level.set(s,number_of_nodes);
4.292 +
4.293 + /*
4.294 + //Setting starting level values using reverse bfs
4.295 + reverse_bfs<Graph> rev_bfs(G,t);
4.296 + rev_bfs.run();
4.297 + //write_property_vector(rev_bfs.dist,"rev_bfs");
4.298 + for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
4.299 + change_level_to(i,rev_bfs.dist(i));
4.300 + //level.put(i,rev_bfs.dist.get(i));
4.301 + }
4.302 + */
4.303 + //------------------------------------
4.304 + //This is the only part that uses BFS
4.305 + //------------------------------------
4.306 +
4.307 +
4.308 + //Starting level of s
4.309 + change_level_to(s,number_of_nodes);
4.310 + //level.put(s,number_of_nodes);
4.311 +
4.312 +
4.313 + //we push as much preflow from s as possible to start with
4.314 + for(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){
4.315 + modify_preflow(j,capacity[j] );
4.316 + make_active(G.head(j));
4.317 + int lev=level[G.head(j)];
4.318 + if(highest_active<lev){
4.319 + highest_active=lev;
4.320 + }
4.321 + }
4.322 + //cout<<highest_active<<endl;
4.323 + }
4.324 +
4.325 +
4.326 + //If the preflow is less than the capacity on the given edge
4.327 + //then it is an edge in the residual graph
4.328 + bool is_admissible_forward_edge(Edge j, int& new_level){
4.329 +
4.330 + if (capacity[j]>preflow[j]){
4.331 + if(level[G.tail(j)]==level[G.head(j)]+1){
4.332 + return true;
4.333 + }
4.334 + else{
4.335 + if (level[G.head(j)] < new_level)
4.336 + new_level=level[G.head(j)];
4.337 + }
4.338 + }
4.339 + return false;
4.340 + }
4.341 +
4.342 + //If the preflow is greater than 0 on the given edge
4.343 + //then the edge reversd is an edge in the residual graph
4.344 + bool is_admissible_backward_edge(Edge j, int& new_level){
4.345 +
4.346 + if (0<preflow[j]){
4.347 + if(level[G.tail(j)]==level[G.head(j)]-1){
4.348 +
4.349 + return true;
4.350 + }
4.351 + else{
4.352 + if (level[G.tail(j)] < new_level)
4.353 + new_level=level[G.tail(j)];
4.354 + }
4.355 +
4.356 + }
4.357 + return false;
4.358 + }
4.359 +
4.360 +
4.361 + }; //class preflow_push
4.362 +
4.363 + template<typename Graph, typename T>
4.364 + T preflow_push<Graph, T>::run() {
4.365 +
4.366 + preprocess();
4.367 + //write_property_vector(level,"level");
4.368 + T e,v;
4.369 + Node a;
4.370 + while (a=get_active_node(), G.valid(a)){
4.371 +
4.372 + //cout<<G.id(a)<<endl;
4.373 + //write_property_vector(excess,"excess");
4.374 + //write_property_vector(level,"level");
4.375 +
4.376 +
4.377 + bool go_to_next_node=false;
4.378 + e = excess[a];
4.379 + while (!go_to_next_node){
4.380 + //Initial value for the new level for the active node we are dealing with
4.381 + int new_level=2*number_of_nodes;
4.382 + //write_property_vector(excess,"excess");
4.383 + //write_property_vector(level,"level");
4.384 + //cout<<G.id(a)<<endl;
4.385 + //Out edges from node a
4.386 + {
4.387 + OutEdgeIt j=G.template first<OutEdgeIt>(a);
4.388 + while (G.valid(j) && e){
4.389 +
4.390 + if (is_admissible_forward_edge(j,new_level)){
4.391 + v=min(e,capacity[j] - preflow[j]);
4.392 + e -= v;
4.393 + //New node might become active
4.394 + if (excess[G.head(j)]==0){
4.395 + make_active(G.head(j));
4.396 + }
4.397 + modify_preflow(j,v);
4.398 + }
4.399 + G.next(j);
4.400 + }
4.401 + }
4.402 + //In edges to node a
4.403 + {
4.404 + InEdgeIt j=G.template first<InEdgeIt>(a);
4.405 + while (G.valid(j) && e){
4.406 + if (is_admissible_backward_edge(j,new_level)){
4.407 + v=min(e,preflow[j]);
4.408 + e -= v;
4.409 + //New node might become active
4.410 + if (excess[G.tail(j)]==0){
4.411 + make_active(G.tail(j));
4.412 + }
4.413 + modify_preflow(j,-v);
4.414 + }
4.415 + G.next(j);
4.416 + }
4.417 + }
4.418 +
4.419 + //if (G.id(a)==999)
4.420 + //cout<<new_level<<" e: "<<e<<endl;
4.421 + //cout<<G.id(a)<<" "<<new_level<<endl;
4.422 +
4.423 + if (0==e){
4.424 + //Saturating push
4.425 + go_to_next_node=true;
4.426 + }
4.427 + else{//If there is still excess in node a
4.428 +
4.429 + //change_level_to(a,new_level+1);
4.430 +
4.431 + //Level remains empty
4.432 + if (num_of_nodes_on_level[level[a]]==1){
4.433 + change_level_to(a,number_of_nodes);
4.434 + //go_to_next_node=True;
4.435 + }
4.436 + else{
4.437 + change_level_to(a,new_level+1);
4.438 + //increase_level(a);
4.439 + }
4.440 +
4.441 +
4.442 +
4.443 +
4.444 + switch(node_examination){
4.445 + case examine_to_relabel:
4.446 + make_active(a);
4.447 +
4.448 + go_to_next_node = true;
4.449 + break;
4.450 + default:
4.451 + break;
4.452 + }
4.453 +
4.454 +
4.455 +
4.456 + }//if (0==e)
4.457 + }
4.458 + }
4.459 + maxflow_value = excess[t];
4.460 + return maxflow_value;
4.461 + }//run
4.462 +
4.463 +
4.464 +}//namespace hugo
4.465 +
4.466 +#endif //PREFLOW_PUSH_HH
5.1 --- a/src/work/athos/reverse_bfs.hh Thu Apr 15 14:41:20 2004 +0000
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,103 +0,0 @@
5.4 -/*
5.5 -reverse_bfs
5.6 -by jacint
5.7 -Performs a bfs on the out edges. It does not count predecessors,
5.8 -only the distances, but one can easily modify it to know the pred as well.
5.9 -
5.10 -Constructor:
5.11 -
5.12 -reverse_bfs(graph_type& G, node_iterator t)
5.13 -
5.14 -
5.15 -
5.16 -Member functions:
5.17 -
5.18 -void run(): runs a reverse bfs from t
5.19 -
5.20 - The following function should be used after run() was already run.
5.21 -
5.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.
5.23 -
5.24 -*/
5.25 -#ifndef REVERSE_BFS_HH
5.26 -#define REVERSE_BFS_HH
5.27 -
5.28 -#include <queue>
5.29 -
5.30 -//#include <marci_list_graph.hh>
5.31 -//#include <marci_property_vector.hh>
5.32 -
5.33 -
5.34 -
5.35 -namespace hugo {
5.36 -
5.37 - template <typename graph_type>
5.38 - class reverse_bfs {
5.39 -
5.40 - typedef typename graph_type::NodeIt NodeIt;
5.41 - typedef typename graph_type::EdgeIt EdgeIt;
5.42 - typedef typename graph_type::EachNodeIt EachNodeIt;
5.43 - typedef typename graph_type::EachEdgeIt EachEdgeIt;
5.44 - typedef typename graph_type::OutEdgeIt OutEdgeIt;
5.45 - typedef typename graph_type::InEdgeIt InEdgeIt;
5.46 - typedef typename graph_type::SymEdgeIt SymEdgeIt;
5.47 -
5.48 -
5.49 -
5.50 - graph_type& G;
5.51 - NodeIt t;
5.52 -// node_property_vector<graph_type, edge_iterator> pred;
5.53 - //node_property_vector<graph_type, int>
5.54 - typename graph_type::NodeMap<int> distance;
5.55 -
5.56 -
5.57 - public :
5.58 -
5.59 - /*
5.60 - The distance of the nodes is n, except t for which it is 0.
5.61 - */
5.62 - reverse_bfs(graph_type& _G, NodeIt _t) :
5.63 - G(_G), t(_t),
5.64 - distance(G, G.nodeNum()) {
5.65 - distance.set(t,0);
5.66 - }
5.67 -
5.68 - void run() {
5.69 -
5.70 - //node_property_vector<graph_type, bool>
5.71 - typename graph_type::NodeMap<bool> reached(G, false);
5.72 - reached.set(t, true);
5.73 -
5.74 - std::queue<NodeIt> bfs_queue;
5.75 - bfs_queue.push(t);
5.76 -
5.77 - while (!bfs_queue.empty()) {
5.78 -
5.79 - NodeIt v=bfs_queue.front();
5.80 - bfs_queue.pop();
5.81 -
5.82 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
5.83 - NodeIt w=G.tail(e);
5.84 - if (!reached.get(w)) {
5.85 - bfs_queue.push(w);
5.86 - distance.set(w, distance.get(v)+1);
5.87 - reached.set(w, true);
5.88 - }
5.89 - }
5.90 - }
5.91 - }
5.92 -
5.93 -
5.94 -
5.95 - int dist(NodeIt v) {
5.96 - return distance.get(v);
5.97 - }
5.98 -
5.99 -
5.100 - };
5.101 -
5.102 -} // namespace hugo
5.103 -
5.104 -#endif //REVERSE_BFS_HH
5.105 -
5.106 -