src/work/marci/bfsit_vs_byhand.cc
author marci
Wed, 21 Apr 2004 15:14:45 +0000
changeset 360 91fba31268d6
parent 359 8cc53a6b1e61
child 389 770cc1f4861f
permissions -rw-r--r--
work/marci/bfs_iterator.h BfsIterator5 -> BfsIterator, DfsIterator5 -> DfsIterator
     1 // -*- c++ -*-
     2 #include <iostream>
     3 #include <fstream>
     4 
     5 #include <list_graph.h>
     6 #include <smart_graph.h>
     7 #include <dimacs.h>
     8 #include <time_measure.h>
     9 #include <for_each_macros.h>
    10 #include <bfs_iterator.h>
    11 
    12 using namespace hugo;
    13 
    14 int main() {
    15   typedef ListGraph 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   Graph::NodeMap<OutEdgeIt> pred(G);
    27   Timer ts;
    28   {
    29     ts.reset();
    30     Graph::NodeMap<bool> reached(G);
    31     reached.set(s, true);
    32     pred.set(s, INVALID);
    33     std::queue<Node> bfs_queue;
    34     bfs_queue.push(t);
    35     while (!bfs_queue.empty()) {
    36       Node v=bfs_queue.front();	
    37       bfs_queue.pop();
    38       OutEdgeIt e;
    39       for(G.first(e,v); G.valid(e); G.next(e)) {
    40 	Node w=G.head(e);
    41 	if (!reached[w]) {
    42 	  bfs_queue.push(w);
    43 	  reached.set(w, true);
    44 	  pred.set(w, e);
    45 	}
    46       }
    47     }
    48 
    49     std::cout << ts << std::endl;
    50   }
    51 
    52   {
    53     ts.reset();      
    54     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
    55     bfs.pushAndSetReached(s);
    56     pred.set(s, INVALID);
    57     while (!bfs.finished()) { 
    58       ++bfs; 
    59       if (G.valid(bfs) && bfs.isBNodeNewlyReached()) 
    60 	pred.set(bfs.bNode(), bfs);
    61     }
    62     std::cout << ts << std::endl;
    63   }
    64 
    65   return 0;
    66 }