COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/hcube.cc @ 729:a9b1c49440f7

Last change on this file since 729:a9b1c49440f7 was 729:a9b1c49440f7, checked in by Alpar Juttner, 20 years ago

Repeat tests more times.

File size: 2.6 KB
Line 
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>
7#include<hugo/max_flow.h>
8
9#include"bench_tools.h"
10
11using namespace std;
12using namespace hugo;
13
14template<class Graph>
15void addHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
16{
17  GRAPH_TYPEDEF_FACTORY(Graph);
18 
19  vector<int> bits(dim+1);
20  bits[0]=1;
21  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
22 
23  for(int i=0;i<bits[dim];i++) {
24    nodes.push_back(G.addNode());
25    for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
26  }
27}
28
29template<class Graph>
30void addBiDirHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
31{
32  GRAPH_TYPEDEF_FACTORY(Graph);
33 
34  vector<int> bits(dim+1);
35  bits[0]=1;
36  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
37 
38  for(int i=0;i<bits[dim];i++) {
39    nodes.push_back(G.addNode());
40    for(int j=0;j<dim;j++) if(i&bits[j]) {
41      G.addEdge(nodes[i-bits[j]],nodes[i]);
42      G.addEdge(nodes[i],nodes[i-bits[j]]);
43    }
44   
45  }
46}
47
48inline int numOfOnes(int n,int dim)
49{
50  int s=0;
51  for(int i=0;i<dim;i++) {
52    s+=n%2;
53    n>>=1;
54  }
55  return s;
56}
57
58inline int numOfZeros(int n,int dim)
59{
60  int s=dim;
61  for(int i=0;i<dim;i++) {
62    s-=n&1;
63    n>>=1;
64  }
65  return s;
66}
67
68int main(int argc, char *argv[])
69{
70  //  typedef ListGraph Graph;
71  typedef SmartGraph Graph;
72
73  ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
74  GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
75
76  Graph G;
77 
78  Timer T;
79 
80  if(argc!=2) {
81    cout << "Usage: " << argv[0] << " dim\n";
82    return 1;
83  }
84 
85  int dim=atoi(argv[1]);
86 
87//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
88//        << dim*(1<<dim) << " edges):";
89
90  T.reset();
91  vector<Node> nodes;
92  addBiDirHiperCube(G,dim,nodes);
93
94  PrintTime("GENGRAPH",T);
95
96  T.reset();
97  Graph::EdgeMap<int> map(G);
98  for(int i=0;i<5;i++) {
99    Primes P;
100    for(int i=0;i<dim*(1<<dim);i++) P();
101   
102    //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
103    for(int i=0;i<dim*(1<<dim);i++)
104      //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
105      map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
106 
107//     for(int i=0;i<(1<<dim);i++) {
108//       int mul= (1<<(numOfZeros(i,dim)/4));
109//       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
110//      map[e]*=mul;
111//     }
112  }
113 
114  PrintTime("GENLENGTHS",T);
115
116  T.reset();
117  {
118    Dijkstra<Graph> Dij(G,map);
119    for(int i=0;i<10;i++)
120      Dij.run(nodes[0]);
121  }
122  PrintTime("DIJKSTRA",T);
123
124  T.reset();
125  {
126   Graph::EdgeMap<int> flow(G);
127   
128    MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
129    for(int i=0;i<10;i++)
130      MF.run(MF.NO_FLOW);
131  }
132  PrintTime("PREFLOW",T);
133
134}
Note: See TracBrowser for help on using the repository browser.