src/work/marci/bfsit_vs_byhand.cc
author marci
Fri, 14 May 2004 18:28:57 +0000
changeset 642 e812963087f0
parent 640 d426dca0aaf7
child 762 511200bdb71f
permissions -rw-r--r--
To avoid confusion my old ListGraph is can be used under name SageGraph, work/sage_graph.h contains it.
     1 // -*- c++ -*-
     2 #include <iostream>
     3 #include <fstream>
     4 
     5 #include <sage_graph.h>
     6 //#include <smart_graph.h>
     7 #include <hugo/dimacs.h>
     8 #include <hugo/time_measure.h>
     9 #include <hugo/for_each_macros.h>
    10 #include <bfs_dfs.h>
    11 
    12 using namespace hugo;
    13 
    14 int main() {
    15   typedef SageGraph Graph; 
    16   typedef Graph::Node Node;
    17   typedef Graph::NodeIt NodeIt;
    18   typedef Graph::Edge Edge;
    19   typedef Graph::EdgeIt EdgeIt;
    20   typedef Graph::OutEdgeIt OutEdgeIt;
    21 
    22   Graph g;
    23   Node s, t;
    24   Graph::EdgeMap<int> cap(g);
    25   //readDimacsMaxFlow(std::cin, g, s, t, cap);
    26   readDimacs(std::cin, g);
    27 
    28   Graph::NodeMap<OutEdgeIt> pred(g);
    29   Timer ts;
    30   {
    31     ts.reset();
    32     Graph::NodeMap<bool> reached(g);
    33     reached.set(s, true);
    34     pred.set(s, INVALID);
    35     std::queue<Node> bfs_queue;
    36     bfs_queue.push(t);
    37     while (!bfs_queue.empty()) {
    38       Node v=bfs_queue.front();	
    39       bfs_queue.pop();
    40       OutEdgeIt e;
    41       for(g.first(e,v); g.valid(e); g.next(e)) {
    42 	Node w=g.head(e);
    43 	if (!reached[w]) {
    44 	  bfs_queue.push(w);
    45 	  reached.set(w, true);
    46 	  pred.set(w, e);
    47 	}
    48       }
    49     }
    50 
    51     std::cout << ts << std::endl;
    52   }
    53 
    54   {
    55     ts.reset();      
    56     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);
    57     bfs.pushAndSetReached(s);
    58     pred.set(s, INVALID);
    59     while (!bfs.finished()) { 
    60       ++bfs; 
    61       if (g.valid(bfs) && bfs.isBNodeNewlyReached()) 
    62 	pred.set(bfs.bNode(), bfs);
    63     }
    64     std::cout << ts << std::endl;
    65   }
    66 
    67   return 0;
    68 }