COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/bfs-bench.cc @ 1768:1e2e0238e7c8

Last change on this file since 1768:1e2e0238e7c8 was 1756:b1f441f24d08, checked in by Alpar Juttner, 19 years ago

GRAPH_TYPEDEFS and UNDIRGRAPH_TYPEDEFS macros added to graph_utils.h.

File size: 2.3 KB
Line 
1// -*- mode:C++ -*-
2
3#include<queue>
4#include<cmath>
5#include<lemon/smart_graph.h>
6#include"bench_tools.h"
7
8using namespace std;
9using namespace lemon;
10
11inline int numOfOnes(int n,int dim)
12{
13  int s=0;
14  for(int i=0;i<dim;i++) {
15    s+=n%2;
16    n>>=1;
17  }
18  return s;
19}
20
21inline int numOfZeros(int n,int dim)
22{
23  int s=dim;
24  for(int i=0;i<dim;i++) {
25    s-=n&1;
26    n>>=1;
27  }
28  return s;
29}
30
31template<class Graph>
32void bfsStlQueue(Graph &G,typename Graph::Node source)
33{
34  GRAPH_TYPEDEFS(typename Graph);
35
36  using namespace std;
37 
38  typename Graph::template NodeMap<bool> visited(G,false);
39   
40  queue<typename Graph::Node> Q;
41   
42  Q.push(source);
43  visited[source]=true;
44  do {
45    Node n(Q.front());
46    Node m;
47    Q.pop();
48    for(OutEdgeIt e(G,n);e!=INVALID;++e)
49      if(!visited[m=G.target(e)]) {
50        Q.push(m);
51        visited.set(m,true);
52      }
53  } while(!Q.empty());
54}
55
56template<class Graph>
57void bfsOwnQueue(Graph &G,typename Graph::Node source)
58{
59  GRAPH_TYPEDEFS(typename Graph);
60
61  using namespace std;
62 
63  typename Graph::template NodeMap<bool> visited(G,false);
64 
65  int N=G.nodeNum();
66  vector<typename Graph::Node> Q(N);
67  int Qh=0;
68  int Qt=0;
69 
70
71  Q[Qh++]=source;
72  visited.set(source,true);
73  do {
74    Node m;
75    Node n=Q[Qt++];
76    for(OutEdgeIt e(G,n);e!=INVALID;++e)
77      if(!visited[m=G.target(e)]) {
78        Q[Qh++]=m;
79        visited.set(m,true);
80      }
81  } while(Qt!=Qh);
82}
83
84template<class Graph>
85void iteratorBench(Graph &G)
86{
87  GRAPH_TYPEDEFS(typename Graph);
88
89  int i=0;
90 
91  for(NodeIt n(G);n!=INVALID;++n)
92    for(OutEdgeIt e(G,n);e!=INVALID;++e)
93      i++;
94}
95
96int main(int argc, char *argv[])
97{
98  typedef SmartGraph Graph;
99
100  GRAPH_TYPEDEFS(Graph);
101
102  Graph G;
103 
104  Timer T;
105 
106  if(argc!=3) {
107    cout << "Usage: " << argv[0] << " dim mul\n";
108    return 1;
109  }
110 
111  int dim=atoi(argv[1]);
112  int mul=atoi(argv[2]);
113 
114//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
115//        << dim*(1<<dim) << " edges):";
116
117  T.reset();
118  vector<Node> nodes;
119  addBiDirHyperCube(G,dim,nodes);
120
121  PrintTime("GENGRAPH",T);
122
123  T.reset();
124  {
125    for(int i=0;i<mul;i++)
126      bfsStlQueue(G,nodes[0]);
127  }
128  PrintTime("BFS-STL",T);
129  T.reset();
130  {
131    for(int i=0;i<mul;i++)
132      bfsOwnQueue(G,nodes[0]);
133  }
134  PrintTime("BFS-OWN",T);
135  T.reset();
136  {
137    for(int i=0;i<mul;i++)
138      iteratorBench(G);
139  }
140  PrintTime("ITERATE",T);
141
142
143}
Note: See TracBrowser for help on using the repository browser.