COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/bfs-bench.cc @ 742:235fd36336b7

Last change on this file since 742:235fd36336b7 was 742:235fd36336b7, checked in by Alpar Juttner, 17 years ago
  • bfs-bench added
  • hypercube generators moved to bench-tools.h
  • new benchmark script
File size: 2.1 KB
RevLine 
[742]1// -*- mode:C++ -*-
2
3#include<math.h>
4#include<hugo/list_graph.h>
5#include<hugo/smart_graph.h>
6#include<hugo/dijkstra.h>
7#include<hugo/max_flow.h>
8
9#include"bench_tools.h"
10
11using namespace std;
12using namespace hugo;
13
14inline int numOfOnes(int n,int dim)
15{
16  int s=0;
17  for(int i=0;i<dim;i++) {
18    s+=n%2;
19    n>>=1;
20  }
21  return s;
22}
23
24inline int numOfZeros(int n,int dim)
25{
26  int s=dim;
27  for(int i=0;i<dim;i++) {
28    s-=n&1;
29    n>>=1;
30  }
31  return s;
32}
33
34template<class Graph>
35void bfsStlQueue(Graph &G,typename Graph::Node source)
36{
37  GRAPH_TYPEDEF_FACTORY(Graph);
38
39  using namespace std;
40 
41  typename Graph::NodeMap<bool> visited(G,false);
42   
43  queue<typename Graph::Node> Q;
44   
45  Q.push(source);
46  visited[source]=true;
47  do {
48    Node n(Q.front());
49    Node m;
50    Q.pop();
51    for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
52      if(!visited[m=G.head(e)]) {
53        Q.push(m);
54        visited.set(m,true);
55      }
56  } while(!Q.empty());
57}
58
59template<class Graph>
60void bfsOwnQueue(Graph &G,typename Graph::Node source)
61{
62  GRAPH_TYPEDEF_FACTORY(Graph);
63
64  using namespace std;
65 
66  typename Graph::NodeMap<bool> visited(G,false);
67 
68  int N=G.nodeNum();
69  vector<typename Graph::Node> Q(N);
70  int Qh=0;
71  int Qt=0;
72 
73
74  Q[Qh++]=source;
75  visited.set(source,true);
76  do {
77    Node m;
78    Node n=Q[Qt++];
79    for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
80      if(!visited[m=G.head(e)]) {
81        Q[Qh++]=m;
82        visited.set(m,true);
83      }
84  } while(Qt!=Qh);
85}
86
87int main(int argc, char *argv[])
88{
89  //  typedef ListGraph Graph;
90  typedef SmartGraph Graph;
91
92  ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
93  GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
94
95  Graph G;
96 
97  Timer T;
98 
99  if(argc!=2) {
100    cout << "Usage: " << argv[0] << " dim\n";
101    return 1;
102  }
103 
104  int dim=atoi(argv[1]);
105 
106//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
107//        << dim*(1<<dim) << " edges):";
108
109  T.reset();
110  vector<Node> nodes;
111  addBiDirHiperCube(G,dim,nodes);
112
113  PrintTime("GENGRAPH",T);
114
115  T.reset();
116  {
117    for(int i=0;i<50000;i++)
118      bfsStlQueue(G,nodes[0]);
119  }
120  PrintTime("BFS-STL",T);
121  T.reset();
122  {
123    for(int i=0;i<50000;i++)
124      bfsOwnQueue(G,nodes[0]);
125  }
126  PrintTime("BFS-OWN",T);
127}
Note: See TracBrowser for help on using the repository browser.