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