marci@358: // -*- c++ -*-
marci@358: #include <iostream>
marci@358: #include <fstream>
marci@358: 
marci@642: #include <sage_graph.h>
marci@389: //#include <smart_graph.h>
marci@555: #include <hugo/dimacs.h>
marci@555: #include <hugo/time_measure.h>
marci@640: #include <hugo/for_each_macros.h>
marci@602: #include <bfs_dfs.h>
marci@358: 
marci@358: using namespace hugo;
marci@358: 
marci@358: int main() {
marci@642:   typedef SageGraph 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@577:   Graph g;
marci@358:   Node s, t;
marci@577:   Graph::EdgeMap<int> cap(g);
marci@577:   //readDimacsMaxFlow(std::cin, g, s, t, cap);
marci@577:   readDimacs(std::cin, g);
marci@577: 
marci@577:   Graph::NodeMap<OutEdgeIt> pred(g);
marci@358:   Timer ts;
marci@358:   {
marci@358:     ts.reset();
marci@577:     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@577:       for(g.first(e,v); g.valid(e); g.next(e)) {
marci@577: 	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@577:     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@577:       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: }