1.1 --- a/src/benchmark/Makefile.am	Tue Jul 27 16:04:21 2004 +0000
     1.2 +++ b/src/benchmark/Makefile.am	Tue Jul 27 16:09:42 2004 +0000
     1.3 @@ -1,7 +1,9 @@
     1.4  AM_CPPFLAGS = -I$(top_srcdir)/src -I$(top_srcdir)/src/work  -I$(top_srcdir)/src/work/marci
     1.5  
     1.6 -noinst_PROGRAMS = graph-bench hcube
     1.7 +noinst_PROGRAMS = graph-bench hcube bfs-bench
     1.8  
     1.9  graph_bench_SOURCES = graph-bench.cc bench_tools.h
    1.10  
    1.11  hcube_SOURCES = hcube.cc bench_tools.h
    1.12 +
    1.13 +bfs_bench_SOURCES = bfs-bench.cc bench_tools.h

     2.1 --- a/src/benchmark/bench_tools.h	Tue Jul 27 16:04:21 2004 +0000
     2.2 +++ b/src/benchmark/bench_tools.h	Tue Jul 27 16:09:42 2004 +0000
     2.3 @@ -81,6 +81,42 @@
     2.4  	    << S.getSystemTime() << ' ' << S.getRealTime() << std::endl;
     2.5  }
     2.6  
     2.7 +
     2.8 +
     2.9 +///
    2.10 +template<class Graph>
    2.11 +void addHiperCube(Graph &G,int dim,std::vector<typename Graph::Node> &nodes)
    2.12 +{
    2.13 +  GRAPH_TYPEDEF_FACTORY(Graph);
    2.14    
    2.15 +  std::vector<int> bits(dim+1);
    2.16 +  bits[0]=1;
    2.17 +  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
    2.18 +  
    2.19 +  for(int i=0;i<bits[dim];i++) {
    2.20 +    nodes.push_back(G.addNode());
    2.21 +    for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
    2.22 +  }
    2.23 +}
    2.24 +
    2.25 +///
    2.26 +template<class Graph>
    2.27 +void addBiDirHiperCube(Graph &G,int dim,std::vector<typename Graph::Node>&nodes)
    2.28 +{
    2.29 +  GRAPH_TYPEDEF_FACTORY(Graph);
    2.30 +  
    2.31 +  std::vector<int> bits(dim+1);
    2.32 +  bits[0]=1;
    2.33 +  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
    2.34 +  
    2.35 +  for(int i=0;i<bits[dim];i++) {
    2.36 +    nodes.push_back(G.addNode());
    2.37 +    for(int j=0;j<dim;j++) if(i&bits[j]) {
    2.38 +      G.addEdge(nodes[i-bits[j]],nodes[i]);
    2.39 +      G.addEdge(nodes[i],nodes[i-bits[j]]);
    2.40 +    }
    2.41 +    
    2.42 +  }
    2.43 +}  
    2.44  
    2.45  #endif

     3.1 --- a/src/benchmark/benchmark	Tue Jul 27 16:04:21 2004 +0000
     3.2 +++ b/src/benchmark/benchmark	Tue Jul 27 16:09:42 2004 +0000
     3.3 @@ -3,7 +3,8 @@
     3.4  function runtest () # prefix, prog, args
     3.5  {
     3.6      echo $1 1>&2
     3.7 -    for ((i=1;i<5;i++))
     3.8 +    $2 $3 $4 $5 $6 $7 $8 $9;
     3.9 +    for ((i=1;i<=5;i++))
    3.10        do
    3.11        $2 $3 $4 $5 $6 $7 $8 $9;
    3.12      done |

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/benchmark/bfs-bench.cc	Tue Jul 27 16:09:42 2004 +0000
     4.3 @@ -0,0 +1,127 @@
     4.4 +// -*- mode:C++ -*-
     4.5 +
     4.6 +#include<math.h>
     4.7 +#include<hugo/list_graph.h>
     4.8 +#include<hugo/smart_graph.h>
     4.9 +#include<hugo/dijkstra.h>
    4.10 +#include<hugo/max_flow.h>
    4.11 +
    4.12 +#include"bench_tools.h"
    4.13 +
    4.14 +using namespace std;
    4.15 +using namespace hugo;
    4.16 +
    4.17 +inline int numOfOnes(int n,int dim)
    4.18 +{
    4.19 +  int s=0;
    4.20 +  for(int i=0;i<dim;i++) {
    4.21 +    s+=n%2;
    4.22 +    n>>=1;
    4.23 +  }
    4.24 +  return s;
    4.25 +}
    4.26 +
    4.27 +inline int numOfZeros(int n,int dim)
    4.28 +{
    4.29 +  int s=dim;
    4.30 +  for(int i=0;i<dim;i++) {
    4.31 +    s-=n&1;
    4.32 +    n>>=1;
    4.33 +  }
    4.34 +  return s;
    4.35 +}
    4.36 +
    4.37 +template<class Graph>
    4.38 +void bfsStlQueue(Graph &G,typename Graph::Node source)
    4.39 +{
    4.40 +  GRAPH_TYPEDEF_FACTORY(Graph);
    4.41 +
    4.42 +  using namespace std;
    4.43 +  
    4.44 +  typename Graph::NodeMap<bool> visited(G,false);
    4.45 +    
    4.46 +  queue<typename Graph::Node> Q;
    4.47 +    
    4.48 +  Q.push(source);
    4.49 +  visited[source]=true;
    4.50 +  do {
    4.51 +    Node n(Q.front());
    4.52 +    Node m;
    4.53 +    Q.pop();
    4.54 +    for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
    4.55 +      if(!visited[m=G.head(e)]) {
    4.56 +	Q.push(m);
    4.57 +	visited.set(m,true);
    4.58 +      }
    4.59 +  } while(!Q.empty());
    4.60 +}
    4.61 +
    4.62 +template<class Graph>
    4.63 +void bfsOwnQueue(Graph &G,typename Graph::Node source)
    4.64 +{
    4.65 +  GRAPH_TYPEDEF_FACTORY(Graph);
    4.66 +
    4.67 +  using namespace std;
    4.68 +  
    4.69 +  typename Graph::NodeMap<bool> visited(G,false);
    4.70 +  
    4.71 +  int N=G.nodeNum();
    4.72 +  vector<typename Graph::Node> Q(N);
    4.73 +  int Qh=0;
    4.74 +  int Qt=0;
    4.75 +  
    4.76 +
    4.77 +  Q[Qh++]=source;
    4.78 +  visited.set(source,true);
    4.79 +  do {
    4.80 +    Node m;
    4.81 +    Node n=Q[Qt++];
    4.82 +    for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
    4.83 +      if(!visited[m=G.head(e)]) {
    4.84 +	Q[Qh++]=m;
    4.85 +	visited.set(m,true);
    4.86 +      }
    4.87 +  } while(Qt!=Qh);
    4.88 +}
    4.89 +
    4.90 +int main(int argc, char *argv[])
    4.91 +{
    4.92 +  //  typedef ListGraph Graph;
    4.93 +  typedef SmartGraph Graph;
    4.94 +
    4.95 +  ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
    4.96 +  GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
    4.97 +
    4.98 +  Graph G;
    4.99 +  
   4.100 +  Timer T;
   4.101 +  
   4.102 +  if(argc!=2) {
   4.103 +    cout << "Usage: " << argv[0] << " dim\n";
   4.104 +    return 1;
   4.105 +  }
   4.106 +  
   4.107 +  int dim=atoi(argv[1]);
   4.108 +  
   4.109 +//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
   4.110 +//        << dim*(1<<dim) << " edges):";
   4.111 +
   4.112 +  T.reset();
   4.113 +  vector<Node> nodes;
   4.114 +  addBiDirHiperCube(G,dim,nodes);
   4.115 +
   4.116 +  PrintTime("GENGRAPH",T);
   4.117 +
   4.118 +  T.reset();
   4.119 +  {
   4.120 +    for(int i=0;i<50000;i++)
   4.121 +      bfsStlQueue(G,nodes[0]);
   4.122 +  }
   4.123 +  PrintTime("BFS-STL",T);
   4.124 +  T.reset();
   4.125 +  {
   4.126 +    for(int i=0;i<50000;i++)
   4.127 +      bfsOwnQueue(G,nodes[0]);
   4.128 +  }
   4.129 +  PrintTime("BFS-OWN",T);
   4.130 +}

     5.1 --- a/src/benchmark/hcube.cc	Tue Jul 27 16:04:21 2004 +0000
     5.2 +++ b/src/benchmark/hcube.cc	Tue Jul 27 16:09:42 2004 +0000
     5.3 @@ -11,40 +11,6 @@
     5.4  using namespace std;
     5.5  using namespace hugo;
     5.6  
     5.7 -template<class Graph>
     5.8 -void addHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
     5.9 -{
    5.10 -  GRAPH_TYPEDEF_FACTORY(Graph);
    5.11 -  
    5.12 -  vector<int> bits(dim+1);
    5.13 -  bits[0]=1;
    5.14 -  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
    5.15 -  
    5.16 -  for(int i=0;i<bits[dim];i++) {
    5.17 -    nodes.push_back(G.addNode());
    5.18 -    for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
    5.19 -  }
    5.20 -}
    5.21 -
    5.22 -template<class Graph>
    5.23 -void addBiDirHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
    5.24 -{
    5.25 -  GRAPH_TYPEDEF_FACTORY(Graph);
    5.26 -  
    5.27 -  vector<int> bits(dim+1);
    5.28 -  bits[0]=1;
    5.29 -  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
    5.30 -  
    5.31 -  for(int i=0;i<bits[dim];i++) {
    5.32 -    nodes.push_back(G.addNode());
    5.33 -    for(int j=0;j<dim;j++) if(i&bits[j]) {
    5.34 -      G.addEdge(nodes[i-bits[j]],nodes[i]);
    5.35 -      G.addEdge(nodes[i],nodes[i-bits[j]]);
    5.36 -    }
    5.37 -    
    5.38 -  }
    5.39 -}
    5.40 -
    5.41  inline int numOfOnes(int n,int dim)
    5.42  {
    5.43    int s=0;