[742] | 1 | // -*- mode:C++ -*- |
---|
| 2 | |
---|
[1632] | 3 | #include<queue> |
---|
| 4 | #include<cmath> |
---|
[921] | 5 | #include<lemon/smart_graph.h> |
---|
[742] | 6 | #include"bench_tools.h" |
---|
| 7 | |
---|
| 8 | using namespace std; |
---|
[921] | 9 | using namespace lemon; |
---|
[742] | 10 | |
---|
| 11 | inline int numOfOnes(int n,int dim) |
---|
| 12 | { |
---|
| 13 | int s=0; |
---|
| 14 | for(int i=0;i<dim;i++) { |
---|
| 15 | s+=n%2; |
---|
| 16 | n>>=1; |
---|
| 17 | } |
---|
| 18 | return s; |
---|
| 19 | } |
---|
| 20 | |
---|
| 21 | inline int numOfZeros(int n,int dim) |
---|
| 22 | { |
---|
| 23 | int s=dim; |
---|
| 24 | for(int i=0;i<dim;i++) { |
---|
| 25 | s-=n&1; |
---|
| 26 | n>>=1; |
---|
| 27 | } |
---|
| 28 | return s; |
---|
| 29 | } |
---|
| 30 | |
---|
| 31 | template<class Graph> |
---|
| 32 | void bfsStlQueue(Graph &G,typename Graph::Node source) |
---|
| 33 | { |
---|
| 34 | GRAPH_TYPEDEF_FACTORY(Graph); |
---|
| 35 | |
---|
| 36 | using namespace std; |
---|
| 37 | |
---|
[751] | 38 | typename Graph::template NodeMap<bool> visited(G,false); |
---|
[742] | 39 | |
---|
| 40 | queue<typename Graph::Node> Q; |
---|
| 41 | |
---|
| 42 | Q.push(source); |
---|
| 43 | visited[source]=true; |
---|
| 44 | do { |
---|
| 45 | Node n(Q.front()); |
---|
| 46 | Node m; |
---|
| 47 | Q.pop(); |
---|
[774] | 48 | for(OutEdgeIt e(G,n);e!=INVALID;++e) |
---|
[986] | 49 | if(!visited[m=G.target(e)]) { |
---|
[742] | 50 | Q.push(m); |
---|
| 51 | visited.set(m,true); |
---|
| 52 | } |
---|
| 53 | } while(!Q.empty()); |
---|
| 54 | } |
---|
| 55 | |
---|
| 56 | template<class Graph> |
---|
| 57 | void bfsOwnQueue(Graph &G,typename Graph::Node source) |
---|
| 58 | { |
---|
| 59 | GRAPH_TYPEDEF_FACTORY(Graph); |
---|
| 60 | |
---|
| 61 | using namespace std; |
---|
| 62 | |
---|
[751] | 63 | typename Graph::template NodeMap<bool> visited(G,false); |
---|
[742] | 64 | |
---|
| 65 | int N=G.nodeNum(); |
---|
| 66 | vector<typename Graph::Node> Q(N); |
---|
| 67 | int Qh=0; |
---|
| 68 | int Qt=0; |
---|
| 69 | |
---|
| 70 | |
---|
| 71 | Q[Qh++]=source; |
---|
| 72 | visited.set(source,true); |
---|
| 73 | do { |
---|
| 74 | Node m; |
---|
| 75 | Node n=Q[Qt++]; |
---|
[774] | 76 | for(OutEdgeIt e(G,n);e!=INVALID;++e) |
---|
[986] | 77 | if(!visited[m=G.target(e)]) { |
---|
[742] | 78 | Q[Qh++]=m; |
---|
| 79 | visited.set(m,true); |
---|
| 80 | } |
---|
| 81 | } while(Qt!=Qh); |
---|
| 82 | } |
---|
| 83 | |
---|
[751] | 84 | template<class Graph> |
---|
| 85 | void iteratorBench(Graph &G) |
---|
| 86 | { |
---|
| 87 | GRAPH_TYPEDEF_FACTORY(Graph); |
---|
| 88 | |
---|
| 89 | int i=0; |
---|
| 90 | |
---|
[774] | 91 | for(NodeIt n(G);n!=INVALID;++n) |
---|
| 92 | for(OutEdgeIt e(G,n);e!=INVALID;++e) |
---|
[751] | 93 | i++; |
---|
| 94 | } |
---|
| 95 | |
---|
[742] | 96 | int main(int argc, char *argv[]) |
---|
| 97 | { |
---|
| 98 | typedef SmartGraph Graph; |
---|
| 99 | |
---|
| 100 | ///\bug GRAPH_TYPEDEF_FACTORY(Graph); |
---|
| 101 | GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph); |
---|
| 102 | |
---|
| 103 | Graph G; |
---|
| 104 | |
---|
| 105 | Timer T; |
---|
| 106 | |
---|
[751] | 107 | if(argc!=3) { |
---|
| 108 | cout << "Usage: " << argv[0] << " dim mul\n"; |
---|
[742] | 109 | return 1; |
---|
| 110 | } |
---|
| 111 | |
---|
| 112 | int dim=atoi(argv[1]); |
---|
[751] | 113 | int mul=atoi(argv[2]); |
---|
[742] | 114 | |
---|
| 115 | // cout << "Creating Hipercube ("<< (1<<dim) << " nodes, " |
---|
| 116 | // << dim*(1<<dim) << " edges):"; |
---|
| 117 | |
---|
| 118 | T.reset(); |
---|
| 119 | vector<Node> nodes; |
---|
[1689] | 120 | addBiDirHyperCube(G,dim,nodes); |
---|
[742] | 121 | |
---|
| 122 | PrintTime("GENGRAPH",T); |
---|
| 123 | |
---|
| 124 | T.reset(); |
---|
| 125 | { |
---|
[751] | 126 | for(int i=0;i<mul;i++) |
---|
[742] | 127 | bfsStlQueue(G,nodes[0]); |
---|
| 128 | } |
---|
| 129 | PrintTime("BFS-STL",T); |
---|
| 130 | T.reset(); |
---|
| 131 | { |
---|
[751] | 132 | for(int i=0;i<mul;i++) |
---|
[742] | 133 | bfsOwnQueue(G,nodes[0]); |
---|
| 134 | } |
---|
| 135 | PrintTime("BFS-OWN",T); |
---|
[751] | 136 | T.reset(); |
---|
| 137 | { |
---|
| 138 | for(int i=0;i<mul;i++) |
---|
| 139 | iteratorBench(G); |
---|
| 140 | } |
---|
| 141 | PrintTime("ITERATE",T); |
---|
| 142 | |
---|
| 143 | |
---|
[742] | 144 | } |
---|