diff -r d8475431bbbb -r 8e85e6bbefdf benchmark/bfs-bench.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/benchmark/bfs-bench.cc	Mon May 23 04:48:14 2005 +0000
@@ -0,0 +1,144 @@
+// -*- mode:C++ -*-
+
+#include <queue>
+#include<math.h>
+#include<lemon/smart_graph.h>
+#include"bench_tools.h"
+
+using namespace std;
+using namespace lemon;
+
+inline int numOfOnes(int n,int dim)
+{
+  int s=0;
+  for(int i=0;i<dim;i++) {
+    s+=n%2;
+    n>>=1;
+  }
+  return s;
+}
+
+inline int numOfZeros(int n,int dim)
+{
+  int s=dim;
+  for(int i=0;i<dim;i++) {
+    s-=n&1;
+    n>>=1;
+  }
+  return s;
+}
+
+template<class Graph>
+void bfsStlQueue(Graph &G,typename Graph::Node source)
+{
+  GRAPH_TYPEDEF_FACTORY(Graph);
+
+  using namespace std;
+  
+  typename Graph::template NodeMap<bool> visited(G,false);
+    
+  queue<typename Graph::Node> Q;
+    
+  Q.push(source);
+  visited[source]=true;
+  do {
+    Node n(Q.front());
+    Node m;
+    Q.pop();
+    for(OutEdgeIt e(G,n);e!=INVALID;++e)
+      if(!visited[m=G.target(e)]) {
+	Q.push(m);
+	visited.set(m,true);
+      }
+  } while(!Q.empty());
+}
+
+template<class Graph>
+void bfsOwnQueue(Graph &G,typename Graph::Node source)
+{
+  GRAPH_TYPEDEF_FACTORY(Graph);
+
+  using namespace std;
+  
+  typename Graph::template NodeMap<bool> visited(G,false);
+  
+  int N=G.nodeNum();
+  vector<typename Graph::Node> Q(N);
+  int Qh=0;
+  int Qt=0;
+  
+
+  Q[Qh++]=source;
+  visited.set(source,true);
+  do {
+    Node m;
+    Node n=Q[Qt++];
+    for(OutEdgeIt e(G,n);e!=INVALID;++e)
+      if(!visited[m=G.target(e)]) {
+	Q[Qh++]=m;
+	visited.set(m,true);
+      }
+  } while(Qt!=Qh);
+}
+
+template<class Graph>
+void iteratorBench(Graph &G)
+{
+  GRAPH_TYPEDEF_FACTORY(Graph);
+
+  int i=0;
+  
+  for(NodeIt n(G);n!=INVALID;++n)
+    for(OutEdgeIt e(G,n);e!=INVALID;++e)
+      i++;
+}
+
+int main(int argc, char *argv[])
+{
+  typedef SmartGraph Graph;
+
+  ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
+  GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
+
+  Graph G;
+  
+  Timer T;
+  
+  if(argc!=3) {
+    cout << "Usage: " << argv[0] << " dim mul\n";
+    return 1;
+  }
+  
+  int dim=atoi(argv[1]);
+  int mul=atoi(argv[2]);
+  
+//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
+//        << dim*(1<<dim) << " edges):";
+
+  T.reset();
+  vector<Node> nodes;
+  addBiDirHiperCube(G,dim,nodes);
+
+  PrintTime("GENGRAPH",T);
+
+  T.reset();
+  {
+    for(int i=0;i<mul;i++)
+      bfsStlQueue(G,nodes[0]);
+  }
+  PrintTime("BFS-STL",T);
+  T.reset();
+  {
+    for(int i=0;i<mul;i++)
+      bfsOwnQueue(G,nodes[0]);
+  }
+  PrintTime("BFS-OWN",T);
+  T.reset();
+  {
+    for(int i=0;i<mul;i++)
+      iteratorBench(G);
+  }
+  PrintTime("ITERATE",T);
+
+
+}