Changeset 77:69b2d279c8f0 in lemon-0.x for src/work/athos/preflow_push.hh

Timestamp:

02/16/04 16:57:59 (20 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@100

Message:

Kijavitottam a preflow_push algoritmust az uj koncept szerint.

File:

• src/work/athos/preflow_push.hh (modified) (26 diffs)

src/work/athos/preflow_push.hh

@@ -7 +7 @@
 //#include "pf_hiba.hh"
 //#include <marci_list_graph.hh>
-#include <marci_graph_traits.hh>
+//#include <marci_graph_traits.hh>
+
 #include "reverse_bfs.hh"
 
@@ -18 +19 @@
 
     //Hasznos typedef-ek
+    typedef typename graph_type::NodeIt NodeIt;
+    typedef typename graph_type::EdgeIt EdgeIt;
+    typedef typename graph_type::EachNodeIt EachNodeIt;
+    typedef typename graph_type::EachEdgeIt EachEdgeIt;
+    typedef typename graph_type::OutEdgeIt OutEdgeIt;
+    typedef typename graph_type::InEdgeIt InEdgeIt;
+    typedef typename graph_type::SymEdgeIt SymEdgeIt;
+
+
+
+    /*
     typedef graph_traits<graph_type>::node_iterator node_iterator;
-    typedef graph_traits<graph_type>::edge_iterator edge_iterator;
+    typedef graph_traits<graph_type>::EdgeIt EdgeIt;
     typedef graph_traits<graph_type>::each_node_iterator each_node_iterator;
-    typedef graph_traits<graph_type>::each_edge_iterator each_edge_iterator;
-    typedef graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
-    typedef graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
-    typedef graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
+    typedef graph_traits<graph_type>::each_EdgeIt each_EdgeIt;
+    typedef graph_traits<graph_type>::out_EdgeIt out_EdgeIt;
+    typedef graph_traits<graph_type>::InEdgeIt InEdgeIt;
+    typedef graph_traits<graph_type>::sym_EdgeIt sym_EdgeIt;
+    */
 
     //---------------------------------------------
@@ -44 +57 @@
     //input
     graph_type& G;
-    node_iterator s;
-    node_iterator t;
-    edge_property_vector<graph_type, T> &capacity;
+    NodeIt s;
+    NodeIt t;
+    typename graph_type::EdgeMap<T> &capacity;
+    //typename graph_type::EdgeMap<T>  &capacity;
     //output
-    edge_property_vector<graph_type, T> preflow;
+    //typename graph_type::EdgeMap<T>  
+    typename graph_type::EdgeMap<T> preflow;
     T maxflow_value;
   
     //auxiliary variables for computation
     int number_of_nodes;
-    node_property_vector<graph_type, int> level;
-    node_property_vector<graph_type, T> excess;
+    
+    
+    typename graph_type::NodeMap<int> level;
+    typename graph_type::NodeMap<T> excess;
+    //node_property_vector<graph_type, int> level;
+    //node_property_vector<graph_type, T> excess;
     
     //Number of nodes on each level
@@ -60 +79 @@
     
     //For the FIFO implementation
-    list<node_iterator> fifo_nodes;
+    list<NodeIt> fifo_nodes;
     //For 'highest label' implementation
     int highest_active;
     //int second_highest_active;
-    vector< list<node_iterator> > active_nodes;
+    vector< list<NodeIt> > active_nodes;
 
   public:
@@ -71 +90 @@
     preflow_push(
                       graph_type& _G, 
-                      node_iterator _s, 
-                      node_iterator _t, 
-                      edge_property_vector<graph_type, T>& _capacity)
+                      NodeIt _s, 
+                      NodeIt _t, 
+                      typename graph_type::EdgeMap<T> & _capacity)
       : G(_G), s(_s), t(_t), 
         capacity(_capacity), 
         preflow(_G),
         //Counting the number of nodes
-        number_of_nodes(number_of(G.first_node())),
+        //number_of_nodes(count(G.first<EachNodeIt>())),
+        number_of_nodes(G.nodeNum()),
+
         level(_G),
         excess(_G)//,
@@ -107 +128 @@
     T run();
   
