src/work/athos/bfs_test.cc
author alpar
Sat, 13 Nov 2004 12:53:28 +0000
changeset 986 e997802b855c
parent 921 818510fa3d99
permissions -rw-r--r--
Naming changes:
- head -> target
- tail -> source
athos@671
     1
// -*- c++ -*-
athos@671
     2
#include <iostream>
athos@671
     3
#include <fstream>
athos@671
     4
athos@671
     5
#include <sage_graph.h>
athos@671
     6
//#include <smart_graph.h>
alpar@921
     7
#include <lemon/dimacs.h>
alpar@921
     8
#include <lemon/time_measure.h>
alpar@921
     9
#include <lemon/for_each_macros.h>
athos@671
    10
#include <bfs_dfs.h>
athos@671
    11
alpar@921
    12
using namespace lemon;
athos@671
    13
athos@671
    14
int main() {
athos@671
    15
  typedef SageGraph Graph; 
athos@671
    16
  typedef Graph::Node Node;
athos@671
    17
  typedef Graph::NodeIt NodeIt;
athos@671
    18
  typedef Graph::Edge Edge;
athos@671
    19
  typedef Graph::EdgeIt EdgeIt;
athos@671
    20
  typedef Graph::OutEdgeIt OutEdgeIt;
athos@671
    21
athos@671
    22
  Graph g;
athos@671
    23
  Node s, t;
athos@671
    24
  Graph::EdgeMap<int> cap(g);
athos@671
    25
  //readDimacsMaxFlow(std::cin, g, s, t, cap);
athos@671
    26
  readDimacs(std::cin, g);
athos@671
    27
athos@671
    28
  Graph::NodeMap<OutEdgeIt> pred(g);
athos@671
    29
athos@671
    30
  Timer ts;
athos@671
    31
  /*
athos@671
    32
  {
athos@671
    33
    ts.reset();
athos@671
    34
    Graph::NodeMap<bool> reached(g);
athos@671
    35
    reached.set(s, true);
athos@671
    36
    pred.set(s, INVALID);
athos@671
    37
    std::queue<Node> bfs_queue;
athos@671
    38
    bfs_queue.push(t);
athos@671
    39
    while (!bfs_queue.empty()) {
athos@671
    40
      Node v=bfs_queue.front();	
athos@671
    41
      bfs_queue.pop();
athos@671
    42
      OutEdgeIt e;
athos@671
    43
      for(g.first(e,v); g.valid(e); g.next(e)) {
alpar@986
    44
	Node w=g.target(e);
athos@671
    45
	if (!reached[w]) {
athos@671
    46
	  bfs_queue.push(w);
athos@671
    47
	  reached.set(w, true);
athos@671
    48
	  pred.set(w, e);
athos@671
    49
	}
athos@671
    50
      }
athos@671
    51
    }
athos@671
    52
athos@671
    53
    std::cout << ts << std::endl;
athos@671
    54
  }
athos@671
    55
  */
athos@671
    56
athos@671
    57
  {
athos@671
    58
    ts.reset();
athos@671
    59
    Graph::NodeMap<bool> bfs_reached(g);
athos@671
    60
    Graph::NodeMap<Edge> bfs_pred(g); 
athos@671
    61
    Graph::NodeMap<int> bfs_dist(g);
athos@671
    62
      
athos@671
    63
    Bfs< Graph, Graph::NodeMap<bool>, 
athos@671
    64
      Graph::NodeMap<Edge>, Graph::NodeMap<int> > 
athos@671
    65
      bfs(g,bfs_reached, bfs_pred, bfs_dist );
athos@671
    66
    bfs.run(s);
athos@671
    67
    /*
athos@671
    68
    pred.set(s, INVALID);
athos@671
    69
    while (!bfs.finished()) { 
athos@671
    70
      ++bfs; 
athos@671
    71
      if (g.valid(bfs) && bfs.isBNodeNewlyReached()) 
athos@671
    72
	pred.set(bfs.bNode(), bfs);
athos@671
    73
    }
athos@671
    74
    */
athos@671
    75
    std::cout << ts << std::endl;
athos@671
    76
  }
athos@671
    77
athos@671
    78
  return 0;
athos@671
    79
}