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