COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/bfs-bench.cc @ 1827:dc660ed95b31

Last change on this file since 1827:dc660ed95b31 was 1756:b1f441f24d08, checked in by Alpar Juttner, 18 years ago

GRAPH_TYPEDEFS and UNDIRGRAPH_TYPEDEFS macros added to graph_utils.h.

File size: 2.3 KB
RevLine 
[742]1// -*- mode:C++ -*-
2
[1632]3#include<queue>
4#include<cmath>
[921]5#include<lemon/smart_graph.h>
[742]6#include"bench_tools.h"
7
8using namespace std;
[921]9using namespace lemon;
[742]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{
[1756]34  GRAPH_TYPEDEFS(typename Graph);
[742]35
36  using namespace std;
37 
[751]38  typename Graph::template NodeMap<bool> visited(G,false);
[742]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();
[774]48    for(OutEdgeIt e(G,n);e!=INVALID;++e)
[986]49      if(!visited[m=G.target(e)]) {
[742]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{
[1756]59  GRAPH_TYPEDEFS(typename Graph);
[742]60
61  using namespace std;
62 
[751]63  typename Graph::template NodeMap<bool> visited(G,false);
[742]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++];
[774]76    for(OutEdgeIt e(G,n);e!=INVALID;++e)
[986]77      if(!visited[m=G.target(e)]) {
[742]78        Q[Qh++]=m;
79        visited.set(m,true);
80      }
81  } while(Qt!=Qh);
82}
83
[751]84template<class Graph>
85void iteratorBench(Graph &G)
86{
[1756]87  GRAPH_TYPEDEFS(typename Graph);
[751]88
89  int i=0;
90 
[774]91  for(NodeIt n(G);n!=INVALID;++n)
92    for(OutEdgeIt e(G,n);e!=INVALID;++e)
[751]93      i++;
94}
95
[742]96int main(int argc, char *argv[])
97{
98  typedef SmartGraph Graph;
99
[1756]100  GRAPH_TYPEDEFS(Graph);
[742]101
102  Graph G;
103 
104  Timer T;
105 
[751]106  if(argc!=3) {
107    cout << "Usage: " << argv[0] << " dim mul\n";
[742]108    return 1;
109  }
110 
111  int dim=atoi(argv[1]);
[751]112  int mul=atoi(argv[2]);
[742]113 
114//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
115//        << dim*(1<<dim) << " edges):";
116
117  T.reset();
118  vector<Node> nodes;
[1689]119  addBiDirHyperCube(G,dim,nodes);
[742]120
121  PrintTime("GENGRAPH",T);
122
123  T.reset();
124  {
[751]125    for(int i=0;i<mul;i++)
[742]126      bfsStlQueue(G,nodes[0]);
127  }
128  PrintTime("BFS-STL",T);
129  T.reset();
130  {
[751]131    for(int i=0;i<mul;i++)
[742]132      bfsOwnQueue(G,nodes[0]);
133  }
134  PrintTime("BFS-OWN",T);
[751]135  T.reset();
136  {
137    for(int i=0;i<mul;i++)
138      iteratorBench(G);
139  }
140  PrintTime("ITERATE",T);
141
142
[742]143}
Note: See TracBrowser for help on using the repository browser.