COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/bfs-bench.cc @ 2130:244e108de26f

Last change on this file since 2130:244e108de26f was 1956:a055123339d5, checked in by Alpar Juttner, 18 years ago

Unified copyright notices

File size: 2.9 KB
RevLine 
[1956]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 */
[742]18
[1632]19#include<queue>
20#include<cmath>
[921]21#include<lemon/smart_graph.h>
[742]22#include"bench_tools.h"
23
24using namespace std;
[921]25using namespace lemon;
[742]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{
[1756]50  GRAPH_TYPEDEFS(typename Graph);
[742]51
52  using namespace std;
53 
[751]54  typename Graph::template NodeMap<bool> visited(G,false);
[742]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();
[774]64    for(OutEdgeIt e(G,n);e!=INVALID;++e)
[986]65      if(!visited[m=G.target(e)]) {
[742]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{
[1756]75  GRAPH_TYPEDEFS(typename Graph);
[742]76
77  using namespace std;
78 
[751]79  typename Graph::template NodeMap<bool> visited(G,false);
[742]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++];
[774]92    for(OutEdgeIt e(G,n);e!=INVALID;++e)
[986]93      if(!visited[m=G.target(e)]) {
[742]94        Q[Qh++]=m;
95        visited.set(m,true);
96      }
97  } while(Qt!=Qh);
98}
99
[751]100template<class Graph>
101void iteratorBench(Graph &G)
102{
[1756]103  GRAPH_TYPEDEFS(typename Graph);
[751]104
105  int i=0;
106 
[774]107  for(NodeIt n(G);n!=INVALID;++n)
108    for(OutEdgeIt e(G,n);e!=INVALID;++e)
[751]109      i++;
110}
111
[742]112int main(int argc, char *argv[])
113{
114  typedef SmartGraph Graph;
115
[1756]116  GRAPH_TYPEDEFS(Graph);
[742]117
118  Graph G;
119 
120  Timer T;
121 
[751]122  if(argc!=3) {
123    cout << "Usage: " << argv[0] << " dim mul\n";
[742]124    return 1;
125  }
126 
127  int dim=atoi(argv[1]);
[751]128  int mul=atoi(argv[2]);
[742]129 
130//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
131//        << dim*(1<<dim) << " edges):";
132
[1847]133  T.restart();
[742]134  vector<Node> nodes;
[1689]135  addBiDirHyperCube(G,dim,nodes);
[742]136
137  PrintTime("GENGRAPH",T);
138
[1847]139  T.restart();
[742]140  {
[751]141    for(int i=0;i<mul;i++)
[742]142      bfsStlQueue(G,nodes[0]);
143  }
144  PrintTime("BFS-STL",T);
[1847]145  T.restart();
[742]146  {
[751]147    for(int i=0;i<mul;i++)
[742]148      bfsOwnQueue(G,nodes[0]);
149  }
150  PrintTime("BFS-OWN",T);
[1847]151  T.restart();
[751]152  {
153    for(int i=0;i<mul;i++)
154      iteratorBench(G);
155  }
156  PrintTime("ITERATE",T);
157
158
[742]159}
Note: See TracBrowser for help on using the repository browser.