benchmark/bfs-bench.cc
author deba
Wed, 25 Jan 2006 14:40:26 +0000
changeset 1903 f3d24016dad5
parent 1756 b1f441f24d08
child 1956 a055123339d5
permissions -rw-r--r--
Bug fix
     1 // -*- mode:C++ -*-
     2 
     3 #include<queue>
     4 #include<cmath>
     5 #include<lemon/smart_graph.h>
     6 #include"bench_tools.h"
     7 
     8 using namespace std;
     9 using namespace lemon;
    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_TYPEDEFS(typename Graph);
    35 
    36   using namespace std;
    37   
    38   typename Graph::template NodeMap<bool> visited(G,false);
    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();
    48     for(OutEdgeIt e(G,n);e!=INVALID;++e)
    49       if(!visited[m=G.target(e)]) {
    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_TYPEDEFS(typename Graph);
    60 
    61   using namespace std;
    62   
    63   typename Graph::template NodeMap<bool> visited(G,false);
    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++];
    76     for(OutEdgeIt e(G,n);e!=INVALID;++e)
    77       if(!visited[m=G.target(e)]) {
    78 	Q[Qh++]=m;
    79 	visited.set(m,true);
    80       }
    81   } while(Qt!=Qh);
    82 }
    83 
    84 template<class Graph>
    85 void iteratorBench(Graph &G)
    86 {
    87   GRAPH_TYPEDEFS(typename Graph);
    88 
    89   int i=0;
    90   
    91   for(NodeIt n(G);n!=INVALID;++n)
    92     for(OutEdgeIt e(G,n);e!=INVALID;++e)
    93       i++;
    94 }
    95 
    96 int main(int argc, char *argv[])
    97 {
    98   typedef SmartGraph Graph;
    99 
   100   GRAPH_TYPEDEFS(Graph);
   101 
   102   Graph G;
   103   
   104   Timer T;
   105   
   106   if(argc!=3) {
   107     cout << "Usage: " << argv[0] << " dim mul\n";
   108     return 1;
   109   }
   110   
   111   int dim=atoi(argv[1]);
   112   int mul=atoi(argv[2]);
   113   
   114 //   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
   115 //        << dim*(1<<dim) << " edges):";
   116 
   117   T.restart();
   118   vector<Node> nodes;
   119   addBiDirHyperCube(G,dim,nodes);
   120 
   121   PrintTime("GENGRAPH",T);
   122 
   123   T.restart();
   124   {
   125     for(int i=0;i<mul;i++)
   126       bfsStlQueue(G,nodes[0]);
   127   }
   128   PrintTime("BFS-STL",T);
   129   T.restart();
   130   {
   131     for(int i=0;i<mul;i++)
   132       bfsOwnQueue(G,nodes[0]);
   133   }
   134   PrintTime("BFS-OWN",T);
   135   T.restart();
   136   {
   137     for(int i=0;i<mul;i++)
   138       iteratorBench(G);
   139   }
   140   PrintTime("ITERATE",T);
   141 
   142 
   143 }