1.1 --- a/src/work/athos/pf_demo.cc Mon Feb 16 11:38:19 2004 +0000
1.2 +++ b/src/work/athos/pf_demo.cc Mon Feb 16 15:57:59 2004 +0000
1.3 @@ -2,9 +2,9 @@
1.4 #include <vector>
1.5 #include <string>
1.6
1.7 -#include "marci_list_graph.hh"
1.8 +#include "list_graph.hh"
1.9 #include "marci_graph_traits.hh"
1.10 -#include "marci_property_vector.hh"
1.11 +//#include "marci_property_vector.hh"
1.12 #include "preflow_push.hh"
1.13
1.14 using namespace marci;
1.15 @@ -12,24 +12,67 @@
1.16
1.17 int main (int, char*[])
1.18 {
1.19 - typedef graph_traits<list_graph>::node_iterator node_iterator;
1.20 - typedef graph_traits<list_graph>::edge_iterator edge_iterator;
1.21 - typedef graph_traits<list_graph>::each_node_iterator each_node_iterator;
1.22 - typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator;
1.23 - typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator;
1.24 - typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;
1.25 - typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;
1.26
1.27 - list_graph flow_test;
1.28 -
1.29
1.30 + typedef ListGraph::NodeIt NodeIt;
1.31 + typedef ListGraph::EdgeIt EdgeIt;
1.32 + /*
1.33 + typedef ListGraph::EachNodeIt EachNodeIt;
1.34 + typedef ListGraph::EachEdgeIt EachEdgeIt;
1.35 + typedef ListGraph::OutEdgeIt OutEdgeIt;
1.36 + typedef ListGraph::InEdgeIt InEdgeIt;
1.37 + typedef ListGraph::SymEdgeIt SymEdgeIt;
1.38 + */
1.39 +
1.40 + //Marci példája
1.41 + ListGraph flowG;
1.42 +
1.43 + NodeIt s=flowG.addNode();
1.44 + NodeIt v1=flowG.addNode();
1.45 + NodeIt v2=flowG.addNode();
1.46 + NodeIt v3=flowG.addNode();
1.47 + NodeIt v4=flowG.addNode();
1.48 + NodeIt t=flowG.addNode();
1.49 +
1.50 +
1.51 + EdgeIt s_v1=flowG.addEdge(s, v1);
1.52 + EdgeIt s_v2=flowG.addEdge(s, v2);
1.53 + EdgeIt v1_v2=flowG.addEdge(v1, v2);
1.54 + EdgeIt v2_v1=flowG.addEdge(v2, v1);
1.55 + EdgeIt v1_v3=flowG.addEdge(v1, v3);
1.56 + EdgeIt v3_v2=flowG.addEdge(v3, v2);
1.57 + EdgeIt v2_v4=flowG.addEdge(v2, v4);
1.58 + EdgeIt v4_v3=flowG.addEdge(v4, v3);
1.59 + EdgeIt v3_t=flowG.addEdge(v3, t);
1.60 + EdgeIt v4_t=flowG.addEdge(v4, t);
1.61 +
1.62 + ListGraph::EdgeMap<int> cap(flowG);
1.63 +
1.64 + cap.set(s_v1, 16);
1.65 + cap.set(s_v2, 13);
1.66 + cap.set(v1_v2, 10);
1.67 + cap.set(v2_v1, 4);
1.68 + cap.set(v1_v3, 12);
1.69 + cap.set(v3_v2, 9);
1.70 + cap.set(v2_v4, 14);
1.71 + cap.set(v4_v3, 7);
1.72 + cap.set(v3_t, 20);
1.73 + cap.set(v4_t, 4);
1.74 +
1.75 +
1.76 +
1.77 +
1.78 +
1.79 +
1.80 +
1.81 + /*
1.82 //Ahuja könyv példája
1.83 node_iterator s=flow_test.add_node();
1.84 - node_iterator v2=flow_test.add_node();
1.85 - node_iterator v3=flow_test.add_node();
1.86 - node_iterator v4=flow_test.add_node();
1.87 - node_iterator v5=flow_test.add_node();
1.88 - node_iterator t=flow_test.add_node();
1.89 + NodeIt v2=flow_test.add_node();
1.90 + NodeIt v3=flow_test.add_node();
1.91 + NodeIt v4=flow_test.add_node();
1.92 + NodeIt v5=flow_test.add_node();
1.93 + NodeIt t=flow_test.add_node();
1.94
1.95 node_property_vector<list_graph, std::string> node_name(flow_test);
1.96 node_name.put(s, "s");
1.97 @@ -70,52 +113,15 @@
1.98 //edge_iterator t_s=flow_test.add_edge(t, s);
1.99 //cap.put(t_s, 20);
1.100
1.101 -
1.102 - /*
1.103 - //Marci példája
1.104 - node_iterator s=flow_test.add_node();
1.105 - node_iterator v1=flow_test.add_node();
1.106 - node_iterator v2=flow_test.add_node();
1.107 - node_iterator v3=flow_test.add_node();
1.108 - node_iterator v4=flow_test.add_node();
1.109 - node_iterator t=flow_test.add_node();
1.110 -
1.111 - node_property_vector<list_graph, std::string> node_name(flow_test);
1.112 - node_name.put(s, "s");
1.113 - node_name.put(v1, "v1");
1.114 - node_name.put(v2, "v2");
1.115 - node_name.put(v3, "v3");
1.116 - node_name.put(v4, "v4");
1.117 - node_name.put(t, "t");
1.118 + */
1.119
1.120 - edge_iterator s_v1=flow_test.add_edge(s, v1);
1.121 - edge_iterator s_v2=flow_test.add_edge(s, v2);
1.122 - edge_iterator v1_v2=flow_test.add_edge(v1, v2);
1.123 - edge_iterator v2_v1=flow_test.add_edge(v2, v1);
1.124 - edge_iterator v1_v3=flow_test.add_edge(v1, v3);
1.125 - edge_iterator v3_v2=flow_test.add_edge(v3, v2);
1.126 - edge_iterator v2_v4=flow_test.add_edge(v2, v4);
1.127 - edge_iterator v4_v3=flow_test.add_edge(v4, v3);
1.128 - edge_iterator v3_t=flow_test.add_edge(v3, t);
1.129 - edge_iterator v4_t=flow_test.add_edge(v4, t);
1.130 -
1.131 - edge_property_vector<list_graph, int> cap(flow_test);
1.132 - cap.put(s_v1, 16);
1.133 - cap.put(s_v2, 13);
1.134 - cap.put(v1_v2, 10);
1.135 - cap.put(v2_v1, 4);
1.136 - cap.put(v1_v3, 12);
1.137 - cap.put(v3_v2, 9);
1.138 - cap.put(v2_v4, 14);
1.139 - cap.put(v4_v3, 7);
1.140 - cap.put(v3_t, 20);
1.141 - cap.put(v4_t, 4);
1.142 - */
1.143 +
1.144 +
1.145 /*Egyszerű példa
1.146 - node_iterator s=flow_test.add_node();
1.147 - node_iterator v1=flow_test.add_node();
1.148 - node_iterator v2=flow_test.add_node();
1.149 - node_iterator t=flow_test.add_node();
1.150 + NodeIt s=flow_test.add_node();
1.151 + NodeIt v1=flow_test.add_node();
1.152 + NodeIt v2=flow_test.add_node();
1.153 + NodeIt t=flow_test.add_node();
1.154
1.155 node_property_vector<list_graph, std::string> node_name(flow_test);
1.156 node_name.put(s, "s");
1.157 @@ -135,9 +141,11 @@
1.158 */
1.159
1.160 std::cout << "preflow-push algorithm test..." << std::endl;
1.161 +
1.162 + /*
1.163 std::cout << "on directed graph graph" << std::endl; //<< flow_test;
1.164 std::cout << "names and capacity values" << std::endl;
1.165 - for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
1.166 + for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) {
1.167 std::cout << node_name.get(i) << ": ";
1.168 std::cout << "out edges: ";
1.169 for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
1.170 @@ -147,13 +155,13 @@
1.171 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
1.172 std::cout << std::endl;
1.173 }
1.174 -
1.175 + */
1.176
1.177 - //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
1.178 + //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) {
1.179 // std::cout << i << " ";
1.180 //}
1.181
1.182 - preflow_push<list_graph, int> preflow_push_test(flow_test, s, t, cap);
1.183 + preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap);
1.184 cout << preflow_push_test.run()<<endl;
1.185
1.186 //cap.put(v5_t, 9);
2.1 --- a/src/work/athos/preflow_push.hh Mon Feb 16 11:38:19 2004 +0000
2.2 +++ b/src/work/athos/preflow_push.hh Mon Feb 16 15:57:59 2004 +0000
2.3 @@ -6,7 +6,8 @@
2.4 #include <vector>
2.5 //#include "pf_hiba.hh"
2.6 //#include <marci_list_graph.hh>
2.7 -#include <marci_graph_traits.hh>
2.8 +//#include <marci_graph_traits.hh>
2.9 +
2.10 #include "reverse_bfs.hh"
2.11
2.12 using namespace std;
2.13 @@ -17,13 +18,25 @@
2.14 class preflow_push {
2.15
2.16 //Hasznos typedef-ek
2.17 + typedef typename graph_type::NodeIt NodeIt;
2.18 + typedef typename graph_type::EdgeIt EdgeIt;
2.19 + typedef typename graph_type::EachNodeIt EachNodeIt;
2.20 + typedef typename graph_type::EachEdgeIt EachEdgeIt;
2.21 + typedef typename graph_type::OutEdgeIt OutEdgeIt;
2.22 + typedef typename graph_type::InEdgeIt InEdgeIt;
2.23 + typedef typename graph_type::SymEdgeIt SymEdgeIt;
2.24 +
2.25 +
2.26 +
2.27 + /*
2.28 typedef graph_traits<graph_type>::node_iterator node_iterator;
2.29 - typedef graph_traits<graph_type>::edge_iterator edge_iterator;
2.30 + typedef graph_traits<graph_type>::EdgeIt EdgeIt;
2.31 typedef graph_traits<graph_type>::each_node_iterator each_node_iterator;
2.32 - typedef graph_traits<graph_type>::each_edge_iterator each_edge_iterator;
2.33 - typedef graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
2.34 - typedef graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
2.35 - typedef graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
2.36 + typedef graph_traits<graph_type>::each_EdgeIt each_EdgeIt;
2.37 + typedef graph_traits<graph_type>::out_EdgeIt out_EdgeIt;
2.38 + typedef graph_traits<graph_type>::InEdgeIt InEdgeIt;
2.39 + typedef graph_traits<graph_type>::sym_EdgeIt sym_EdgeIt;
2.40 + */
2.41
2.42 //---------------------------------------------
2.43 //Parameters of the algorithm
2.44 @@ -43,41 +56,49 @@
2.45 private:
2.46 //input
2.47 graph_type& G;
2.48 - node_iterator s;
2.49 - node_iterator t;
2.50 - edge_property_vector<graph_type, T> &capacity;
2.51 + NodeIt s;
2.52 + NodeIt t;
2.53 + typename graph_type::EdgeMap<T> &capacity;
2.54 + //typename graph_type::EdgeMap<T> &capacity;
2.55 //output
2.56 - edge_property_vector<graph_type, T> preflow;
2.57 + //typename graph_type::EdgeMap<T>
2.58 + typename graph_type::EdgeMap<T> preflow;
2.59 T maxflow_value;
2.60
2.61 //auxiliary variables for computation
2.62 int number_of_nodes;
2.63 - node_property_vector<graph_type, int> level;
2.64 - node_property_vector<graph_type, T> excess;
2.65 +
2.66 +
2.67 + typename graph_type::NodeMap<int> level;
2.68 + typename graph_type::NodeMap<T> excess;
2.69 + //node_property_vector<graph_type, int> level;
2.70 + //node_property_vector<graph_type, T> excess;
2.71
2.72 //Number of nodes on each level
2.73 vector<int> num_of_nodes_on_level;
2.74
2.75 //For the FIFO implementation
2.76 - list<node_iterator> fifo_nodes;
2.77 + list<NodeIt> fifo_nodes;
2.78 //For 'highest label' implementation
2.79 int highest_active;
2.80 //int second_highest_active;
2.81 - vector< list<node_iterator> > active_nodes;
2.82 + vector< list<NodeIt> > active_nodes;
2.83
2.84 public:
2.85
2.86 //Constructing the object using the graph, source, sink and capacity vector
2.87 preflow_push(
2.88 graph_type& _G,
2.89 - node_iterator _s,
2.90 - node_iterator _t,
2.91 - edge_property_vector<graph_type, T>& _capacity)
2.92 + NodeIt _s,
2.93 + NodeIt _t,
2.94 + typename graph_type::EdgeMap<T> & _capacity)
2.95 : G(_G), s(_s), t(_t),
2.96 capacity(_capacity),
2.97 preflow(_G),
2.98 //Counting the number of nodes
2.99 - number_of_nodes(number_of(G.first_node())),
2.100 + //number_of_nodes(count(G.first<EachNodeIt>())),
2.101 + number_of_nodes(G.nodeNum()),
2.102 +
2.103 level(_G),
2.104 excess(_G)//,
2.105 // Default constructor: active_nodes()
2.106 @@ -106,7 +127,7 @@
2.107 //Returns the value of a maximal flow
2.108 T run();
2.109
2.110 - edge_property_vector<graph_type, T> getmaxflow(){
2.111 + typename graph_type::EdgeMap<T> getmaxflow(){
2.112 return preflow;
2.113 }
2.114
2.115 @@ -114,32 +135,33 @@
2.116 private:
2.117 //For testing purposes only
2.118 //Lists the node_properties
2.119 - void write_property_vector(node_property_vector<graph_type, T> a,
2.120 + void write_property_vector(typename graph_type::NodeMap<T> a,
2.121 + //node_property_vector<graph_type, T> a,
2.122 char* prop_name="property"){
2.123 - for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
2.124 + for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
2.125 cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl;
2.126 }
2.127 cout<<endl;
2.128 }
2.129
2.130 //Modifies the excess of the node and makes sufficient changes
2.131 - void modify_excess(const node_iterator& a ,T v){
2.132 + void modify_excess(const NodeIt& a ,T v){
2.133 T old_value=excess.get(a);
2.134 - excess.put(a,old_value+v);
2.135 + excess.set(a,old_value+v);
2.136 }
2.137
2.138 //This private procedure is supposed to modify the preflow on edge j
2.139 //by value v (which can be positive or negative as well)
2.140 //and maintain the excess on the head and tail
2.141 //Here we do not check whether this is possible or not
2.142 - void modify_preflow(edge_iterator j, const T& v){
2.143 + void modify_preflow(EdgeIt j, const T& v){
2.144
2.145 //Auxiliary variable
2.146 T old_value;
2.147
2.148 //Modifiyng the edge
2.149 old_value=preflow.get(j);
2.150 - preflow.put(j,old_value+v);
2.151 + preflow.set(j,old_value+v);
2.152
2.153
2.154 //Modifiyng the head
2.155 @@ -152,7 +174,7 @@
2.156
2.157 //Gives the active node to work with
2.158 //(depending on the implementation to be used)
2.159 - node_iterator get_active_node(){
2.160 + NodeIt get_active_node(){
2.161 //cout<<highest_active<<endl;
2.162
2.163 switch(implementation) {
2.164 @@ -164,12 +186,12 @@
2.165 }
2.166
2.167 if( highest_active>=0) {
2.168 - node_iterator a=active_nodes[highest_active].front();
2.169 + NodeIt a=active_nodes[highest_active].front();
2.170 active_nodes[highest_active].pop_front();
2.171 return a;
2.172 }
2.173 else {
2.174 - return node_iterator();
2.175 + return NodeIt();
2.176 }
2.177
2.178 break;
2.179 @@ -178,22 +200,22 @@
2.180 case impl_fifo : {
2.181
2.182 if( ! fifo_nodes.empty() ) {
2.183 - node_iterator a=fifo_nodes.front();
2.184 + NodeIt a=fifo_nodes.front();
2.185 fifo_nodes.pop_front();
2.186 return a;
2.187 }
2.188 else {
2.189 - return node_iterator();
2.190 + return NodeIt();
2.191 }
2.192 break;
2.193 }
2.194 }
2.195 //
2.196 - return node_iterator();
2.197 + return NodeIt();
2.198 }
2.199
2.200 //Puts node 'a' among the active nodes
2.201 - void make_active(const node_iterator& a){
2.202 + void make_active(const NodeIt& a){
2.203 //s and t never become active
2.204 if (a!=s && a!= t){
2.205 switch(implementation){
2.206 @@ -215,14 +237,15 @@
2.207 }
2.208
2.209 //Changes the level of node a and make sufficent changes
2.210 - void change_level_to(node_iterator a, int new_value){
2.211 + void change_level_to(NodeIt a, int new_value){
2.212 int seged = level.get(a);
2.213 - level.put(a,new_value);
2.214 + level.set(a,new_value);
2.215 --num_of_nodes_on_level[seged];
2.216 ++num_of_nodes_on_level[new_value];
2.217 }
2.218
2.219 //Collection of things useful (or necessary) to do before running
2.220 +
2.221 void preprocess(){
2.222
2.223 //---------------------------------------
2.224 @@ -231,11 +254,11 @@
2.225
2.226 //Setting starting preflow, level and excess values to zero
2.227 //This can be important, if the algorithm is run more then once
2.228 - for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
2.229 - level.put(i,0);
2.230 - excess.put(i,0);
2.231 - for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j)
2.232 - preflow.put(j, 0);
2.233 + for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
2.234 + level.set(i,0);
2.235 + excess.set(i,0);
2.236 + for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j)
2.237 + preflow.set(j, 0);
2.238 }
2.239 num_of_nodes_on_level[0]=number_of_nodes;
2.240 highest_active=0;
2.241 @@ -251,7 +274,7 @@
2.242 reverse_bfs<graph_type> rev_bfs(G,t);
2.243 rev_bfs.run();
2.244 //write_property_vector(rev_bfs.dist,"rev_bfs");
2.245 - for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
2.246 + for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
2.247 change_level_to(i,rev_bfs.dist(i));
2.248 //level.put(i,rev_bfs.dist.get(i));
2.249 }
2.250 @@ -266,7 +289,7 @@
2.251
2.252
2.253 //we push as much preflow from s as possible to start with
2.254 - for(out_edge_iterator j=G.first_out_edge(s); j.valid(); ++j){
2.255 + for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){
2.256 modify_preflow(j,capacity.get(j) );
2.257 make_active(G.head(j));
2.258 int lev=level.get(G.head(j));
2.259 @@ -280,7 +303,7 @@
2.260
2.261 //If the preflow is less than the capacity on the given edge
2.262 //then it is an edge in the residual graph
2.263 - bool is_admissible_forward_edge(out_edge_iterator j, int& new_level){
2.264 + bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){
2.265 if (capacity.get(j)>preflow.get(j)){
2.266 if(level.get(G.tail(j))==level.get(G.head(j))+1){
2.267 return true;
2.268 @@ -295,7 +318,7 @@
2.269
2.270 //If the preflow is greater than 0 on the given edge
2.271 //then the edge reversd is an edge in the residual graph
2.272 - bool is_admissible_backward_edge(in_edge_iterator j, int& new_level){
2.273 + bool is_admissible_backward_edge(InEdgeIt j, int& new_level){
2.274 if (0<preflow.get(j)){
2.275 if(level.get(G.tail(j))==level.get(G.head(j))-1){
2.276 return true;
2.277 @@ -318,22 +341,25 @@
2.278 preprocess();
2.279
2.280 T e,v;
2.281 - node_iterator a;
2.282 + NodeIt a;
2.283 while (a=get_active_node(), a.valid()){
2.284 //cout<<G.id(a)<<endl;
2.285 //write_property_vector(excess,"excess");
2.286 //write_property_vector(level,"level");
2.287
2.288 - //Initial value for the new level for the active node we are dealing with
2.289 - int new_level=2*number_of_nodes;
2.290
2.291 bool go_to_next_node=false;
2.292 e = excess.get(a);
2.293 while (!go_to_next_node){
2.294 -
2.295 +
2.296 + //Initial value for the new level for the active node we are dealing with
2.297 + int new_level=2*number_of_nodes;
2.298 + //write_property_vector(excess,"excess");
2.299 + //write_property_vector(level,"level");
2.300 + //cout<<G.id(a)<<endl;
2.301 //Out edges from node a
2.302 {
2.303 - out_edge_iterator j=G.first_out_edge(a);
2.304 + OutEdgeIt j=G.template first<OutEdgeIt>(a);
2.305 while (j.valid() && e){
2.306
2.307 if (is_admissible_forward_edge(j,new_level)){
2.308 @@ -350,7 +376,7 @@
2.309 }
2.310 //In edges to node a
2.311 {
2.312 - in_edge_iterator j=G.first_in_edge(a);
2.313 + InEdgeIt j=G.template first<InEdgeIt>(a);
2.314 while (j.valid() && e){
2.315 if (is_admissible_backward_edge(j,new_level)){
2.316 v=min(e,preflow.get(j));
2.317 @@ -372,7 +398,9 @@
2.318 go_to_next_node=true;
2.319 }
2.320 else{//If there is still excess in node a
2.321 -
2.322 +
2.323 + //change_level_to(a,new_level+1);
2.324 +
2.325 //Level remains empty
2.326 if (num_of_nodes_on_level[level.get(a)]==1){
2.327 change_level_to(a,number_of_nodes);
2.328 @@ -382,7 +410,7 @@
2.329 change_level_to(a,new_level+1);
2.330 //increase_level(a);
2.331 }
2.332 -
2.333 +
2.334
2.335
2.336
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/athos/reverse_bfs.hh Mon Feb 16 15:57:59 2004 +0000
3.3 @@ -0,0 +1,103 @@
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_list_graph.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 +
3.40 + typedef typename graph_type::NodeIt NodeIt;
3.41 + typedef typename graph_type::EdgeIt EdgeIt;
3.42 + typedef typename graph_type::EachNodeIt EachNodeIt;
3.43 + typedef typename graph_type::EachEdgeIt EachEdgeIt;
3.44 + typedef typename graph_type::OutEdgeIt OutEdgeIt;
3.45 + typedef typename graph_type::InEdgeIt InEdgeIt;
3.46 + typedef typename graph_type::SymEdgeIt SymEdgeIt;
3.47 +
3.48 +
3.49 +
3.50 + graph_type& G;
3.51 + NodeIt t;
3.52 +// node_property_vector<graph_type, edge_iterator> pred;
3.53 + //node_property_vector<graph_type, int>
3.54 + typename graph_type::NodeMap<int> distance;
3.55 +
3.56 +
3.57 + public :
3.58 +
3.59 + /*
3.60 + The distance of the nodes is n, except t for which it is 0.
3.61 + */
3.62 + reverse_bfs(graph_type& _G, NodeIt _t) :
3.63 + G(_G), t(_t),
3.64 + distance(G, G.nodeNum()) {
3.65 + distance.set(t,0);
3.66 + }
3.67 +
3.68 + void run() {
3.69 +
3.70 + //node_property_vector<graph_type, bool>
3.71 + typename graph_type::NodeMap<bool> reached(G, false);
3.72 + reached.set(t, true);
3.73 +
3.74 + std::queue<NodeIt> bfs_queue;
3.75 + bfs_queue.push(t);
3.76 +
3.77 + while (!bfs_queue.empty()) {
3.78 +
3.79 + NodeIt v=bfs_queue.front();
3.80 + bfs_queue.pop();
3.81 +
3.82 + for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
3.83 + NodeIt w=G.tail(e);
3.84 + if (!reached.get(w)) {
3.85 + bfs_queue.push(w);
3.86 + distance.set(w, distance.get(v)+1);
3.87 + reached.set(w, true);
3.88 + }
3.89 + }
3.90 + }
3.91 + }
3.92 +
3.93 +
3.94 +
3.95 + int dist(NodeIt v) {
3.96 + return distance.get(v);
3.97 + }
3.98 +
3.99 +
3.100 + };
3.101 +
3.102 +} // namespace marci
3.103 +
3.104 +#endif //REVERSE_BFS_HH
3.105 +
3.106 +