COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/bfs-bench.cc @ 2158:0b620ff10e7c

Last change on this file since 2158:0b620ff10e7c was 1956:a055123339d5, checked in by Alpar Juttner, 18 years ago

Unified copyright notices

File size: 2.9 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include<queue>
20#include<cmath>
21#include<lemon/smart_graph.h>
22#include"bench_tools.h"
23
24using namespace std;
25using namespace lemon;
26
27inline int numOfOnes(int n,int dim)
28{
29  int s=0;
30  for(int i=0;i<dim;i++) {
31    s+=n%2;
32    n>>=1;
33  }
34  return s;
35}
36
37inline int numOfZeros(int n,int dim)
38{
39  int s=dim;
40  for(int i=0;i<dim;i++) {
41    s-=n&1;
42    n>>=1;
43  }
44  return s;
45}
46
47template<class Graph>
48void bfsStlQueue(Graph &G,typename Graph::Node source)
49{
50  GRAPH_TYPEDEFS(typename Graph);
51
52  using namespace std;
53 
54  typename Graph::template NodeMap<bool> visited(G,false);
55   
56  queue<typename Graph::Node> Q;
57   
58  Q.push(source);
59  visited[source]=true;
60  do {
61    Node n(Q.front());
62    Node m;
63    Q.pop();
64    for(OutEdgeIt e(G,n);e!=INVALID;++e)
65      if(!visited[m=G.target(e)]) {
66        Q.push(m);
67        visited.set(m,true);
68      }
69  } while(!Q.empty());
70}
71
72template<class Graph>
73void bfsOwnQueue(Graph &G,typename Graph::Node source)
74{
75  GRAPH_TYPEDEFS(typename Graph);
76
77  using namespace std;
78 
79  typename Graph::template NodeMap<bool> visited(G,false);
80 
81  int N=G.nodeNum();
82  vector<typename Graph::Node> Q(N);
83  int Qh=0;
84  int Qt=0;
85 
86
87  Q[Qh++]=source;
88  visited.set(source,true);
89  do {
90    Node m;
91    Node n=Q[Qt++];
92    for(OutEdgeIt e(G,n);e!=INVALID;++e)
93      if(!visited[m=G.target(e)]) {
94        Q[Qh++]=m;
95        visited.set(m,true);
96      }
97  } while(Qt!=Qh);
98}
99
100template<class Graph>
101void iteratorBench(Graph &G)
102{
103  GRAPH_TYPEDEFS(typename Graph);
104
105  int i=0;
106 
107  for(NodeIt n(G);n!=INVALID;++n)
108    for(OutEdgeIt e(G,n);e!=INVALID;++e)
109      i++;
110}
111
112int main(int argc, char *argv[])
113{
114  typedef SmartGraph Graph;
115
116  GRAPH_TYPEDEFS(Graph);
117
118  Graph G;
119 
120  Timer T;
121 
122  if(argc!=3) {
123    cout << "Usage: " << argv[0] << " dim mul\n";
124    return 1;
125  }
126 
127  int dim=atoi(argv[1]);
128  int mul=atoi(argv[2]);
129 
130//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
131//        << dim*(1<<dim) << " edges):";
132
133  T.restart();
134  vector<Node> nodes;
135  addBiDirHyperCube(G,dim,nodes);
136
137  PrintTime("GENGRAPH",T);
138
139  T.restart();
140  {
141    for(int i=0;i<mul;i++)
142      bfsStlQueue(G,nodes[0]);
143  }
144  PrintTime("BFS-STL",T);
145  T.restart();
146  {
147    for(int i=0;i<mul;i++)
148      bfsOwnQueue(G,nodes[0]);
149  }
150  PrintTime("BFS-OWN",T);
151  T.restart();
152  {
153    for(int i=0;i<mul;i++)
154      iteratorBench(G);
155  }
156  PrintTime("ITERATE",T);
157
158
159}
Note: See TracBrowser for help on using the repository browser.