COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/bfs-bench.cc @ 774:4297098d9677

Last change on this file since 774:4297098d9677 was 774:4297098d9677, checked in by Alpar Juttner, 20 years ago

Merge back the whole branches/hugo++ to trunk.

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