COIN-OR::LEMON - Graph Library

Changeset 14:99014d576aed in lemon-0.x


Ignore:
Timestamp:
01/12/04 12:50:52 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@27
Message:

reimplemented max_flow algorithm class with bfs_iterator1

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci_max_flow.hh

    r9 r14  
    9595  };
    9696
    97   template <typename graph_type, typename pred_type, typename free_type>
    98   struct flow_visitor {
    99     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    100     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    101     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    102     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
    103     graph_type& G;
    104     pred_type& pred;
    105     free_type& free;
    106     flow_visitor(graph_type& _G, pred_type& _pred, free_type& _free) : G(_G), pred(_pred), free(_free) { }
    107     void at_previously_reached(out_edge_iterator& e) {
    108       //node_iterator v=G.tail(e);
    109       //node_iterator w=G.head(e);
    110       //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is already reached";
    111       //std::cout<<std::endl;
    112    }
    113     void at_newly_reached(out_edge_iterator& e) {
    114       node_iterator v=G.tail(e);
    115       node_iterator w=G.head(e);
    116       //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
    117       pred.put(w, e);
    118       if (pred.get(v).is_valid()) {
    119         free.put(w, std::min(free.get(v), e.free()));
    120         //std::cout <<" nem elso csucs: ";
    121         //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
    122       } else {
    123         free.put(w, e.free());
    124         //std::cout <<" elso csucs: ";
    125         //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
    126       }
    127       //std::cout<<std::endl;
    128     }
    129   };
    130 
    13197  template <typename graph_type, typename T>
    13298  struct max_flow_type {
     
    153119      aug_graph_type res_graph(G, flow, capacity);
    154120
    155       typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
    156       bfs_queue_type bfs_queue;
    157       //bfs_queue.push(res_graph.first_out_edge(s));
    158 
    159       typedef node_property_vector<aug_graph_type, bool> reached_type;
    160       //reached_type reached(res_graph, false);
    161       reached_type reached(res_graph);
    162       //reached.put(s, true);
    163 
    164       typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
    165       pred_type pred(res_graph);
    166       pred.put(s, res_graph.invalid_edge());
    167      
    168       typedef node_property_vector<aug_graph_type, int> free_type;
    169       free_type free(res_graph);
    170 
    171       typedef flow_visitor<aug_graph_type, pred_type, free_type> visitor_type;
    172       visitor_type vis(res_graph, pred, free);
    173      
    174       bfs_iterator< aug_graph_type, reached_type, visitor_type >
    175         res_bfs(res_graph, bfs_queue, reached, vis);
    176 
    177       //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) {
    178       //for(graph_traits<aug_graph_type>::out_edge_iterator j=res_graph.first_out_edge(i); j.is_valid(); ++j) {
    179       //  std::cout<<"("<<res_graph.tail(j)<< "->"<<res_graph.head(j)<<") ";
    180       //}
    181       //}
    182       //std::cout<<std::endl;
    183 
    184       //char c;
    185121      bool augment;
    186122      do {
    187123        augment=false;
    188        
    189         while (!bfs_queue.empty()) { bfs_queue.pop(); }
     124
     125        typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
     126        bfs_queue_type bfs_queue;
    190127        bfs_queue.push(res_graph.first_out_edge(s));
    191        
    192         for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
     128
     129        typedef node_property_vector<aug_graph_type, bool> reached_type;
     130        //reached_type reached(res_graph);
     131        //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
     132        reached_type reached(res_graph, false);
    193133        reached.put(s, true);
    194134       
     135        bfs_iterator1< aug_graph_type, reached_type >
     136        res_bfs(res_graph, bfs_queue, reached);
     137
     138        typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
     139        pred_type pred(res_graph);
     140        pred.put(s, res_graph.invalid_edge());
     141
     142        typedef node_property_vector<aug_graph_type, int> free_type;
     143        free_type free(res_graph);
     144       
    195145        //searching for augmenting path
    196         while ( /*std::cin>>c &&*/ res_bfs.is_valid() ) {
    197           res_bfs.process();
    198           //if (res_graph.head(graph_traits<aug_graph_type>::out_edge_iterator(res_bfs))==t) break;
     146        while ( res_bfs.is_valid() ) {
     147          //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
     148          if (res_bfs.is_newly_reached()) {
     149            graph_traits<aug_graph_type>::edge_iterator e;
     150            e=res_bfs;
     151            node_iterator v=res_graph.tail(e);
     152            node_iterator w=res_graph.head(e);
     153            //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
     154            pred.put(w, e);
     155            if (pred.get(v).is_valid()) {
     156              free.put(w, std::min(free.get(v), e.free()));
     157              //std::cout <<" nem elso csucs: ";
     158              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
     159            } else {
     160              free.put(w, e.free());
     161              //std::cout <<" elso csucs: ";
     162              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
     163            }
     164            //std::cout<<std::endl;
     165          }
     166       
    199167          if (res_graph.head(res_bfs)==t) break;
    200           //res_bfs.next();
    201168          ++res_bfs;
    202169        }
    203         //for (; std::cin>>c && !res_bfs.finished() && res_graph.head(res_bfs.current())!=t; res_bfs.next()) { res_bfs.process(); }
    204170        if (reached.get(t)) {
    205171          augment=true;
     
    216182        }
    217183
    218         std::cout << "max flow:"<< std::endl;
     184        std::cout << "actual flow: "<< std::endl;
    219185        for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {
    220186          std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
Note: See TracChangeset for help on using the changeset viewer.