COIN-OR::LEMON - Graph Library

Ticket #309: benchmark_graphs.cpp

File benchmark_graphs.cpp, 5.9 KB (added by Peter Kovacs, 12 years ago)
Line 
1#include <iostream>
2#include <fstream>
3#include <cstdlib>
4
5#include <lemon/list_graph.h>
6#include <lemon/smart_graph.h>
7//#include <lemon/static_graph.h>
8#include <lemon/dimacs.h>
9#include <lemon/adaptors.h>
10#include <lemon/random.h>
11#include <lemon/time_measure.h>
12
13using namespace std;
14using namespace lemon;
15
16template <typename Graph>
17class NodeIterator1 {
18  const Graph &_gr;
19  int _cnt;
20public:
21  NodeIterator1(const Graph &gr) : _gr(gr), _cnt(0) {}
22  void operator()() {
23    for (typename Graph::NodeIt n(_gr); n != INVALID; ++n)
24      ++_cnt;
25  }
26  int count() { return _cnt; }
27};
28
29template <typename Graph>
30class NodeIterator2 {
31  const Graph &_gr;
32  int _cnt;
33public:
34  NodeIterator2(const Graph &gr) : _gr(gr), _cnt(0) {}
35  void operator()() {
36    typename Graph::Node n;
37    for (_gr.first(n); n != INVALID; _gr.next(n))
38      ++_cnt;
39  }
40  int count() { return _cnt; }
41};
42
43template <typename Graph>
44class ArcIterator1 {
45  const Graph &_gr;
46  int _cnt;
47public:
48  ArcIterator1(const Graph &gr) : _gr(gr), _cnt(0) {}
49  void operator()() {
50    for (typename Graph::ArcIt e(_gr); e != INVALID; ++e)
51      ++_cnt;
52  }
53  int count() { return _cnt; }
54};
55
56template <typename Graph>
57class ArcIterator2 {
58  const Graph &_gr;
59  int _cnt;
60public:
61  ArcIterator2(const Graph &gr) : _gr(gr), _cnt(0) {}
62  void operator()() {
63    typename Graph::Arc e;
64    for (_gr.first(e); e != INVALID; _gr.next(e))
65      ++_cnt;
66  }
67  int count() { return _cnt; }
68};
69
70template <typename Graph>
71class OutArcIterator {
72  const Graph &_gr;
73  int _cnt;
74public:
75  OutArcIterator(const Graph &gr) : _gr(gr), _cnt(0) {}
76  void operator()() {
77    for (typename Graph::NodeIt n(_gr); n != INVALID; ++n) {
78      for (typename Graph::OutArcIt e(_gr, n); e != INVALID; ++e)
79        ++_cnt;
80    }
81  }
82  int count() { return _cnt; }
83};
84
85template <typename Graph>
86class InArcIterator {
87  const Graph &_gr;
88  int _cnt;
89public:
90  InArcIterator(const Graph &gr) : _gr(gr), _cnt(0) {}
91  void operator()() {
92    for (typename Graph::NodeIt n(_gr); n != INVALID; ++n) {
93      for (typename Graph::InArcIt e(_gr, n); e != INVALID; ++e)
94        ++_cnt;
95    }
96  }
97  int count() { return _cnt; }
98};
99
100
101const int K = 10;
102
103template <typename GR>
104void benchmarkGraph(const GR &gr, int n, int m) {
105  Timer tni1, tni2, tai1, tai2, toai, tiai;
106  NodeIterator1<GR> ni1(gr);
107  NodeIterator2<GR> ni2(gr);
108  ArcIterator1<GR> ai1(gr);
109  ArcIterator2<GR> ai2(gr);
110  OutArcIterator<GR> oai(gr);
111  InArcIterator<GR> iai(gr);
112 
113  tni1.restart();
114  for (int i=0; i!=K; ++i) ni1();
115  tni1.stop();
116  tni2.restart();
117  for (int i=0; i!=K; ++i) ni2();
118  tni2.stop();
119  tai1.restart();
120  for (int i=0; i!=K; ++i) ai1();
121  tai1.stop();
122  tai2.restart();
123  for (int i=0; i!=K; ++i) ai2();
124  tai2.stop();
125  toai.restart();
126  for (int i=0; i!=K; ++i) oai();
127  toai.stop();
128  tiai.restart();
129  for (int i=0; i!=K; ++i) iai();
130  tiai.stop();
131
132  cout << "  NodeIt:    " << tni1.realTime() / K
133       << "    \t"        << tni2.realTime() / K << endl;
134  cout << "  ArcIt:     " << tai1.realTime() / K
135       << "    \t"        << tai2.realTime() / K << endl;
136  cout << "  OutArcIt:  " << toai.realTime() / K << endl;
137  cout << "  InArcIt:   " << tiai.realTime() / K << endl;
138  cout << endl;
139 
140  if (ni1.count() != K * n) exit(-1);
141  if (ni2.count() != K * n) exit(-1);
142  if (ai1.count() != K * m) exit(-1);
143  if (ai2.count() != K * m) exit(-1);
144  if (oai.count() != K * m) exit(-1);
145  if (iai.count() != K * m) exit(-1);
146}
147
148int main(int argc, char *argv[])
149{
150  if (argc < 3) {
151    cout << "Usage: " << argv[0] << " n m" << endl;
152    return -1;
153  }
154 
155  int n = atoi(argv[1]);
156  int m = atoi(argv[2]);
157 
158  cout << "Benchmark tests on a random digraph (n = " << n
159       << ", m = " << m << ")" << endl << endl;
160 
161  vector<pair<int, int> > arcs1;
162  for (int j = 0; j != m; ++j) {
163    arcs1.push_back(make_pair(rnd[n], rnd[n]));
164  }
165  vector<pair<int, int> > arcs2(arcs1);
166  sort(arcs2.begin(), arcs2.end());
167
168  // Building graphs
169  cout << "ListDigraph - Building                  ";
170  Timer tlgr1;
171  ListDigraph lgr1;
172  vector<ListDigraph::Node> lnodes1;
173  for (int i = 0; i != n; ++i) {
174    lnodes1.push_back(lgr1.addNode());
175  } 
176  for (int j = 0; j != m; ++j) {
177    lgr1.addArc(lnodes1[arcs1[j].first], lnodes1[arcs1[j].second]);
178  }
179  tlgr1.stop();
180  cout << tlgr1.realTime() << endl;
181 
182  cout << "ListDigraph (sorted arcs) - Building    ";
183  Timer tlgr2;
184  ListDigraph lgr2;
185  vector<ListDigraph::Node> lnodes2;
186  for (int i = 0; i != n; ++i) {
187    lnodes2.push_back(lgr2.addNode());
188  } 
189  for (int j = 0; j != m; ++j) {
190    lgr2.addArc(lnodes2[arcs2[j].first], lnodes2[arcs2[j].second]);
191  }
192  tlgr2.stop();
193  cout << tlgr2.realTime() << endl;
194
195  cout << "SmartDigraph - Building                 ";
196  Timer tsgr1;
197  SmartDigraph sgr1;
198  vector<SmartDigraph::Node> snodes1;
199  for (int i = 0; i != n; ++i) {
200    snodes1.push_back(sgr1.addNode());
201  } 
202  for (int j = 0; j != m; ++j) {
203    sgr1.addArc(snodes1[arcs1[j].first], snodes1[arcs1[j].second]);
204  }
205  tsgr1.stop();
206  cout << tsgr1.realTime() << endl;
207
208  cout << "SmartDigraph (sorted arcs) - Building   ";
209  Timer tsgr2;
210  SmartDigraph sgr2;
211  vector<SmartDigraph::Node> snodes2;
212  for (int i = 0; i != n; ++i) {
213    snodes2.push_back(sgr2.addNode());
214  } 
215  for (int j = 0; j != m; ++j) {
216    sgr2.addArc(snodes2[arcs2[j].first], snodes2[arcs2[j].second]);
217  }
218  tsgr2.stop();
219  cout << tsgr2.realTime() << endl;
220
221  cout << endl;
222 
223  // Iteration test
224  cout << "ListDigraph - Iteration" << endl;
225  benchmarkGraph(lgr1, n, m);
226 
227  cout << "ListDigraph (sorted arcs) - Iteration" << endl;
228  benchmarkGraph(lgr2, n, m);
229 
230  cout << "SmartDigraph - Iteration" << endl;
231  benchmarkGraph(sgr1, n, m);
232 
233  cout << "SmartDigraph (sorted arcs) - Iteration" << endl;
234  benchmarkGraph(sgr2, n, m);
235 
236  return 0;
237}