source: lemon-0.x/src/work/marci_max_flow.hh @ 15:e41c71268807

#ifndef MARCI_MAX_FLOW_HH
#define MARCI_MAX_FLOW_HH

#include <algorithm>

#include <marci_graph_traits.hh>
#include <marci_property_vector.hh>
#include <marci_bfs.hh>

namespace marci {

  template<typename graph_type, typename T>
  class res_graph_type { 
    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    typedef typename graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;

    graph_type& G;
    edge_property_vector<graph_type, T>& flow;
    edge_property_vector<graph_type, T>& capacity;
  public:
    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) { }

    class res_edge_it {
      friend class res_graph_type<graph_type, T>;
    protected:
      res_graph_type<graph_type, T>* resG;
      sym_edge_iterator sym;
    public:
      res_edge_it() { }
      //bool is_free() {  
      //if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
      //  return (resG->flow.get(sym)<resG->capacity.get(sym)); 
      //} else { 
      //  return (resG->flow.get(sym)>0); 
      //}
      //}
      T free() { 
        if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
          return (resG->capacity.get(sym)-resG->flow.get(sym)); 
        } else { 
          return (resG->flow.get(sym)); 
        }
      }
      bool is_valid() { return sym.is_valid(); }
      void augment(T a) {
        if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
          resG->flow.put(sym, resG->flow.get(sym)+a);
        } else { 
          resG->flow.put(sym, resG->flow.get(sym)-a);
        }
      }
    };

    class res_out_edge_it : public res_edge_it {
    public:
      res_out_edge_it() { }
      res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) { 
        resG=&_resG;
        sym=resG->G.first_sym_edge(v);
        while( sym.is_valid() && !(free()>0) ) { ++sym; }
      }
      res_out_edge_it& operator++() { 
        ++sym; 
        while( sym.is_valid() && !(free()>0) ) { ++sym; }
        return *this; 
      }
    };

    res_out_edge_it first_out_edge(const node_iterator& v) {
      return res_out_edge_it(*this, v);
    }

    each_node_iterator first_node() {
      return G.first_node();
    }

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

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

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

  template <typename graph_type, typename T>
  struct graph_traits< res_graph_type<graph_type, T> > {
    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator;
    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator;
  };

  template <typename graph_type, typename T>
  struct max_flow_type {
    
    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
    typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;

    graph_type& G;
    node_iterator s;
    node_iterator t;
    edge_property_vector<graph_type, T> flow;
    edge_property_vector<graph_type, T>& capacity;

    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) { 
      for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) 
        for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) 
          flow.put(j, 0);
    }
    void run() {
      typedef res_graph_type<graph_type, T> aug_graph_type;
      aug_graph_type res_graph(G, flow, capacity);

      bool augment;
      do {
        augment=false;

        typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
        bfs_queue_type bfs_queue;
        bfs_queue.push(res_graph.first_out_edge(s));

        typedef node_property_vector<aug_graph_type, bool> reached_type;
        //reached_type reached(res_graph);
        //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
        reached_type reached(res_graph, false);
        reached.put(s, true); 
        
        bfs_iterator1< aug_graph_type, reached_type > 
        res_bfs(res_graph, bfs_queue, reached);

        typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
        pred_type pred(res_graph);
        pred.put(s, res_graph.invalid_edge());

        typedef node_property_vector<aug_graph_type, int> free_type;
        free_type free(res_graph);
        
        //searching for augmenting path
        while ( res_bfs.is_valid() ) { 
          //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
          if (res_bfs.is_newly_reached()) {
            graph_traits<aug_graph_type>::edge_iterator e;
            e=res_bfs;
            node_iterator v=res_graph.tail(e);
            node_iterator w=res_graph.head(e);
            //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
            pred.put(w, e);
            if (pred.get(v).is_valid()) {
              free.put(w, std::min(free.get(v), e.free()));
              //std::cout <<" nem elso csucs: ";
              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
            } else {
              free.put(w, e.free()); 
              //std::cout <<" elso csucs: ";
              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
            }
            //std::cout<<std::endl;
          }
        
          if (res_graph.head(res_bfs)==t) break;
          ++res_bfs;
        }
        if (reached.get(t)) {
          augment=true;
          node_iterator n=t;
          T augment_value=free.get(t);
          std::cout<<"augmentation: ";
          while (pred.get(n).is_valid()) { 
            graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);
            e.augment(augment_value); 
            std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
            n=res_graph.tail(e);
          }
          std::cout<<std::endl;
        }

        std::cout << "actual flow: "<< std::endl;
        for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) { 
          std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
        }
        std::cout<<std::endl;

      } while (augment);
    }
  };

} // namespace marci

#endif //MARCI_MAX_FLOW_HH