alpar@74: // -*- mode:c++ -*-
alpar@74: 
alpar@74: #ifndef EDMONDS_KARP_HH
alpar@74: #define EDMONDS_KARP_HH
alpar@74: 
alpar@74: #include <queue>
alpar@74: 
alpar@74: //#include <marci_property_vector.hh>
alpar@74: 
alpar@74: #include <algorithm>
alpar@74: 
alpar@74: //#include <bfs_iterator.hh>
alpar@74: 
alpar@108: namespace hugo {
alpar@74:   template <typename Graph, typename FlowMap, typename CapacityMap>
alpar@74:   typename FlowMap::ValueType maxFlow(Graph &G,
alpar@74: 				      FlowMap &f,
alpar@74: 				      CapacityMap &c,
marci@95: 				      typename Graph::NodeIt s,
marci@95: 				      typename Graph::NodeIt t)
alpar@74:   { 
alpar@93:     typedef typename Graph::NodeIt NodeIt;
alpar@91:     typedef typename Graph::EachNodeIt EachNodeIt;
alpar@74:     typedef typename Graph::EdgeIt EdgeIt;
alpar@74:     typedef typename Graph::EachEdgeIt EachEdgeIt;
alpar@74:     typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@74:     typedef typename Graph::InEdgeIt InEdgeIt;
alpar@74:     typedef typename FlowMap::ValueType T;
alpar@74:     
alpar@74:     T flow_val = 0;
alpar@74:     T aug_val;
alpar@74: 
alpar@93:     for(EachEdgeIt e(G);G.valid(e);G.goNext(e))
alpar@74:       f.set(e,0);
alpar@74:     
alpar@93:     std::queue<NodeIt> bfs_queue;
alpar@74:     typename Graph::NodeMap<int> visited(G); //0: unvisited,
alpar@74:                                              //1: reached by a forward edge
alpar@74:                                              //2: reached by a backward edge
alpar@74:                                              //3: it is node s
alpar@74:     typename Graph::NodeMap<EdgeIt> tree(G);
alpar@74:     
alpar@94:     NodeIt gn;  //FIXME: it might be too global for some people...
alpar@74:     
alpar@74:   augment:
alpar@74:     
alpar@93:     for(EachNodeIt n(G);G.valid(n);G.goNext(n))
alpar@74:       visited.set(n,0);
alpar@74:     
alpar@74:     visited.set(s,3);
alpar@74:     
alpar@74:     //There must be a better way to do this:
alpar@74:     while(!bfs_queue.empty()) bfs_queue.pop();
alpar@74:     
alpar@74:     bfs_queue.push(s);
alpar@74:     
alpar@74:     while(!bfs_queue.empty() && !visited.get(t))
alpar@74:       {
alpar@93: 	NodeIt n(bfs_queue.front());
alpar@93: 	bfs_queue.pop();
alpar@93: 	for(OutEdgeIt e(G,n);G.valid(e);G.goNext(e))
alpar@74: 	  if(f.get(e)<c.get(e) &&   //FIXME: <
alpar@74: 	     !visited.get(G.bNode(e))) 
alpar@74: 	    {
alpar@93: 	      NodeIt nn(G.bNode(e)); //It improves nothing
alpar@93: 	      tree.set(nn,e);
alpar@93: 	      visited.set(nn,1);
alpar@93: 	      bfs_queue.push(nn);
alpar@74: 	    }
alpar@93: 	for(InEdgeIt e(G,n);G.valid(e);G.goNext(e))
alpar@74: 	  if(f.get(e)>0 &&   //FIXME: >
alpar@74: 	     !visited.get(G.bNode(e))) 
alpar@74: 	    {
alpar@93: 	      NodeIt nn(G.bNode(e));
alpar@93: 	      tree.set(nn,e);
alpar@93: 	      visited.set(nn,2);
alpar@93: 	      bfs_queue.push(nn);
alpar@74: 	    }
alpar@74:       }
alpar@74:     
alpar@74:     if(!visited.get(t)) return flow_val;
alpar@74: 
alpar@74:     // Augmenting value computation
alpar@80:     aug_val = visited.get(t)==1 ?
alpar@74:       c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t));
alpar@74:     //FIXME: I would need 'G.opposite(e,n)'
alpar@80:     gn = visited.get(t)==1 ? G.tail(tree.get(t)) : G.head(tree.get(t));
alpar@80:     while(gn!=s) if(visited.get(gn)==1)
alpar@74:       {
alpar@93: 	//FIXME: nonstandard gcc extension!
alpar@74: 	aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn));
alpar@80: 	gn=G.tail(tree.get(gn));
alpar@74:       }
alpar@74:     else {
alpar@93:       //FIXME: nonstandard gcc extension!
alpar@74:       aug_val <?= f.get(tree.get(gn));
alpar@80:       gn=G.head(tree.get(gn));
alpar@74:     }
alpar@74: 	
alpar@74:     // The augmentation itself
alpar@74:     gn = t;
alpar@80:     while(gn!=s) if(visited.get(gn)==1)
alpar@74:       {
alpar@74: 	f.set(tree.get(gn),f.get(tree.get(gn))+aug_val);
alpar@80: 	gn=G.tail(tree.get(gn));
alpar@74:       }
alpar@74:     else {
alpar@74:       f.set(tree.get(gn),f.get(tree.get(gn))-aug_val);
alpar@80:       gn=G.head(tree.get(gn));
alpar@74:     }
alpar@74: 
alpar@74:     flow_val+=aug_val;
alpar@74: 
alpar@74:     goto augment;   // Vivat goto forever!
alpar@74:   }
alpar@74:   
alpar@108: } // namespace hugo
alpar@74: 
alpar@74: #endif //EDMONDS_KARP_HH