COIN-OR::LEMON - Graph Library

Changeset 19:3151a1026db9 in lemon-0.x for src/work/marci_max_flow.hh


Ignore:
Timestamp:
01/20/04 18:39:13 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@32
Message:

* empty log message *

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci_max_flow.hh

    r17 r19  
    44#include <algorithm>
    55
    6 #include <marci_graph_traits.hh>
    76#include <marci_property_vector.hh>
    87#include <marci_bfs.hh>
     
    1211  template<typename graph_type, typename T>
    1312  class res_graph_type {
    14     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    15     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    16     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    17     typedef typename graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
    18 
     13    typedef typename graph_type::node_iterator node_iterator;
     14    typedef typename graph_type::each_node_iterator each_node_iterator;
     15    typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator;
    1916    graph_type& G;
    2017    edge_property_vector<graph_type, T>& flow;
     
    2320    res_graph_type(graph_type& _G, edge_property_vector<graph_type, T>& _flow, edge_property_vector<graph_type, T>& _capacity) : G(_G), flow(_flow), capacity(_capacity) { }
    2421
    25     class res_edge_it {
     22    class edge_iterator {
    2623      friend class res_graph_type<graph_type, T>;
    2724    protected:
    2825      res_graph_type<graph_type, T>* resG;
    29       sym_edge_iterator sym;
     26      old_sym_edge_iterator sym;
    3027    public:
    31       res_edge_it() { }
     28      edge_iterator() { }
    3229      //bool is_free() { 
    3330      //if (resG->G.a_node(sym)==resG->G.tail(sym)) {
     
    4441        }
    4542      }
    46       bool is_valid() { return sym.is_valid(); }
     43      bool valid() { return sym.valid(); }
    4744      void make_invalid() { sym.make_invalid(); }
    4845      void augment(T a) {
     
    5552    };
    5653
    57     class res_out_edge_it : public res_edge_it {
     54    class out_edge_iterator : public edge_iterator {
    5855    public:
    59       res_out_edge_it() { }
    60       res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
     56      out_edge_iterator() { }
     57      out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
    6158        resG=&_resG;
    6259        sym=resG->G.first_sym_edge(v);
    63         while( sym.is_valid() && !(free()>0) ) { ++sym; }
     60        while( sym.valid() && !(free()>0) ) { ++sym; }
    6461      }
    65       res_out_edge_it& operator++() {
     62      out_edge_iterator& operator++() {
    6663        ++sym;
    67         while( sym.is_valid() && !(free()>0) ) { ++sym; }
     64        while( sym.valid() && !(free()>0) ) { ++sym; }
    6865        return *this;
    6966      }
    7067    };
    7168
    72     res_out_edge_it first_out_edge(const node_iterator& v) {
    73       return res_out_edge_it(*this, v);
     69    out_edge_iterator first_out_edge(const node_iterator& v) {
     70      return out_edge_iterator(*this, v);
    7471    }
    7572
     
    7875    }
    7976
    80     node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); }
    81     node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); }
     77    node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); }
     78    node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); }
    8279
    8380    int id(const node_iterator& v) { return G.id(v); }
    8481
    8582    //node_iterator invalid_node() { return G.invalid_node(); }
    86     //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
    87    
    88   };
    89 
    90   template <typename graph_type, typename T>
    91   struct graph_traits< res_graph_type<graph_type, T> > {
    92     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    93     typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator;
    94     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    95     typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator;
     83    //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
    9684  };
    9785
    9886  template <typename graph_type, typename T>
    9987  struct max_flow_type {
    100    
    101     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    102     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    103     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    104     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
    105     typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
    106 
     88    typedef typename graph_type::node_iterator node_iterator;
     89    typedef typename graph_type::edge_iterator edge_iterator;
     90    typedef typename graph_type::each_node_iterator each_node_iterator;
     91    typedef typename graph_type::out_edge_iterator out_edge_iterator;
     92    typedef typename graph_type::in_edge_iterator in_edge_iterator;
    10793    graph_type& G;
    10894    node_iterator s;
     
    11298
    11399    max_flow_type(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) {
    114       for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
    115         for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j)
     100      for(each_node_iterator i=G.first_node(); i.valid(); ++i)
     101        for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j)
    116102          flow.put(j, 0);
    117103    }
     
    124110        augment=false;
    125111
    126         typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
     112        typedef std::queue<aug_graph_type::out_edge_iterator> bfs_queue_type;
    127113        bfs_queue_type bfs_queue;
    128114        bfs_queue.push(res_graph.first_out_edge(s));
     
    135121        res_bfs(res_graph, bfs_queue, reached);
    136122
    137         typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
     123        typedef node_property_vector<aug_graph_type, aug_graph_type::edge_iterator> pred_type;
    138124        pred_type pred(res_graph);
    139         graph_traits<aug_graph_type>::edge_iterator a;
     125        aug_graph_type::edge_iterator a;
    140126        a.make_invalid();
    141127        pred.put(s, a);
     
    145131       
    146132        //searching for augmenting path
    147         while ( res_bfs.is_valid() ) {
     133        while ( res_bfs.valid() ) {
    148134          //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
    149           if (res_bfs.is_newly_reached()) {
    150             graph_traits<aug_graph_type>::edge_iterator e;
     135          if (res_bfs.newly_reached()) {
     136            aug_graph_type::edge_iterator e;
    151137            e=res_bfs;
    152138            node_iterator v=res_graph.tail(e);
     
    154140            //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
    155141            pred.put(w, e);
    156             if (pred.get(v).is_valid()) {
     142            if (pred.get(v).valid()) {
    157143              free.put(w, std::min(free.get(v), e.free()));
    158144              //std::cout <<" nem elso csucs: ";
     
    174160          T augment_value=free.get(t);
    175161          std::cout<<"augmentation: ";
    176           while (pred.get(n).is_valid()) {
    177             graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);
     162          while (pred.get(n).valid()) {
     163            aug_graph_type::edge_iterator e=pred.get(n);
    178164            e.augment(augment_value);
    179165            std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
     
    184170
    185171        std::cout << "actual flow: "<< std::endl;
    186         for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {
     172        for(typename graph_type::each_edge_iterator e=G.first_edge(); e.valid(); ++e) {
    187173          std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    188174        }
Note: See TracChangeset for help on using the changeset viewer.