# Ticket #309: benchmark_graphs.cpp

File benchmark_graphs.cpp, 5.9 KB (added by , 15 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 | |

13 | using namespace std; |

14 | using namespace lemon; |

15 | |

16 | template <typename Graph> |

17 | class NodeIterator1 { |

18 | const Graph &_gr; |

19 | int _cnt; |

20 | public: |

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 | |

29 | template <typename Graph> |

30 | class NodeIterator2 { |

31 | const Graph &_gr; |

32 | int _cnt; |

33 | public: |

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 | |

43 | template <typename Graph> |

44 | class ArcIterator1 { |

45 | const Graph &_gr; |

46 | int _cnt; |

47 | public: |

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 | |

56 | template <typename Graph> |

57 | class ArcIterator2 { |

58 | const Graph &_gr; |

59 | int _cnt; |

60 | public: |

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 | |

70 | template <typename Graph> |

71 | class OutArcIterator { |

72 | const Graph &_gr; |

73 | int _cnt; |

74 | public: |

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 | |

85 | template <typename Graph> |

86 | class InArcIterator { |

87 | const Graph &_gr; |

88 | int _cnt; |

89 | public: |

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 | |

101 | const int K = 10; |

102 | |

103 | template <typename GR> |

104 | void 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 | |

148 | int 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 | } |