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