alpar@1956: /* -*- C++ -*-
alpar@1956:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2391:  * Copyright (C) 2003-2007
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1956:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1956:  *
alpar@1956:  * Permission to use, modify and distribute this software is granted
alpar@1956:  * provided that this copyright notice appears in all copies. For
alpar@1956:  * precise terms see the accompanying LICENSE file.
alpar@1956:  *
alpar@1956:  * This software is provided "AS IS" with no warranty of any kind,
alpar@1956:  * express or implied, and with no claim as to its suitability for any
alpar@1956:  * purpose.
alpar@1956:  *
alpar@1956:  */
alpar@742: 
alpar@1632: #include<queue>
alpar@1632: #include<cmath>
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@1756:   GRAPH_TYPEDEFS(typename 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@1756:   GRAPH_TYPEDEFS(typename 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@1756:   GRAPH_TYPEDEFS(typename 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@1756:   GRAPH_TYPEDEFS(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@1847:   T.restart();
alpar@742:   vector<Node> nodes;
alpar@1689:   addBiDirHyperCube(G,dim,nodes);
alpar@742: 
alpar@742:   PrintTime("GENGRAPH",T);
alpar@742: 
alpar@1847:   T.restart();
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@1847:   T.restart();
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@1847:   T.restart();
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: }