// -*- mode:c++ -*-

#ifndef EDMONDS_KARP_HH

#define EDMONDS_KARP_HH

#include <queue>

//#include <marci_property_vector.hh>

#include <algorithm>

//#include <bfs_iterator.hh>

namespace marci {

  template <typename Graph, typename FlowMap, typename CapacityMap>

  typename FlowMap::ValueType maxFlow(Graph &G,

				      FlowMap &f,

				      CapacityMap &c,

				      typename Graph::NodeIt s,

				      typename Graph::NodeIt t)

  { 

    typedef typename Graph::NodeIt NodeIt;

    typedef typename Graph::EachNodeIt EachNodeIt;

    typedef typename Graph::EdgeIt EdgeIt;

    typedef typename Graph::EachEdgeIt EachEdgeIt;

    typedef typename Graph::OutEdgeIt OutEdgeIt;

    typedef typename Graph::InEdgeIt InEdgeIt;

    typedef typename FlowMap::ValueType T;

    T flow_val = 0;

    T aug_val;

    for(EachEdgeIt e(G);G.valid(e);G.goNext(e))

      f.set(e,0);

    std::queue<NodeIt> bfs_queue;

    typename Graph::NodeMap<int> visited(G); //0: unvisited,

                                             //1: reached by a forward edge

                                             //2: reached by a backward edge

                                             //3: it is node s

    typename Graph::NodeMap<EdgeIt> tree(G);

    NodeIt gn;  //FIXME: it might be too global for some people...

  augment:

    for(EachNodeIt n(G);G.valid(n);G.goNext(n))

      visited.set(n,0);

    visited.set(s,3);

    //There must be a better way to do this:

    while(!bfs_queue.empty()) bfs_queue.pop();

    bfs_queue.push(s);

    while(!bfs_queue.empty() && !visited.get(t))

      {

	NodeIt n(bfs_queue.front());

	bfs_queue.pop();

	for(OutEdgeIt e(G,n);G.valid(e);G.goNext(e))

	  if(f.get(e)<c.get(e) &&   //FIXME: <

	     !visited.get(G.bNode(e))) 

	    {

	      NodeIt nn(G.bNode(e)); //It improves nothing

	      tree.set(nn,e);

	      visited.set(nn,1);

	      bfs_queue.push(nn);

	    }

	for(InEdgeIt e(G,n);G.valid(e);G.goNext(e))

	  if(f.get(e)>0 &&   //FIXME: >

	     !visited.get(G.bNode(e))) 

	    {

	      NodeIt nn(G.bNode(e));

	      tree.set(nn,e);

	      visited.set(nn,2);

	      bfs_queue.push(nn);

	    }

      }

    if(!visited.get(t)) return flow_val;

    // Augmenting value computation

    aug_val = visited.get(t)==1 ?

      c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t));

    //FIXME: I would need 'G.opposite(e,n)'

    gn = visited.get(t)==1 ? G.tail(tree.get(t)) : G.head(tree.get(t));

    while(gn!=s) if(visited.get(gn)==1)

      {

	//FIXME: nonstandard gcc extension!

	aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn));

	gn=G.tail(tree.get(gn));

      }

    else {

      //FIXME: nonstandard gcc extension!

      aug_val <?= f.get(tree.get(gn));

      gn=G.head(tree.get(gn));

    }

    // The augmentation itself

    gn = t;

    while(gn!=s) if(visited.get(gn)==1)

      {

	f.set(tree.get(gn),f.get(tree.get(gn))+aug_val);

	gn=G.tail(tree.get(gn));

      }

    else {

      f.set(tree.get(gn),f.get(tree.get(gn))-aug_val);

      gn=G.head(tree.get(gn));

    }

    flow_val+=aug_val;

    goto augment;   // Vivat goto forever!

  }

} // namespace marci

#endif //EDMONDS_KARP_HH