COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

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


Ignore:
Timestamp:
02/16/04 16:57:59 (21 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.

Location:
src/work/athos
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed

  • src/work/athos/pf_demo.cc

    r36 r77  
    33#include <string>
    44
    5 #include "marci_list_graph.hh"
     5#include "list_graph.hh"
    66#include "marci_graph_traits.hh"
    7 #include "marci_property_vector.hh"
     7//#include "marci_property_vector.hh"
    88#include "preflow_push.hh"
    99
    … …  
    1313int main (int, char*[])
    1414{
    15   typedef graph_traits<list_graph>::node_iterator node_iterator;
    16   typedef graph_traits<list_graph>::edge_iterator edge_iterator;
    17   typedef graph_traits<list_graph>::each_node_iterator each_node_iterator;
    18   typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator;
    19   typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator;
    20   typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;
    21   typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;
    2215
    23   list_graph flow_test;
    24  
    2516 
     17  typedef ListGraph::NodeIt NodeIt;
     18  typedef ListGraph::EdgeIt EdgeIt;
     19  /*
     20  typedef ListGraph::EachNodeIt EachNodeIt;
     21  typedef ListGraph::EachEdgeIt EachEdgeIt;
     22  typedef ListGraph::OutEdgeIt OutEdgeIt;
     23  typedef ListGraph::InEdgeIt InEdgeIt;
     24  typedef ListGraph::SymEdgeIt SymEdgeIt;
     25  */
     26 
     27  //Marci példája
     28  ListGraph flowG;
     29
     30  NodeIt s=flowG.addNode();
     31  NodeIt v1=flowG.addNode();
     32  NodeIt v2=flowG.addNode();
     33  NodeIt v3=flowG.addNode();
     34  NodeIt v4=flowG.addNode();
     35  NodeIt t=flowG.addNode();
     36 
     37
     38  EdgeIt s_v1=flowG.addEdge(s, v1);
     39  EdgeIt s_v2=flowG.addEdge(s, v2);
     40  EdgeIt v1_v2=flowG.addEdge(v1, v2);
     41  EdgeIt v2_v1=flowG.addEdge(v2, v1);
     42  EdgeIt v1_v3=flowG.addEdge(v1, v3);
     43  EdgeIt v3_v2=flowG.addEdge(v3, v2);
     44  EdgeIt v2_v4=flowG.addEdge(v2, v4);
     45  EdgeIt v4_v3=flowG.addEdge(v4, v3);
     46  EdgeIt v3_t=flowG.addEdge(v3, t);
     47  EdgeIt v4_t=flowG.addEdge(v4, t);
     48
     49  ListGraph::EdgeMap<int> cap(flowG);
     50
     51  cap.set(s_v1, 16);
     52  cap.set(s_v2, 13);
     53  cap.set(v1_v2, 10);
     54  cap.set(v2_v1, 4);
     55  cap.set(v1_v3, 12);
     56  cap.set(v3_v2, 9);
     57  cap.set(v2_v4, 14);
     58  cap.set(v4_v3, 7);
     59  cap.set(v3_t, 20);
     60  cap.set(v4_t, 4);
     61
     62
     63
     64
     65
     66
     67
     68  /*
    2669  //Ahuja könyv példája
    2770  node_iterator s=flow_test.add_node();
    28   node_iterator v2=flow_test.add_node();
    29   node_iterator v3=flow_test.add_node();
    30   node_iterator v4=flow_test.add_node();
    31   node_iterator v5=flow_test.add_node();
    32   node_iterator t=flow_test.add_node();
     71  NodeIt v2=flow_test.add_node();
     72  NodeIt v3=flow_test.add_node();
     73  NodeIt v4=flow_test.add_node();
     74  NodeIt v5=flow_test.add_node();
     75  NodeIt t=flow_test.add_node();
    3376 
    3477  node_property_vector<list_graph, std::string> node_name(flow_test);
    … …  
    71114  //cap.put(t_s, 20);
    72115
    73  
    74   /*
    75   //Marci példája
    76   node_iterator s=flow_test.add_node();
    77   node_iterator v1=flow_test.add_node();
    78   node_iterator v2=flow_test.add_node();
    79   node_iterator v3=flow_test.add_node();
    80   node_iterator v4=flow_test.add_node();
    81   node_iterator t=flow_test.add_node();
    82  
    83   node_property_vector<list_graph, std::string> node_name(flow_test);
    84   node_name.put(s, "s");
    85   node_name.put(v1, "v1");
    86   node_name.put(v2, "v2");
    87   node_name.put(v3, "v3");
    88   node_name.put(v4, "v4");
    89   node_name.put(t, "t");
     116  */
    90117
    91   edge_iterator s_v1=flow_test.add_edge(s, v1);
    92   edge_iterator s_v2=flow_test.add_edge(s, v2);
    93   edge_iterator v1_v2=flow_test.add_edge(v1, v2);
    94   edge_iterator v2_v1=flow_test.add_edge(v2, v1);
    95   edge_iterator v1_v3=flow_test.add_edge(v1, v3);
    96   edge_iterator v3_v2=flow_test.add_edge(v3, v2);
    97   edge_iterator v2_v4=flow_test.add_edge(v2, v4);
    98   edge_iterator v4_v3=flow_test.add_edge(v4, v3);
    99   edge_iterator v3_t=flow_test.add_edge(v3, t);
    100   edge_iterator v4_t=flow_test.add_edge(v4, t);
    101  
    102   edge_property_vector<list_graph, int> cap(flow_test); 
    103   cap.put(s_v1, 16);
    104   cap.put(s_v2, 13);
    105   cap.put(v1_v2, 10);
    106   cap.put(v2_v1, 4);
    107   cap.put(v1_v3, 12);
    108   cap.put(v3_v2, 9);
    109   cap.put(v2_v4, 14);
    110   cap.put(v4_v3, 7);
    111   cap.put(v3_t, 20);
    112   cap.put(v4_t, 4);
    113   */
     118
     119
    114120  /*Egyszerû példa
    115   node_iterator s=flow_test.add_node();
    116   node_iterator v1=flow_test.add_node();
    117   node_iterator v2=flow_test.add_node();
    118   node_iterator t=flow_test.add_node();
     121  NodeIt s=flow_test.add_node();
     122  NodeIt v1=flow_test.add_node();
     123  NodeIt v2=flow_test.add_node();
     124  NodeIt t=flow_test.add_node();
    119125 
    120126  node_property_vector<list_graph, std::string> node_name(flow_test);
    … …  
    136142
    137143  std::cout << "preflow-push algorithm test..." << std::endl;
     144
     145  /*
    138146  std::cout << "on directed graph graph" << std::endl; //<< flow_test;
    139147  std::cout << "names and capacity values" << std::endl;
    140   for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
     148  for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) {
    141149    std::cout << node_name.get(i) << ": ";
    142150    std::cout << "out edges: ";
    … …  
    148156    std::cout << std::endl;
    149157  }
    150 
     158  */
    151159 
    152   //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
     160  //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) {
    153161  //  std::cout << i << " ";
    154162  //}
    155163 
    156   preflow_push<list_graph, int> preflow_push_test(flow_test, s, t, cap);
     164  preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap);
    157165  cout << preflow_push_test.run()<<endl;
    158166

  • 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.