COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
02/16/04 16:57:59 (17 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:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/preflow_push.hh

    r36 r77  
    77//#include "pf_hiba.hh"
    88//#include <marci_list_graph.hh>
    9 #include <marci_graph_traits.hh>
     9//#include <marci_graph_traits.hh>
     10
    1011#include "reverse_bfs.hh"
    1112
     
    1819
    1920    //Hasznos typedef-ek
     21    typedef typename graph_type::NodeIt NodeIt;
     22    typedef typename graph_type::EdgeIt EdgeIt;
     23    typedef typename graph_type::EachNodeIt EachNodeIt;
     24    typedef typename graph_type::EachEdgeIt EachEdgeIt;
     25    typedef typename graph_type::OutEdgeIt OutEdgeIt;
     26    typedef typename graph_type::InEdgeIt InEdgeIt;
     27    typedef typename graph_type::SymEdgeIt SymEdgeIt;
     28
     29
     30
     31    /*
    2032    typedef graph_traits<graph_type>::node_iterator node_iterator;
    21     typedef graph_traits<graph_type>::edge_iterator edge_iterator;
     33    typedef graph_traits<graph_type>::EdgeIt EdgeIt;
    2234    typedef graph_traits<graph_type>::each_node_iterator each_node_iterator;
    23     typedef graph_traits<graph_type>::each_edge_iterator each_edge_iterator;
    24     typedef graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
    25     typedef graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
    26     typedef graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
     35    typedef graph_traits<graph_type>::each_EdgeIt each_EdgeIt;
     36    typedef graph_traits<graph_type>::out_EdgeIt out_EdgeIt;
     37    typedef graph_traits<graph_type>::InEdgeIt InEdgeIt;
     38    typedef graph_traits<graph_type>::sym_EdgeIt sym_EdgeIt;
     39    */
    2740
    2841    //---------------------------------------------
     
    4457    //input
    4558    graph_type& G;
    46     node_iterator s;
    47     node_iterator t;
    48     edge_property_vector<graph_type, T> &capacity;
     59    NodeIt s;
     60    NodeIt t;
     61    typename graph_type::EdgeMap<T> &capacity;
     62    //typename graph_type::EdgeMap<T>  &capacity;
    4963    //output
    50     edge_property_vector<graph_type, T> preflow;
     64    //typename graph_type::EdgeMap<T> 
     65    typename graph_type::EdgeMap<T> preflow;
    5166    T maxflow_value;
    5267 
    5368    //auxiliary variables for computation
    5469    int number_of_nodes;
    55     node_property_vector<graph_type, int> level;
    56     node_property_vector<graph_type, T> excess;
     70   
     71   
     72    typename graph_type::NodeMap<int> level;
     73    typename graph_type::NodeMap<T> excess;
     74    //node_property_vector<graph_type, int> level;
     75    //node_property_vector<graph_type, T> excess;
    5776   
    5877    //Number of nodes on each level
     
    6079   
    6180    //For the FIFO implementation
    62     list<node_iterator> fifo_nodes;
     81    list<NodeIt> fifo_nodes;
    6382    //For 'highest label' implementation
    6483    int highest_active;
    6584    //int second_highest_active;
    66     vector< list<node_iterator> > active_nodes;
     85    vector< list<NodeIt> > active_nodes;
    6786
    6887  public:
     
    7190    preflow_push(
    7291                      graph_type& _G,
    73                       node_iterator _s,
    74                       node_iterator _t,
    75                       edge_property_vector<graph_type, T>& _capacity)
     92                      NodeIt _s,
     93                      NodeIt _t,
     94                      typename graph_type::EdgeMap<T> & _capacity)
    7695      : G(_G), s(_s), t(_t),
    7796        capacity(_capacity),
    7897        preflow(_G),
    7998        //Counting the number of nodes
    80         number_of_nodes(number_of(G.first_node())),
     99        //number_of_nodes(count(G.first<EachNodeIt>())),
     100        number_of_nodes(G.nodeNum()),
     101
    81102        level(_G),
    82103        excess(_G)//,
     
    107128    T run();
    108129 
    109     edge_property_vector<graph_type, T> getmaxflow(){
     130    typename graph_type::EdgeMap<T> getmaxflow(){
    110131      return preflow;
    111132    }
     
    115136    //For testing purposes only
    116137    //Lists the node_properties
    117     void write_property_vector(node_property_vector<graph_type, T> a,
     138    void write_property_vector(typename graph_type::NodeMap<T> a,
     139                               //node_property_vector<graph_type, T> a,
    118140                               char* prop_name="property"){
    119       for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
     141      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
    120142        cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl;
    121143      }
     
    124146
    125147    //Modifies the excess of the node and makes sufficient changes
    126     void modify_excess(const node_iterator& a ,T v){
     148    void modify_excess(const NodeIt& a ,T v){
    127149        T old_value=excess.get(a);
    128         excess.put(a,old_value+v);
     150        excess.set(a,old_value+v);
    129151    }
    130152 
     
    133155    //and maintain the excess on the head and tail
    134156    //Here we do not check whether this is possible or not
    135     void modify_preflow(edge_iterator j, const T& v){
     157    void modify_preflow(EdgeIt j, const T& v){
    136158
    137159      //Auxiliary variable
     
    140162      //Modifiyng the edge
    141163      old_value=preflow.get(j);
    142       preflow.put(j,old_value+v);
     164      preflow.set(j,old_value+v);
    143165
    144166
     
    153175    //Gives the active node to work with
    154176    //(depending on the implementation to be used)
    155     node_iterator get_active_node(){
     177    NodeIt get_active_node(){
    156178      //cout<<highest_active<<endl;
    157179
     
    165187
    166188        if( highest_active>=0) {
    167           node_iterator a=active_nodes[highest_active].front();
     189          NodeIt a=active_nodes[highest_active].front();
    168190          active_nodes[highest_active].pop_front();
    169191          return a;
    170192        }
    171193        else {
    172           return node_iterator();
     194          return NodeIt();
    173195        }
    174196       
     
    179201
    180202        if( ! fifo_nodes.empty() ) {
    181           node_iterator a=fifo_nodes.front();
     203          NodeIt a=fifo_nodes.front();
    182204          fifo_nodes.pop_front();
    183205          return a;
    184206        }
    185207        else {
    186           return node_iterator();
     208          return NodeIt();
    187209        }
    188210        break;
     
    190212      }
    191213      //
    192       return node_iterator();
     214      return NodeIt();
    193215    }
    194216
    195217    //Puts node 'a' among the active nodes
    196     void make_active(const node_iterator& a){
     218    void make_active(const NodeIt& a){
    197219      //s and t never become active
    198220      if (a!=s && a!= t){
     
    216238
    217239    //Changes the level of node a and make sufficent changes
    218     void change_level_to(node_iterator a, int new_value){
     240    void change_level_to(NodeIt a, int new_value){
    219241      int seged = level.get(a);
    220       level.put(a,new_value);
     242      level.set(a,new_value);
    221243      --num_of_nodes_on_level[seged];
    222244      ++num_of_nodes_on_level[new_value];
     
    224246
    225247    //Collection of things useful (or necessary) to do before running
     248
    226249    void preprocess(){
    227250
     
    232255      //Setting starting preflow, level and excess values to zero
    233256      //This can be important, if the algorithm is run more then once
    234       for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
    235         level.put(i,0);
    236         excess.put(i,0);
    237         for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j)
    238           preflow.put(j, 0);
     257      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
     258        level.set(i,0);
     259        excess.set(i,0);
     260        for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j)
     261          preflow.set(j, 0);
    239262      }
    240263      num_of_nodes_on_level[0]=number_of_nodes;
     
    252275      rev_bfs.run();
    253276      //write_property_vector(rev_bfs.dist,"rev_bfs");
    254       for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
     277      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
    255278        change_level_to(i,rev_bfs.dist(i));
    256279        //level.put(i,rev_bfs.dist.get(i));
     
    267290     
    268291      //we push as much preflow from s as possible to start with
    269       for(out_edge_iterator j=G.first_out_edge(s); j.valid(); ++j){
     292      for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){
    270293        modify_preflow(j,capacity.get(j) );
    271294        make_active(G.head(j));
     
    281304    //If the preflow is less than the capacity on the given edge
    282305    //then it is an edge in the residual graph
    283     bool is_admissible_forward_edge(out_edge_iterator j, int& new_level){
     306    bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){
    284307      if (capacity.get(j)>preflow.get(j)){
    285308        if(level.get(G.tail(j))==level.get(G.head(j))+1){
     
    296319    //If the preflow is greater than 0 on the given edge
    297320    //then the edge reversd is an edge in the residual graph
    298     bool is_admissible_backward_edge(in_edge_iterator j, int& new_level){
     321    bool is_admissible_backward_edge(InEdgeIt j, int& new_level){
    299322      if (0<preflow.get(j)){
    300323        if(level.get(G.tail(j))==level.get(G.head(j))-1){
     
    319342   
    320343    T e,v;
    321     node_iterator a;
     344    NodeIt a;
    322345    while (a=get_active_node(), a.valid()){
    323346      //cout<<G.id(a)<<endl;
     
    325348      //write_property_vector(level,"level");
    326349
    327       //Initial value for the new level for the active node we are dealing with
    328       int new_level=2*number_of_nodes;
    329350
    330351      bool go_to_next_node=false;
    331352      e = excess.get(a);
    332353      while (!go_to_next_node){
    333        
     354
     355        //Initial value for the new level for the active node we are dealing with
     356        int new_level=2*number_of_nodes;
     357        //write_property_vector(excess,"excess");
     358        //write_property_vector(level,"level");
     359        //cout<<G.id(a)<<endl;
    334360        //Out edges from node a
    335361        {
    336           out_edge_iterator j=G.first_out_edge(a);
     362          OutEdgeIt j=G.template first<OutEdgeIt>(a);
    337363          while (j.valid() && e){
    338364
     
    351377        //In edges to node a
    352378        {
    353           in_edge_iterator j=G.first_in_edge(a);
     379          InEdgeIt j=G.template first<InEdgeIt>(a);
    354380          while (j.valid() && e){
    355381            if (is_admissible_backward_edge(j,new_level)){
     
    373399        }
    374400        else{//If there is still excess in node a
    375 
     401         
     402          //change_level_to(a,new_level+1);
     403         
    376404          //Level remains empty
    377405          if (num_of_nodes_on_level[level.get(a)]==1){
     
    383411            //increase_level(a);
    384412          }
    385 
     413         
    386414   
    387415         
Note: See TracChangeset for help on using the changeset viewer.