alpar@742: // -*- mode:C++ -*- alpar@742: alpar@839: #include <queue> alpar@742: #include<math.h> alpar@921: #include<lemon/smart_graph.h> alpar@742: #include"bench_tools.h" alpar@742: alpar@742: using namespace std; alpar@921: using namespace lemon; alpar@742: alpar@742: inline int numOfOnes(int n,int dim) alpar@742: { alpar@742: int s=0; alpar@742: for(int i=0;i<dim;i++) { alpar@742: s+=n%2; alpar@742: n>>=1; alpar@742: } alpar@742: return s; alpar@742: } alpar@742: alpar@742: inline int numOfZeros(int n,int dim) alpar@742: { alpar@742: int s=dim; alpar@742: for(int i=0;i<dim;i++) { alpar@742: s-=n&1; alpar@742: n>>=1; alpar@742: } alpar@742: return s; alpar@742: } alpar@742: alpar@742: template<class Graph> alpar@742: void bfsStlQueue(Graph &G,typename Graph::Node source) alpar@742: { alpar@742: GRAPH_TYPEDEF_FACTORY(Graph); alpar@742: alpar@742: using namespace std; alpar@742: alpar@751: typename Graph::template NodeMap<bool> visited(G,false); alpar@742: alpar@742: queue<typename Graph::Node> Q; alpar@742: alpar@742: Q.push(source); alpar@742: visited[source]=true; alpar@742: do { alpar@742: Node n(Q.front()); alpar@742: Node m; alpar@742: Q.pop(); alpar@774: for(OutEdgeIt e(G,n);e!=INVALID;++e) alpar@986: if(!visited[m=G.target(e)]) { alpar@742: Q.push(m); alpar@742: visited.set(m,true); alpar@742: } alpar@742: } while(!Q.empty()); alpar@742: } alpar@742: alpar@742: template<class Graph> alpar@742: void bfsOwnQueue(Graph &G,typename Graph::Node source) alpar@742: { alpar@742: GRAPH_TYPEDEF_FACTORY(Graph); alpar@742: alpar@742: using namespace std; alpar@742: alpar@751: typename Graph::template NodeMap<bool> visited(G,false); alpar@742: alpar@742: int N=G.nodeNum(); alpar@742: vector<typename Graph::Node> Q(N); alpar@742: int Qh=0; alpar@742: int Qt=0; alpar@742: alpar@742: alpar@742: Q[Qh++]=source; alpar@742: visited.set(source,true); alpar@742: do { alpar@742: Node m; alpar@742: Node n=Q[Qt++]; alpar@774: for(OutEdgeIt e(G,n);e!=INVALID;++e) alpar@986: if(!visited[m=G.target(e)]) { alpar@742: Q[Qh++]=m; alpar@742: visited.set(m,true); alpar@742: } alpar@742: } while(Qt!=Qh); alpar@742: } alpar@742: alpar@751: template<class Graph> alpar@751: void iteratorBench(Graph &G) alpar@751: { alpar@751: GRAPH_TYPEDEF_FACTORY(Graph); alpar@751: alpar@751: int i=0; alpar@751: alpar@774: for(NodeIt n(G);n!=INVALID;++n) alpar@774: for(OutEdgeIt e(G,n);e!=INVALID;++e) alpar@751: i++; alpar@751: } alpar@751: alpar@742: int main(int argc, char *argv[]) alpar@742: { alpar@742: typedef SmartGraph Graph; alpar@742: alpar@742: ///\bug GRAPH_TYPEDEF_FACTORY(Graph); alpar@742: GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph); alpar@742: alpar@742: Graph G; alpar@742: alpar@742: Timer T; alpar@742: alpar@751: if(argc!=3) { alpar@751: cout << "Usage: " << argv[0] << " dim mul\n"; alpar@742: return 1; alpar@742: } alpar@742: alpar@742: int dim=atoi(argv[1]); alpar@751: int mul=atoi(argv[2]); alpar@742: alpar@742: // cout << "Creating Hipercube ("<< (1<<dim) << " nodes, " alpar@742: // << dim*(1<<dim) << " edges):"; alpar@742: alpar@742: T.reset(); alpar@742: vector<Node> nodes; alpar@742: addBiDirHiperCube(G,dim,nodes); alpar@742: alpar@742: PrintTime("GENGRAPH",T); alpar@742: alpar@742: T.reset(); alpar@742: { alpar@751: for(int i=0;i<mul;i++) alpar@742: bfsStlQueue(G,nodes[0]); alpar@742: } alpar@742: PrintTime("BFS-STL",T); alpar@742: T.reset(); alpar@742: { alpar@751: for(int i=0;i<mul;i++) alpar@742: bfsOwnQueue(G,nodes[0]); alpar@742: } alpar@742: PrintTime("BFS-OWN",T); alpar@751: T.reset(); alpar@751: { alpar@751: for(int i=0;i<mul;i++) alpar@751: iteratorBench(G); alpar@751: } alpar@751: PrintTime("ITERATE",T); alpar@751: alpar@751: alpar@742: }