-    edge_property_vector<graph_type, T> getmaxflow(){
+    typename graph_type::EdgeMap<T>  getmaxflow(){
       return preflow;
     }
@@ -115 +136 @@
     //For testing purposes only
     //Lists the node_properties
-    void write_property_vector(node_property_vector<graph_type, T> a, 
+    void write_property_vector(typename graph_type::NodeMap<T> a,
+                               //node_property_vector<graph_type, T> a, 
                                char* prop_name="property"){
-      for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
         cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl;
       }
@@ -124 +146 @@
 
     //Modifies the excess of the node and makes sufficient changes
-    void modify_excess(const node_iterator& a ,T v){
+    void modify_excess(const NodeIt& a ,T v){
         T old_value=excess.get(a);
-        excess.put(a,old_value+v);
+        excess.set(a,old_value+v);
     }
   
@@ -133 +155 @@
     //and maintain the excess on the head and tail
     //Here we do not check whether this is possible or not
-    void modify_preflow(edge_iterator j, const T& v){
+    void modify_preflow(EdgeIt j, const T& v){
 
       //Auxiliary variable
@@ -140 +162 @@
       //Modifiyng the edge
       old_value=preflow.get(j);
-      preflow.put(j,old_value+v);
+      preflow.set(j,old_value+v);
 
 
@@ -153 +175 @@
     //Gives the active node to work with 
     //(depending on the implementation to be used)
-    node_iterator get_active_node(){
+    NodeIt get_active_node(){
       //cout<<highest_active<<endl;
 
@@ -165 +187 @@
 
         if( highest_active>=0) {
-          node_iterator a=active_nodes[highest_active].front();
+          NodeIt a=active_nodes[highest_active].front();
           active_nodes[highest_active].pop_front();
           return a;
         }
         else {
-          return node_iterator();
+          return NodeIt();
         }
         
@@ -179 +201 @@
 
         if( ! fifo_nodes.empty() ) {
-          node_iterator a=fifo_nodes.front();
+          NodeIt a=fifo_nodes.front();
           fifo_nodes.pop_front();
           return a;
         }
         else {
-          return node_iterator();
+          return NodeIt();
         }
         break;
@@ -190 +212 @@
       }
       //
-      return node_iterator();
+      return NodeIt();
     }
 
     //Puts node 'a' among the active nodes
-    void make_active(const node_iterator& a){
+    void make_active(const NodeIt& a){
       //s and t never become active
       if (a!=s && a!= t){
@@ -216 +238 @@
 
     //Changes the level of node a and make sufficent changes
-    void change_level_to(node_iterator a, int new_value){
+    void change_level_to(NodeIt a, int new_value){
       int seged = level.get(a);
-      level.put(a,new_value);
+      level.set(a,new_value);
       --num_of_nodes_on_level[seged];
       ++num_of_nodes_on_level[new_value];
@@ -224 +246 @@
 
     //Collection of things useful (or necessary) to do before running
+
     void preprocess(){
 
@@ -232 +255 @@
       //Setting starting preflow, level and excess values to zero
       //This can be important, if the algorithm is run more then once
-      for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
-        level.put(i,0);
-        excess.put(i,0);
-        for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) 
-          preflow.put(j, 0);
+      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
+        level.set(i,0);
+        excess.set(i,0);
+        for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j) 
+          preflow.set(j, 0);
       }
       num_of_nodes_on_level[0]=number_of_nodes;
@@ -252 +275 @@
       rev_bfs.run();
       //write_property_vector(rev_bfs.dist,"rev_bfs");
-      for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
         change_level_to(i,rev_bfs.dist(i));
         //level.put(i,rev_bfs.dist.get(i));
@@ -267 +290 @@
       
       //we push as much preflow from s as possible to start with
-      for(out_edge_iterator j=G.first_out_edge(s); j.valid(); ++j){ 
+      for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){ 
         modify_preflow(j,capacity.get(j) );
         make_active(G.head(j));
@@ -281 +304 @@
     //If the preflow is less than the capacity on the given edge
     //then it is an edge in the residual graph
-    bool is_admissible_forward_edge(out_edge_iterator j, int& new_level){
+    bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){
       if (capacity.get(j)>preflow.get(j)){
         if(level.get(G.tail(j))==level.get(G.head(j))+1){
@@ -296 +319 @@
     //If the preflow is greater than 0 on the given edge
     //then the edge reversd is an edge in the residual graph
-    bool is_admissible_backward_edge(in_edge_iterator j, int& new_level){
+    bool is_admissible_backward_edge(InEdgeIt j, int& new_level){
       if (0<preflow.get(j)){
         if(level.get(G.tail(j))==level.get(G.head(j))-1){
@@ -319 +342 @@
     
     T e,v;
-    node_iterator a;
+    NodeIt a;
     while (a=get_active_node(), a.valid()){
       //cout<<G.id(a)<<endl;
@@ -325 +348 @@
       //write_property_vector(level,"level");
 
-      //Initial value for the new level for the active node we are dealing with
-      int new_level=2*number_of_nodes;
 
       bool go_to_next_node=false;
       e = excess.get(a);
       while (!go_to_next_node){
-        
+
+        //Initial value for the new level for the active node we are dealing with
+        int new_level=2*number_of_nodes;
+        //write_property_vector(excess,"excess");
+        //write_property_vector(level,"level");
+        //cout<<G.id(a)<<endl;
         //Out edges from node a
         {
-          out_edge_iterator j=G.first_out_edge(a);
+          OutEdgeIt j=G.template first<OutEdgeIt>(a);
           while (j.valid() && e){
 
@@ -351 +377 @@
         //In edges to node a
         {
-          in_edge_iterator j=G.first_in_edge(a);
+          InEdgeIt j=G.template first<InEdgeIt>(a);
           while (j.valid() && e){
             if (is_admissible_backward_edge(j,new_level)){
@@ -373 +399 @@
         }
         else{//If there is still excess in node a
-
+          
+          //change_level_to(a,new_level+1);
+          
           //Level remains empty
           if (num_of_nodes_on_level[level.get(a)]==1){
@@ -383 +411 @@
             //increase_level(a);
           }
-
+