Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci_max_flow.hh
changeset 99 f26897fb91fd
parent 17 8b29d935f1a6
child 107 8d62f0072ff0
equal deleted inserted replaced
2:4e50ef17d83b 3:f091a2e92fe6 
     1 #ifndef MARCI_MAX_FLOW_HH
 
     1 #ifndef MARCI_MAX_FLOW_HH
 
     2 #define MARCI_MAX_FLOW_HH
 
     2 #define MARCI_MAX_FLOW_HH
 
     3 
     3 
     4 #include <algorithm>
 
     4 #include <algorithm>
 
     5 
     5 
     6 #include <marci_graph_traits.hh>
 
       
     7 #include <marci_property_vector.hh>
 
     6 #include <marci_property_vector.hh>
 
     8 #include <marci_bfs.hh>
 
     7 #include <marci_bfs.hh>
 
     9 
     8 
    10 namespace marci {
 
     9 namespace marci {
 
    11 
    10 
    12   template<typename graph_type, typename T>
 
    11   template<typename graph_type, typename T>
 
    13   class res_graph_type { 
    12   class res_graph_type { 
    14     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
 
    13     typedef typename graph_type::node_iterator node_iterator;
 
    15     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
 
    14     typedef typename graph_type::each_node_iterator each_node_iterator;
 
    16     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
 
    15     typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator;
 
    17     typedef typename graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
 
       
    18 
       
    19     graph_type& G;
 
    16     graph_type& G;
 
    20     edge_property_vector<graph_type, T>& flow;
 
    17     edge_property_vector<graph_type, T>& flow;
 
    21     edge_property_vector<graph_type, T>& capacity;
 
    18     edge_property_vector<graph_type, T>& capacity;
 
    22   public:
 
    19   public:
 
    23     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) { }
 
    20     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) { }
 
    24 
    21 
    25     class res_edge_it {
 
    22     class edge_iterator {
 
    26       friend class res_graph_type<graph_type, T>;
 
    23       friend class res_graph_type<graph_type, T>;
 
    27     protected:
 
    24     protected:
 
    28       res_graph_type<graph_type, T>* resG;
 
    25       res_graph_type<graph_type, T>* resG;
 
    29       sym_edge_iterator sym;
 
    26       old_sym_edge_iterator sym;
 
    30     public:
 
    27     public:
 
    31       res_edge_it() { }
 
    28       edge_iterator() { }
 
    32       //bool is_free() {  
    29       //bool is_free() {  
    33       //if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
    30       //if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
    34       //  return (resG->flow.get(sym)<resG->capacity.get(sym)); 
    31       //  return (resG->flow.get(sym)<resG->capacity.get(sym)); 
    35       //} else { 
    32       //} else { 
    36       //  return (resG->flow.get(sym)>0); 
    33       //  return (resG->flow.get(sym)>0); 
    41 	  return (resG->capacity.get(sym)-resG->flow.get(sym)); 
    38 	  return (resG->capacity.get(sym)-resG->flow.get(sym)); 
    42 	} else { 
    39 	} else { 
    43 	  return (resG->flow.get(sym)); 
    40 	  return (resG->flow.get(sym)); 
    44 	}
 
    41 	}
 
    45       }
 
    42       }
 
    46       bool is_valid() { return sym.is_valid(); }
 
    43       bool valid() { return sym.valid(); }
 
    47       void make_invalid() { sym.make_invalid(); }
 
    44       void make_invalid() { sym.make_invalid(); }
 
    48       void augment(T a) {
 
    45       void augment(T a) {
 
    49 	if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
    46 	if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
    50 	  resG->flow.put(sym, resG->flow.get(sym)+a);
 
    47 	  resG->flow.put(sym, resG->flow.get(sym)+a);
 
    51 	} else { 
    48 	} else { 
    52 	  resG->flow.put(sym, resG->flow.get(sym)-a);
 
    49 	  resG->flow.put(sym, resG->flow.get(sym)-a);
 
    53 	}
 
    50 	}
 
    54       }
 
    51       }
 
    55     };
 
    52     };
 
    56 
    53 
    57     class res_out_edge_it : public res_edge_it {
 
    54     class out_edge_iterator : public edge_iterator {
 
    58     public:
 
    55     public:
 
    59       res_out_edge_it() { }
 
    56       out_edge_iterator() { }
 
    60       res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) { 
    57       out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) { 
    61       	resG=&_resG;
 
    58       	resG=&_resG;
 
    62 	sym=resG->G.first_sym_edge(v);
 
    59 	sym=resG->G.first_sym_edge(v);
 
    63 	while( sym.is_valid() && !(free()>0) ) { ++sym; }
 
    60 	while( sym.valid() && !(free()>0) ) { ++sym; }
 
    64       }
 
    61       }
 
    65       res_out_edge_it& operator++() { 
    62       out_edge_iterator& operator++() { 
    66 	++sym; 
    63 	++sym; 
    67 	while( sym.is_valid() && !(free()>0) ) { ++sym; }
 
    64 	while( sym.valid() && !(free()>0) ) { ++sym; }
 
    68 	return *this; 
    65 	return *this; 
    69       }
 
    66       }
 
    70     };
 
    67     };
 
    71 
    68 
    72     res_out_edge_it first_out_edge(const node_iterator& v) {
 
    69     out_edge_iterator first_out_edge(const node_iterator& v) {
 
    73       return res_out_edge_it(*this, v);
 
    70       return out_edge_iterator(*this, v);
 
    74     }
 
    71     }
 
    75 
    72 
    76     each_node_iterator first_node() {
 
    73     each_node_iterator first_node() {
 
    77       return G.first_node();
 
    74       return G.first_node();
 
    78     }
 
    75     }
 
    79 
    76 
    80     node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); }
 
    77     node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); }
 
    81     node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); }
 
    78     node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); }
 
    82 
    79 
    83     int id(const node_iterator& v) { return G.id(v); }
 
    80     int id(const node_iterator& v) { return G.id(v); }
 
    84 
    81 
    85     //node_iterator invalid_node() { return G.invalid_node(); }
 
    82     //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; }
 
    83     //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;
 
       
    96   };
 
    84   };
 
    97 
    85 
    98   template <typename graph_type, typename T>
 
    86   template <typename graph_type, typename T>
 
    99   struct max_flow_type {
 
    87   struct max_flow_type {
 
   100     
    88     typedef typename graph_type::node_iterator node_iterator;
 
   101     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
 
    89     typedef typename graph_type::edge_iterator edge_iterator;
 
   102     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
 
    90     typedef typename graph_type::each_node_iterator each_node_iterator;
 
   103     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
 
    91     typedef typename graph_type::out_edge_iterator out_edge_iterator;
 
   104     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
 
    92     typedef typename graph_type::in_edge_iterator in_edge_iterator;
 
   105     typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
 
       
   106 
       
   107     graph_type& G;
 
    93     graph_type& G;
 
   108     node_iterator s;
 
    94     node_iterator s;
 
   109     node_iterator t;
 
    95     node_iterator t;
 
   110     edge_property_vector<graph_type, T> flow;
 
    96     edge_property_vector<graph_type, T> flow;
 
   111     edge_property_vector<graph_type, T>& capacity;
 
    97     edge_property_vector<graph_type, T>& capacity;
 
   112 
    98 
   113     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) { 
    99     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) 
   100       for(each_node_iterator i=G.first_node(); i.valid(); ++i) 
   115 	for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) 
   101 	for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) 
   116 	  flow.put(j, 0);
 
   102 	  flow.put(j, 0);
 
   117     }
 
   103     }
 
   118     void run() {
 
   104     void run() {
 
   119       typedef res_graph_type<graph_type, T> aug_graph_type;
 
   105       typedef res_graph_type<graph_type, T> aug_graph_type;
 
   120       aug_graph_type res_graph(G, flow, capacity);
 
   106       aug_graph_type res_graph(G, flow, capacity);
 
   121 
   107 
   122       bool augment;
 
   108       bool augment;
 
   123       do {
 
   109       do {
 
   124 	augment=false;
 
   110 	augment=false;
 
   125 
   111 
   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;
 
   127 	bfs_queue_type bfs_queue;
 
   113 	bfs_queue_type bfs_queue;
 
   128 	bfs_queue.push(res_graph.first_out_edge(s));
 
   114 	bfs_queue.push(res_graph.first_out_edge(s));
 
   129 
   115 
   130 	typedef node_property_vector<aug_graph_type, bool> reached_type;
 
   116 	typedef node_property_vector<aug_graph_type, bool> reached_type;
 
   131 	reached_type reached(res_graph, false);
 
   117 	reached_type reached(res_graph, false);
 
   132 	reached.put(s, true); 
   118 	reached.put(s, true); 
   133 	
   119 	
   134 	bfs_iterator1< aug_graph_type, reached_type > 
   120 	bfs_iterator1< aug_graph_type, reached_type > 
   135 	res_bfs(res_graph, bfs_queue, reached);
 
   121 	res_bfs(res_graph, bfs_queue, reached);
 
   136 
   122 
   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;
 
   138 	pred_type pred(res_graph);
 
   124 	pred_type pred(res_graph);
 
   139 	graph_traits<aug_graph_type>::edge_iterator a; 
   125 	aug_graph_type::edge_iterator a; 
   140 	a.make_invalid();
 
   126 	a.make_invalid();
 
   141 	pred.put(s, a);
 
   127 	pred.put(s, a);
 
   142 
   128 
   143 	typedef node_property_vector<aug_graph_type, int> free_type;
 
   129 	typedef node_property_vector<aug_graph_type, int> free_type;
 
   144 	free_type free(res_graph);
 
   130 	free_type free(res_graph);
 
   145 	
   131 	
   146 	//searching for augmenting path
 
   132 	//searching for augmenting path
 
   147 	while ( res_bfs.is_valid() ) { 
   133 	while ( res_bfs.valid() ) { 
   148 	  //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
 
   134 	  //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()) {
 
   135 	  if (res_bfs.newly_reached()) {
 
   150 	    graph_traits<aug_graph_type>::edge_iterator e;
 
   136 	    aug_graph_type::edge_iterator e;
 
   151 	    e=res_bfs;
 
   137 	    e=res_bfs;
 
   152 	    node_iterator v=res_graph.tail(e);
 
   138 	    node_iterator v=res_graph.tail(e);
 
   153 	    node_iterator w=res_graph.head(e);
 
   139 	    node_iterator w=res_graph.head(e);
 
   154 	    //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
 
   140 	    //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
 
   155 	    pred.put(w, e);
 
   141 	    pred.put(w, e);
 
   156 	    if (pred.get(v).is_valid()) {
 
   142 	    if (pred.get(v).valid()) {
 
   157 	      free.put(w, std::min(free.get(v), e.free()));
 
   143 	      free.put(w, std::min(free.get(v), e.free()));
 
   158 	      //std::cout <<" nem elso csucs: ";
 
   144 	      //std::cout <<" nem elso csucs: ";
 
   159 	      //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
 
   145 	      //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
 
   160 	    } else {
 
   146 	    } else {
 
   161 	      free.put(w, e.free()); 
   147 	      free.put(w, e.free()); 
   171 	if (reached.get(t)) {
 
   157 	if (reached.get(t)) {
 
   172 	  augment=true;
 
   158 	  augment=true;
 
   173 	  node_iterator n=t;
 
   159 	  node_iterator n=t;
 
   174 	  T augment_value=free.get(t);
 
   160 	  T augment_value=free.get(t);
 
   175 	  std::cout<<"augmentation: ";
 
   161 	  std::cout<<"augmentation: ";
 
   176 	  while (pred.get(n).is_valid()) { 
   162 	  while (pred.get(n).valid()) { 
   177 	    graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);
 
   163 	    aug_graph_type::edge_iterator e=pred.get(n);
 
   178 	    e.augment(augment_value); 
   164 	    e.augment(augment_value); 
   179 	    std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
 
   165 	    std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
 
   180 	    n=res_graph.tail(e);
 
   166 	    n=res_graph.tail(e);
 
   181 	  }
 
   167 	  }
 
   182 	  std::cout<<std::endl;
 
   168 	  std::cout<<std::endl;
 
   183 	}
 
   169 	}
 
   184 
   170 
   185 	std::cout << "actual flow: "<< std::endl;
 
   171 	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) { 
   187 	  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
   173 	  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
   188 	}
 
   174 	}
 
   189 	std::cout<<std::endl;
 
   175 	std::cout<<std::endl;
 
   190 
   176 
   191       } while (augment);
 
   177       } while (augment);
lemon-0.x