lemon-0.x: src/work/marci_max_flow.hh@d33813af6e50

     1 #ifndef MARCI_MAX_FLOW_HH

     2 #define MARCI_MAX_FLOW_HH

     4 #include <algorithm>

     6 #include <marci_graph_traits.hh>

     7 #include <marci_property_vector.hh>

     8 #include <marci_bfs.hh>

    10 namespace marci {

    12   template<typename graph_type, typename T>

    13   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;

    19     graph_type& G;

    20     edge_property_vector<graph_type, T>& flow;

    21     edge_property_vector<graph_type, T>& capacity;

    22   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) { }

    25     class res_edge_it {

    26       friend class res_graph_type<graph_type, T>;

    27     protected:

    28       res_graph_type<graph_type, T>* resG;

    29       sym_edge_iterator sym;

    30     public:

    31       res_edge_it() { }

    32       //bool is_free() {

    33       //if (resG->G.a_node(sym)==resG->G.tail(sym)) {

    34       //  return (resG->flow.get(sym)<resG->capacity.get(sym));

    35       //} else {

    36       //  return (resG->flow.get(sym)>0);

    37       //}

    38       //}

    39       T free() {

    40 	if (resG->G.a_node(sym)==resG->G.tail(sym)) {

    41 	  return (resG->capacity.get(sym)-resG->flow.get(sym));

    42 	} else {

    43 	  return (resG->flow.get(sym));

    44 	}

    45       }

    46       bool is_valid() { return sym.is_valid(); }

    47       void augment(T a) {

    48 	if (resG->G.a_node(sym)==resG->G.tail(sym)) {

    49 	  resG->flow.put(sym, resG->flow.get(sym)+a);

    50 	} else {

    51 	  resG->flow.put(sym, resG->flow.get(sym)-a);

    52 	}

    53       }

    54     };

    56     class res_out_edge_it : public res_edge_it {

    57     public:

    58       res_out_edge_it() { }

    59       res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {

    60       	resG=&_resG;

    61 	sym=resG->G.first_sym_edge(v);

    62 	while( sym.is_valid() && !(free()>0) ) { ++sym; }

    63       }

    64       res_out_edge_it& operator++() {

    65 	++sym;

    66 	while( sym.is_valid() && !(free()>0) ) { ++sym; }

    67 	return *this;

    68       }

    69     };

    71     res_out_edge_it first_out_edge(const node_iterator& v) {

    72       return res_out_edge_it(*this, v);

    73     }

    75     each_node_iterator first_node() {

    76       return G.first_node();

    77     }

    79     node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); }

    80     node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); }

    82     int id(const node_iterator& v) { return G.id(v); }

    84     node_iterator invalid_node() { return G.invalid_node(); }

    85     res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }

    87   };

    89   template <typename graph_type, typename T>

    90   struct graph_traits< res_graph_type<graph_type, T> > {

    91     typedef typename graph_traits<graph_type>::node_iterator node_iterator;

    92     typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator;

    93     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;

    94     typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator;

    95   };

    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   };

   131   template <typename graph_type, typename T>

   132   struct max_flow_type {

   134     typedef typename graph_traits<graph_type>::node_iterator node_iterator;

   135     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;

   136     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;

   137     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;

   138     typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;

   140     graph_type& G;

   141     node_iterator s;

   142     node_iterator t;

   143     edge_property_vector<graph_type, T> flow;

   144     edge_property_vector<graph_type, T>& capacity;

   146     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) {

   147       for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)

   148 	for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j)

   149 	  flow.put(j, 0);

   150     }

   151     void run() {

   152       typedef res_graph_type<graph_type, T> aug_graph_type;

   153       aug_graph_type res_graph(G, flow, capacity);

   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));

   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);

   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());

   168       typedef node_property_vector<aug_graph_type, int> free_type;

   169       free_type free(res_graph);

   171       typedef flow_visitor<aug_graph_type, pred_type, free_type> visitor_type;

   172       visitor_type vis(res_graph, pred, free);

   174       bfs_iterator< aug_graph_type, reached_type, visitor_type >

   175 	res_bfs(res_graph, bfs_queue, reached, vis);

   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;

   184       //char c;

   185       bool augment;

   186       do {

   187 	augment=false;

   189 	while (!bfs_queue.empty()) { bfs_queue.pop(); }

   190 	bfs_queue.push(res_graph.first_out_edge(s));

   192 	for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }

   193 	reached.put(s, true);

   195 	//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;

   199 	  if (res_graph.head(res_bfs)==t) break;

   200 	  //res_bfs.next();

   201 	  ++res_bfs;

   202 	}

   203 	//for (; std::cin>>c && !res_bfs.finished() && res_graph.head(res_bfs.current())!=t; res_bfs.next()) { res_bfs.process(); }

   204 	if (reached.get(t)) {

   205 	  augment=true;

   206 	  node_iterator n=t;

   207 	  T augment_value=free.get(t);

   208 	  std::cout<<"augmentation: ";

   209 	  while (pred.get(n).is_valid()) {

   210 	    graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);

   211 	    e.augment(augment_value);

   212 	    std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";

   213 	    n=res_graph.tail(e);

   214 	  }

   215 	  std::cout<<std::endl;

   216 	}

   218 	std::cout << "max flow:"<< std::endl;

   219 	for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {

   220 	  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";

   221 	}

   222 	std::cout<<std::endl;

   224       } while (augment);

   225     }

   226   };

   228 } // namespace marci

   230 #endif //MARCI_MAX_FLOW_HH

author	marci
	Mon, 12 Jan 2004 11:49:56 +0000
changeset 13	d33813af6e50
child 14	99014d576aed
permissions	-rw-r--r--