COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/hcube.cc @ 801:48638058e188

Last change on this file since 801:48638058e188 was 742:235fd36336b7, checked in by Alpar Juttner, 20 years ago
  • bfs-bench added
  • hypercube generators moved to bench-tools.h
  • new benchmark script
File size: 1.8 KB
RevLine 
[708]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>
[729]7#include<hugo/max_flow.h>
8
[711]9#include"bench_tools.h"
[708]10
11using namespace std;
12using namespace hugo;
13
[718]14inline 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
24inline 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
[708]34int main(int argc, char *argv[])
35{
36  //  typedef ListGraph Graph;
37  typedef SmartGraph Graph;
38
39  ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
40  GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
41
42  Graph G;
43 
44  Timer T;
45 
46  if(argc!=2) {
47    cout << "Usage: " << argv[0] << " dim\n";
48    return 1;
49  }
50 
51  int dim=atoi(argv[1]);
52 
[718]53//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
54//        << dim*(1<<dim) << " edges):";
[708]55
[718]56  T.reset();
[708]57  vector<Node> nodes;
58  addBiDirHiperCube(G,dim,nodes);
[718]59
60  PrintTime("GENGRAPH",T);
61
[708]62  T.reset();
63  Graph::EdgeMap<int> map(G);
[729]64  for(int i=0;i<5;i++) {
[708]65    Primes P;
66    for(int i=0;i<dim*(1<<dim);i++) P();
67   
68    //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
69    for(int i=0;i<dim*(1<<dim);i++)
70      //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
71      map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
[718]72 
73//     for(int i=0;i<(1<<dim);i++) {
74//       int mul= (1<<(numOfZeros(i,dim)/4));
75//       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
76//      map[e]*=mul;
77//     }
[708]78  }
79 
[718]80  PrintTime("GENLENGTHS",T);
81
[708]82  T.reset();
83  {
84    Dijkstra<Graph> Dij(G,map);
[729]85    for(int i=0;i<10;i++)
86      Dij.run(nodes[0]);
[708]87  }
[718]88  PrintTime("DIJKSTRA",T);
89
90  T.reset();
91  {
92   Graph::EdgeMap<int> flow(G);
[708]93   
[729]94    MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
95    for(int i=0;i<10;i++)
96      MF.run(MF.NO_FLOW);
[718]97  }
98  PrintTime("PREFLOW",T);
99
[708]100}
Note: See TracBrowser for help on using the repository browser.