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