COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/hcube.cc @ 967:6563019430ba

Last change on this file since 967:6563019430ba was 946:c94ef40a22ce, checked in by Mihaly Barasz, 20 years ago

The graph_factory branch (@ 1321) has been merged to trunk.

File size: 2.0 KB
Line 
1// -*- mode:C++ -*-
2
3#include<math.h>
4#include<lemon/list_graph.h>
5#include<lemon/smart_graph.h>
6#include<lemon/dijkstra.h>
7#include<lemon/preflow.h>
8
9#include"bench_tools.h"
10
11using namespace std;
12using namespace lemon;
13
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
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 
53//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
54//        << dim*(1<<dim) << " edges):";
55
56  T.reset();
57  vector<Node> nodes;
58  addBiDirHiperCube(G,dim,nodes);
59
60  PrintTime("GENGRAPH",T);
61
62  T.reset();
63  Graph::EdgeMap<int> map(G);
64  for(int i=0;i<5;i++) {
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
70    ///\todo It must have been commented out because of
71    ///setToId
72//     Edge te;
73//     for(int i=0;i<dim*(1<<dim);i++) {
74//       te.setToId(((long long int)(i)*93505)%(dim*(1<<dim)));
75//       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
76//       map[te]=P();
77//     }
78   
79//     for(int i=0;i<(1<<dim);i++) {
80//       int mul= (1<<(numOfZeros(i,dim)/4));
81//       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
82//      map[e]*=mul;
83//     }
84  }
85 
86  PrintTime("GENLENGTHS",T);
87
88  T.reset();
89  {
90    Dijkstra<Graph> Dij(G,map);
91    for(int i=0;i<10;i++)
92      Dij.run(nodes[0]);
93  }
94  PrintTime("DIJKSTRA",T);
95
96  T.reset();
97  {
98   Graph::EdgeMap<int> flow(G);
99   
100    Preflow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
101    for(int i=0;i<10;i++)
102      MF.run(MF.NO_FLOW);
103  }
104  PrintTime("PREFLOW",T);
105
106}
Note: See TracBrowser for help on using the repository browser.