alpar@74: // -*- mode:c++ -*- alpar@74: alpar@74: #ifndef EDMONDS_KARP_HH alpar@74: #define EDMONDS_KARP_HH alpar@74: alpar@74: #include alpar@74: alpar@74: //#include alpar@74: alpar@74: #include alpar@74: alpar@74: //#include alpar@74: alpar@921: namespace lemon { alpar@74: template alpar@987: typename FlowMap::Value 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@987: typedef typename FlowMap::Value 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 bfs_queue; alpar@74: typename Graph::NodeMap 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 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)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@986: gn = visited.get(t)==1 ? G.source(tree.get(t)) : G.target(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