1.1 --- a/src/benchmark/bfs-bench.cc Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,144 +0,0 @@
1.4 -// -*- mode:C++ -*-
1.5 -
1.6 -#include <queue>
1.7 -#include<math.h>
1.8 -#include<lemon/smart_graph.h>
1.9 -#include"bench_tools.h"
1.10 -
1.11 -using namespace std;
1.12 -using namespace lemon;
1.13 -
1.14 -inline int numOfOnes(int n,int dim)
1.15 -{
1.16 - int s=0;
1.17 - for(int i=0;i<dim;i++) {
1.18 - s+=n%2;
1.19 - n>>=1;
1.20 - }
1.21 - return s;
1.22 -}
1.23 -
1.24 -inline int numOfZeros(int n,int dim)
1.25 -{
1.26 - int s=dim;
1.27 - for(int i=0;i<dim;i++) {
1.28 - s-=n&1;
1.29 - n>>=1;
1.30 - }
1.31 - return s;
1.32 -}
1.33 -
1.34 -template<class Graph>
1.35 -void bfsStlQueue(Graph &G,typename Graph::Node source)
1.36 -{
1.37 - GRAPH_TYPEDEF_FACTORY(Graph);
1.38 -
1.39 - using namespace std;
1.40 -
1.41 - typename Graph::template NodeMap<bool> visited(G,false);
1.42 -
1.43 - queue<typename Graph::Node> Q;
1.44 -
1.45 - Q.push(source);
1.46 - visited[source]=true;
1.47 - do {
1.48 - Node n(Q.front());
1.49 - Node m;
1.50 - Q.pop();
1.51 - for(OutEdgeIt e(G,n);e!=INVALID;++e)
1.52 - if(!visited[m=G.target(e)]) {
1.53 - Q.push(m);
1.54 - visited.set(m,true);
1.55 - }
1.56 - } while(!Q.empty());
1.57 -}
1.58 -
1.59 -template<class Graph>
1.60 -void bfsOwnQueue(Graph &G,typename Graph::Node source)
1.61 -{
1.62 - GRAPH_TYPEDEF_FACTORY(Graph);
1.63 -
1.64 - using namespace std;
1.65 -
1.66 - typename Graph::template NodeMap<bool> visited(G,false);
1.67 -
1.68 - int N=G.nodeNum();
1.69 - vector<typename Graph::Node> Q(N);
1.70 - int Qh=0;
1.71 - int Qt=0;
1.72 -
1.73 -
1.74 - Q[Qh++]=source;
1.75 - visited.set(source,true);
1.76 - do {
1.77 - Node m;
1.78 - Node n=Q[Qt++];
1.79 - for(OutEdgeIt e(G,n);e!=INVALID;++e)
1.80 - if(!visited[m=G.target(e)]) {
1.81 - Q[Qh++]=m;
1.82 - visited.set(m,true);
1.83 - }
1.84 - } while(Qt!=Qh);
1.85 -}
1.86 -
1.87 -template<class Graph>
1.88 -void iteratorBench(Graph &G)
1.89 -{
1.90 - GRAPH_TYPEDEF_FACTORY(Graph);
1.91 -
1.92 - int i=0;
1.93 -
1.94 - for(NodeIt n(G);n!=INVALID;++n)
1.95 - for(OutEdgeIt e(G,n);e!=INVALID;++e)
1.96 - i++;
1.97 -}
1.98 -
1.99 -int main(int argc, char *argv[])
1.100 -{
1.101 - typedef SmartGraph Graph;
1.102 -
1.103 - ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
1.104 - GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
1.105 -
1.106 - Graph G;
1.107 -
1.108 - Timer T;
1.109 -
1.110 - if(argc!=3) {
1.111 - cout << "Usage: " << argv[0] << " dim mul\n";
1.112 - return 1;
1.113 - }
1.114 -
1.115 - int dim=atoi(argv[1]);
1.116 - int mul=atoi(argv[2]);
1.117 -
1.118 -// cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
1.119 -// << dim*(1<<dim) << " edges):";
1.120 -
1.121 - T.reset();
1.122 - vector<Node> nodes;
1.123 - addBiDirHiperCube(G,dim,nodes);
1.124 -
1.125 - PrintTime("GENGRAPH",T);
1.126 -
1.127 - T.reset();
1.128 - {
1.129 - for(int i=0;i<mul;i++)
1.130 - bfsStlQueue(G,nodes[0]);
1.131 - }
1.132 - PrintTime("BFS-STL",T);
1.133 - T.reset();
1.134 - {
1.135 - for(int i=0;i<mul;i++)
1.136 - bfsOwnQueue(G,nodes[0]);
1.137 - }
1.138 - PrintTime("BFS-OWN",T);
1.139 - T.reset();
1.140 - {
1.141 - for(int i=0;i<mul;i++)
1.142 - iteratorBench(G);
1.143 - }
1.144 - PrintTime("ITERATE",T);
1.145 -
1.146 -
1.147 -}