marci@358: // -*- c++ -*-
marci@358: #include <iostream>
marci@358: #include <fstream>
marci@358: 
marci@358: #include <list_graph.h>
marci@358: #include <smart_graph.h>
marci@358: #include <dimacs.h>
marci@358: #include <time_measure.h>
marci@358: #include <for_each_macros.h>
marci@358: #include <bfs_iterator.h>
marci@358: 
marci@358: using namespace hugo;
marci@358: 
marci@358: int main() {
marci@358:   typedef ListGraph Graph; 
marci@358:   typedef Graph::Node Node;
marci@358:   typedef Graph::NodeIt NodeIt;
marci@358:   typedef Graph::Edge Edge;
marci@358:   typedef Graph::EdgeIt EdgeIt;
marci@358:   typedef Graph::OutEdgeIt OutEdgeIt;
marci@358: 
marci@358:   Graph G;
marci@358:   Node s, t;
marci@358:   Graph::EdgeMap<int> cap(G);
marci@358:   readDimacsMaxFlow(std::cin, G, s, t, cap);
marci@358:   Graph::NodeMap<OutEdgeIt> pred(G);
marci@358:   Timer ts;
marci@358:   {
marci@358:     ts.reset();
marci@358:     Graph::NodeMap<bool> reached(G);
marci@358:     reached.set(s, true);
marci@358:     pred.set(s, INVALID);
marci@358:     std::queue<Node> bfs_queue;
marci@358:     bfs_queue.push(t);
marci@358:     while (!bfs_queue.empty()) {
marci@358:       Node v=bfs_queue.front();	
marci@358:       bfs_queue.pop();
marci@358:       OutEdgeIt e;
marci@358:       for(G.first(e,v); G.valid(e); G.next(e)) {
marci@358: 	Node w=G.head(e);
marci@358: 	if (!reached[w]) {
marci@358: 	  bfs_queue.push(w);
marci@358: 	  reached.set(w, true);
marci@358: 	  pred.set(w, e);
marci@358: 	}
marci@358:       }
marci@358:     }
marci@358: 
marci@358:     std::cout << ts << std::endl;
marci@358:   }
marci@358: 
marci@358:   {
marci@358:     ts.reset();      
marci@360:     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
marci@358:     bfs.pushAndSetReached(s);
marci@358:     pred.set(s, INVALID);
marci@358:     while (!bfs.finished()) { 
marci@358:       ++bfs; 
marci@358:       if (G.valid(bfs) && bfs.isBNodeNewlyReached()) 
marci@358: 	pred.set(bfs.bNode(), bfs);
marci@358:     }
marci@358:     std::cout << ts << std::endl;
marci@358:   }
marci@358: 
marci@358:   return 0;
marci@358: }