source: lemon-0.x/src/work/edmonds_karp.hh @ 43:8ff5dc7d18eb

#ifndef MARCI_MAX_FLOW_HH
#define MARCI_MAX_FLOW_HH

#include <algorithm>

#include <bfs_iterator.hh>

namespace marci {

  template<typename Graph, typename T>
  class ResGraph {
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::EachNodeIt EachNodeIt;
    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
    const Graph& G;
    typename Graph::EdgeMap<T>& flow;
    const typename Graph::EdgeMap<T>& capacity;
  public:
    ResGraph(const Graph& _G, typename Graph::EdgeMap<T>& _flow, 
             const typename Graph::EdgeMap<T>& _capacity) : 
      G(_G), flow(_flow), capacity(_capacity) { }

    class EdgeIt; 
    class OutEdgeIt; 
    friend class EdgeIt; 
    friend class OutEdgeIt; 

    class EdgeIt {
      friend class ResGraph<Graph, T>;
    protected:
      const ResGraph<Graph, T>* resG;
      OldSymEdgeIt sym;
    public:
      EdgeIt() { } 
      //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
      T free() const { 
        if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
          return (resG->capacity.get(sym)-resG->flow.get(sym)); 
        } else { 
          return (resG->flow.get(sym)); 
        }
      }
      bool valid() const { return sym.valid(); }
      void augment(const T a) const {
        if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
          resG->flow.set(sym, resG->flow.get(sym)+a);
        } else { 
          resG->flow.set(sym, resG->flow.get(sym)-a);
        }
      }
    };

    class OutEdgeIt : public EdgeIt {
      friend class ResGraph<Graph, T>;
    public:
      OutEdgeIt() { }
      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
    private:
      OutEdgeIt(const ResGraph<Graph, T>& _resG, const NodeIt v) { 
        resG=&_resG;
        sym=resG->G.template first<OldSymEdgeIt>(v);
        while( sym.valid() && !(free()>0) ) { ++sym; }
      }
    public:
      OutEdgeIt& operator++() { 
        ++sym; 
        while( sym.valid() && !(free()>0) ) { ++sym; }
        return *this; 
      }
    };

    void getFirst(OutEdgeIt& e, const NodeIt v) const { 
      e=OutEdgeIt(*this, v); 
    }
    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
    
    template< typename It >
    It first() const { 
      It e;
      getFirst(e);
      return e; 
    }

    template< typename It >
    It first(const NodeIt v) const { 
      It e;
      getFirst(e, v);
      return e; 
    }

    NodeIt tail(const EdgeIt e) const { return G.aNode(e.sym); }
    NodeIt head(const EdgeIt e) const { return G.bNode(e.sym); }

    NodeIt aNode(const OutEdgeIt e) const { return G.aNode(e.sym); }
    NodeIt bNode(const OutEdgeIt e) const { return G.bNode(e.sym); }

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

    template <typename ValueType>
    class NodeMap {
      //const ResGraph<Graph, T>& G; 
      typename Graph::NodeMap<ValueType> node_map; 
    public:
      NodeMap(const ResGraph<Graph, T>& _G) : node_map(_G.G)/*: G(_G)*/ { }
      NodeMap(const ResGraph<Graph, T>& _G, const ValueType a) : node_map(_G.G, a) /*: G(_G)*/ { }
      void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); }
      ValueType get(const NodeIt nit) const { return node_map.get(nit); }
    };

  };

  template <typename Graph, typename T>
  struct max_flow_type {
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::EdgeIt EdgeIt;
    typedef typename Graph::EachEdgeIt EachEdgeIt;
    typedef typename Graph::OutEdgeIt OutEdgeIt;
    typedef typename Graph::InEdgeIt InEdgeIt;
    const Graph& G;
    NodeIt s;
    NodeIt t;
    typename Graph::EdgeMap<T> flow;
    const typename Graph::EdgeMap<T>& capacity;

    max_flow_type(const Graph& _G, NodeIt _s, NodeIt _t, const typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
    void run() {
      typedef ResGraph<Graph, T> AugGraph;
      AugGraph res_graph(G, flow, capacity);

      bool augment;
      do {
        augment=false;

        typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
        typedef typename AugGraph::EdgeIt AugEdgeIt;
        typedef std::queue<AugOutEdgeIt> BfsQueue;
        BfsQueue bfs_queue;
        bfs_queue.push(res_graph.template first<AugOutEdgeIt>(s));

        typedef typename AugGraph::NodeMap<bool> ReachedMap;
        ReachedMap reached(res_graph, false);
        reached.set(s, true); 
        
        bfs_iterator1< AugGraph, ReachedMap > 
        res_bfs(res_graph, bfs_queue, reached);

        typedef typename AugGraph::NodeMap<AugEdgeIt> PredMap;
        PredMap pred(res_graph);
        //typename AugGraph::EdgeIt a; //invalid
        //a.makeInvalid();
        //pred.set(s, a);

        typedef typename AugGraph::NodeMap<int> FreeMap;
        FreeMap free(res_graph);
        
        //searching for augmenting path
        while ( res_bfs.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.newly_reached()) {
            AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
            NodeIt v=res_graph.tail(e);
            NodeIt w=res_graph.head(e);
            //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
            pred.set(w, e);
            if (pred.get(v).valid()) {
              free.set(w, std::min(free.get(v), e.free()));
              //std::cout <<" nem elso csucs: ";
              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
            } else {
              free.set(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;
        } //end searching augmenting path
        if (reached.get(t)) {
          augment=true;
          NodeIt n=t;
          T augment_value=free.get(t);
          std::cout<<"augmentation: ";
          while (pred.get(n).valid()) { 
            AugEdgeIt 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(EachEdgeIt e=G.template first<EachEdgeIt>(); e.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