COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
10/16/04 02:20:13 (16 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1293
Message:

It's time to design an iterable generic bfs

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/bfsit_vs_byhand.cc

    r921 r944  
    33#include <fstream>
    44
    5 #include <sage_graph.h>
     5//#include <sage_graph.h>
    66#include <lemon/smart_graph.h>
     7#include <lemon/list_graph.h>
    78#include <lemon/dimacs.h>
    89#include <lemon/time_measure.h>
    910//#include <lemon/for_each_macros.h>
    10 #include <bfs_dfs.h>
     11#include <bfs_mm.h>
     12#include <lemon/bfs.h>
    1113
    1214using namespace lemon;
     
    1618
    1719int main() {
    18   typedef SageGraph Graph;
     20  //  typedef SageGraph Graph;
     21  typedef SmartGraph Graph ;
     22  //typedef ListGraph Graph;
    1923  typedef Graph::Node Node;
    2024  typedef Graph::NodeIt NodeIt;
     
    2428
    2529  Graph g;
    26   //Node s;
    27   //Graph::EdgeMap<int> cap(g);
    28   //readDimacsMaxFlow(std::cin, g, s, t, cap);
    2930  readDimacs(std::cin, g);
    30   NodeIt s;
    31   g.first(s);
     31  NodeIt s(g);
    3232
    3333  cout << g.nodeNum() << endl;
     
    3737  cout << "iteration time of bfs written by hand..." << endl;
    3838  Timer ts;
     39  ts.reset();
     40  for (int i=0; i<100; ++i)
    3941  {
    40     ts.reset();
    4142    Graph::NodeMap<bool> reached(g);
    4243    reached.set(s, true);
     
    4748      Node v=bfs_queue.front();
    4849      bfs_queue.pop();
    49       OutEdgeIt e;
    50       for(g.first(e,v); g.valid(e); g.next(e)) {
     50      for(OutEdgeIt e(g,v); e!=INVALID; ++e) {
    5151        Node w=g.head(e);
    5252        if (!reached[w]) {
     
    5757      }
    5858    }
    59 
    60     std::cout << ts << std::endl;
    6159  }
     60  std::cout << ts << std::endl;
    6261
    6362  cout << "iteration time with bfs iterator..." << endl;
     63  ts.reset();     
     64  for (int i=0; i<100; ++i)
    6465  {
    65     ts.reset();     
    66     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);
     66    Graph::NodeMap<bool> reached(g);
     67    marci::BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g, reached);
    6768    bfs.pushAndSetReached(s);
    6869    pred.set(s, INVALID);
    6970    while (!bfs.finished()) {
    7071      ++bfs;
    71       if (g.valid(bfs) && bfs.isBNodeNewlyReached())
     72      if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached())
    7273        pred.set(bfs.head(), Graph::Edge(bfs));
    7374    }
    74     std::cout << ts << std::endl;
    7575  }
     76  std::cout << ts << std::endl;
     77
     78  cout << "iteration time with bfs aplar..." << endl;
     79  ts.reset();     
     80  for (int i=0; i<100; ++i)
     81  {
     82    Bfs<Graph> bfs(g);
     83    bfs.setPredMap(pred);
     84    bfs.run(s);
     85  }
     86  std::cout << ts << std::endl;
     87
    7688
    7789  return 0;
Note: See TracChangeset for help on using the changeset viewer.