COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/bfs-bench.cc @ 1416:1b481ced25e7

Last change on this file since 1416:1b481ced25e7 was 986:e997802b855c, checked in by Alpar Juttner, 20 years ago

Naming changes:

  • head -> target
  • tail -> source
File size: 2.3 KB
Line 
1// -*- mode:C++ -*-
2
3#include <queue>
4#include<math.h>
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_TYPEDEF_FACTORY(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_TYPEDEF_FACTORY(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_TYPEDEF_FACTORY(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  ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
101  GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
102
103  Graph G;
104 
105  Timer T;
106 
107  if(argc!=3) {
108    cout << "Usage: " << argv[0] << " dim mul\n";
109    return 1;
110  }
111 
112  int dim=atoi(argv[1]);
113  int mul=atoi(argv[2]);
114 
115//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
116//        << dim*(1<<dim) << " edges):";
117
118  T.reset();
119  vector<Node> nodes;
120  addBiDirHiperCube(G,dim,nodes);
121
122  PrintTime("GENGRAPH",T);
123
124  T.reset();
125  {
126    for(int i=0;i<mul;i++)
127      bfsStlQueue(G,nodes[0]);
128  }
129  PrintTime("BFS-STL",T);
130  T.reset();
131  {
132    for(int i=0;i<mul;i++)
133      bfsOwnQueue(G,nodes[0]);
134  }
135  PrintTime("BFS-OWN",T);
136  T.reset();
137  {
138    for(int i=0;i<mul;i++)
139      iteratorBench(G);
140  }
141  PrintTime("ITERATE",T);
142
143
144}
Note: See TracBrowser for help on using the repository browser.