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