Changeset 742:235fd36336b7 in lemon-0.x for src/benchmark/bench_tools.h

Timestamp:

07/27/04 18:09:42 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@999

Message:

• bfs-bench added
• hypercube generators moved to bench-tools.h
• new benchmark script

File:

• src/benchmark/bench_tools.h (modified) (1 diff)

src/benchmark/bench_tools.h

@@ -82 +82 @@
 }
 
+
+
+///
+template<class Graph>
+void addHiperCube(Graph &G,int dim,std::vector<typename Graph::Node> &nodes)
+{
+  GRAPH_TYPEDEF_FACTORY(Graph);
   
+  std::vector<int> bits(dim+1);
+  bits[0]=1;
+  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
+  
+  for(int i=0;i<bits[dim];i++) {
+    nodes.push_back(G.addNode());
+    for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
+  }
+}
+
+///
+template<class Graph>
+void addBiDirHiperCube(Graph &G,int dim,std::vector<typename Graph::Node>&nodes)
+{
+  GRAPH_TYPEDEF_FACTORY(Graph);
+  
+  std::vector<int> bits(dim+1);
+  bits[0]=1;
+  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
+  
+  for(int i=0;i<bits[dim];i++) {
+    nodes.push_back(G.addNode());
+    for(int j=0;j<dim;j++) if(i&bits[j]) {
+      G.addEdge(nodes[i-bits[j]],nodes[i]);
+      G.addEdge(nodes[i],nodes[i-bits[j]]);
+    }
+    
+  }
+}  
 
 #endif