|
alpar@2238
|
1 |
#include"edge_lookup_test.h"
|
|
alpar@2235
|
2 |
#include<lemon/smart_graph.h>
|
|
alpar@2235
|
3 |
#include<vector>
|
|
alpar@2235
|
4 |
#include<lemon/time_measure.h>
|
|
alpar@2235
|
5 |
|
|
alpar@2235
|
6 |
using namespace lemon;
|
|
alpar@2235
|
7 |
|
|
alpar@2235
|
8 |
GRAPH_TYPEDEFS(SmartGraph)
|
|
alpar@2235
|
9 |
typedef SmartGraph Graph;
|
|
alpar@2235
|
10 |
|
|
alpar@2235
|
11 |
class FE
|
|
alpar@2235
|
12 |
{
|
|
alpar@2235
|
13 |
public:
|
|
alpar@2235
|
14 |
Graph &_g;
|
|
alpar@2235
|
15 |
FE(Graph &g) :_g(g) {}
|
|
alpar@2235
|
16 |
void operator()()
|
|
alpar@2235
|
17 |
{
|
|
alpar@2235
|
18 |
Edge e;
|
|
alpar@2235
|
19 |
|
|
alpar@2235
|
20 |
for(NodeIt v(_g);v!=INVALID;++v)
|
|
alpar@2235
|
21 |
for(NodeIt u(_g);u!=INVALID;++u)
|
|
alpar@2235
|
22 |
e=findEdge(_g,u,v);
|
|
alpar@2235
|
23 |
}
|
|
alpar@2235
|
24 |
|
|
alpar@2235
|
25 |
};
|
|
alpar@2235
|
26 |
|
|
alpar@2235
|
27 |
class EL
|
|
alpar@2235
|
28 |
{
|
|
alpar@2235
|
29 |
public:
|
|
alpar@2235
|
30 |
Graph &_g;
|
|
alpar@2235
|
31 |
EdgeLookUp<Graph> _el;
|
|
alpar@2235
|
32 |
EL(Graph &g) :_g(g), _el(g) {}
|
|
alpar@2235
|
33 |
void operator()()
|
|
alpar@2235
|
34 |
{
|
|
alpar@2235
|
35 |
Edge e;
|
|
alpar@2235
|
36 |
|
|
alpar@2235
|
37 |
for(NodeIt v(_g);v!=INVALID;++v)
|
|
alpar@2235
|
38 |
for(NodeIt u(_g);u!=INVALID;++u)
|
|
alpar@2235
|
39 |
e=_el(u,v);
|
|
alpar@2235
|
40 |
}
|
|
alpar@2235
|
41 |
|
|
alpar@2235
|
42 |
};
|
|
alpar@2235
|
43 |
class EL2
|
|
alpar@2235
|
44 |
{
|
|
alpar@2235
|
45 |
public:
|
|
alpar@2235
|
46 |
Graph &_g;
|
|
alpar@2235
|
47 |
EdgeLookUp2<Graph> _el;
|
|
alpar@2235
|
48 |
EL2(Graph &g) :_g(g), _el(g) {}
|
|
alpar@2235
|
49 |
void operator()()
|
|
alpar@2235
|
50 |
{
|
|
alpar@2235
|
51 |
Edge e;
|
|
alpar@2235
|
52 |
|
|
alpar@2235
|
53 |
for(NodeIt v(_g);v!=INVALID;++v)
|
|
alpar@2235
|
54 |
for(NodeIt u(_g);u!=INVALID;++u)
|
|
alpar@2235
|
55 |
e=_el(u,v);
|
|
alpar@2235
|
56 |
}
|
|
alpar@2235
|
57 |
|
|
alpar@2235
|
58 |
};
|
|
alpar@2235
|
59 |
|
|
alpar@2235
|
60 |
class EL3
|
|
alpar@2235
|
61 |
{
|
|
alpar@2235
|
62 |
public:
|
|
alpar@2235
|
63 |
Graph &_g;
|
|
alpar@2235
|
64 |
EdgeLookUp3<Graph> _el;
|
|
alpar@2235
|
65 |
EL3(Graph &g) :_g(g), _el(g) {}
|
|
alpar@2235
|
66 |
void operator()()
|
|
alpar@2235
|
67 |
{
|
|
alpar@2235
|
68 |
Edge e;
|
|
alpar@2235
|
69 |
|
|
alpar@2235
|
70 |
for(NodeIt v(_g);v!=INVALID;++v)
|
|
alpar@2235
|
71 |
for(NodeIt u(_g);u!=INVALID;++u)
|
|
alpar@2235
|
72 |
e=_el(u,v);
|
|
alpar@2235
|
73 |
}
|
|
alpar@2235
|
74 |
|
|
alpar@2235
|
75 |
};
|
|
alpar@2235
|
76 |
|
|
alpar@2240
|
77 |
// class EL4
|
|
alpar@2240
|
78 |
// {
|
|
alpar@2240
|
79 |
// public:
|
|
alpar@2240
|
80 |
// Graph &_g;
|
|
alpar@2240
|
81 |
// EdgeLookUp4<Graph> _el;
|
|
alpar@2240
|
82 |
// EL4(Graph &g) :_g(g), _el(g) {}
|
|
alpar@2240
|
83 |
// void operator()()
|
|
alpar@2240
|
84 |
// {
|
|
alpar@2240
|
85 |
// Edge e;
|
|
alpar@2235
|
86 |
|
|
alpar@2240
|
87 |
// for(NodeIt v(_g);v!=INVALID;++v)
|
|
alpar@2240
|
88 |
// for(NodeIt u(_g);u!=INVALID;++u)
|
|
alpar@2240
|
89 |
// e=_el(u,v);
|
|
alpar@2240
|
90 |
// }
|
|
alpar@2235
|
91 |
|
|
alpar@2240
|
92 |
// };
|
|
alpar@2235
|
93 |
|
|
alpar@2238
|
94 |
int main(int, char**argv)
|
|
alpar@2235
|
95 |
{
|
|
alpar@2235
|
96 |
int N=atoi(argv[1]);
|
|
alpar@2235
|
97 |
int M=int(N*atof(argv[2]));
|
|
alpar@2235
|
98 |
|
|
alpar@2235
|
99 |
Graph g;
|
|
alpar@2235
|
100 |
|
|
alpar@2235
|
101 |
std::vector<Node> v;
|
|
alpar@2235
|
102 |
for(int i=0;i<N;i++) v.push_back(g.addNode());
|
|
alpar@2235
|
103 |
for(int i=0;i<M;i++) g.addEdge(v[int(drand48()*N)],v[int(drand48()*N)]);
|
|
alpar@2235
|
104 |
|
|
alpar@2235
|
105 |
// {
|
|
alpar@2235
|
106 |
// Edge e;
|
|
alpar@2235
|
107 |
|
|
alpar@2235
|
108 |
// TimeReport t("findEdge: ");
|
|
alpar@2235
|
109 |
// for(NodeIt u(g);u!=INVALID;++u)
|
|
alpar@2235
|
110 |
// for(NodeIt v(g);v!=INVALID;++v)
|
|
alpar@2235
|
111 |
// e=findEdge(g,u,v);
|
|
alpar@2235
|
112 |
// }
|
|
alpar@2235
|
113 |
// {
|
|
alpar@2235
|
114 |
// Edge e;
|
|
alpar@2235
|
115 |
// EdgeLookUp<Graph> el(g);
|
|
alpar@2235
|
116 |
|
|
alpar@2235
|
117 |
// TimeReport t("EdgeLookUp: ");
|
|
alpar@2235
|
118 |
// for(NodeIt u(g);u!=INVALID;++u)
|
|
alpar@2235
|
119 |
// for(NodeIt v(g);v!=INVALID;++v)
|
|
alpar@2235
|
120 |
// e=el(u,v);
|
|
alpar@2235
|
121 |
// }
|
|
alpar@2235
|
122 |
|
|
alpar@2235
|
123 |
|
|
alpar@2235
|
124 |
TimeStamp t1 = runningTimeTest(FE(g),1);
|
|
alpar@2235
|
125 |
TimeStamp t2 = runningTimeTest(EL(g),1);
|
|
alpar@2235
|
126 |
TimeStamp t3 = runningTimeTest(EL2(g),1);
|
|
alpar@2235
|
127 |
TimeStamp t4 = runningTimeTest(EL3(g),1);
|
|
alpar@2240
|
128 |
// TimeStamp t5 = runningTimeTest(EL4(g),1);
|
|
alpar@2235
|
129 |
|
|
alpar@2235
|
130 |
std::cout << t1.userTime()/N/N << ' '
|
|
alpar@2235
|
131 |
<< t2.userTime()/N/N << ' '
|
|
alpar@2235
|
132 |
<< t3.userTime()/N/N << ' '
|
|
alpar@2235
|
133 |
<< t4.userTime()/N/N << ' '
|
|
alpar@2240
|
134 |
// << t5.userTime()/N/N
|
|
alpar@2240
|
135 |
<< std::endl;
|
|
alpar@2235
|
136 |
}
|
|
alpar@2235
|
137 |
|