COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/hcube.cc @ 1894:f794a0bb40c9

Last change on this file since 1894:f794a0bb40c9 was 1847:7cbc12e42482, checked in by Alpar Juttner, 18 years ago
  • Changed and improved Timer interface
    • several new member functions
    • reset() -> restart() renaming
    • TimeReport?: a Timer that prints a report on destruction.
  • counter.h: a tool to measure the number of streps of algorithms.
  • New documentation module for time measuring and counting.
File size: 1.9 KB
Line 
1// -*- mode:C++ -*-
2
3#include<cmath>
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  GRAPH_TYPEDEFS(Graph);
40
41  Graph G;
42 
43  Timer T;
44 
45  if(argc!=2) {
46    cout << "Usage: " << argv[0] << " dim\n";
47    return 1;
48  }
49 
50  int dim=atoi(argv[1]);
51 
52//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
53//        << dim*(1<<dim) << " edges):";
54
55  T.restart();
56  vector<Node> nodes;
57  addBiDirHyperCube(G,dim,nodes);
58
59  PrintTime("GENGRAPH",T);
60
61  T.restart();
62  Graph::EdgeMap<int> map(G);
63  for(int i=0;i<5;i++) {
64    Primes P;
65    for(int i=0;i<dim*(1<<dim);i++) P();
66   
67    //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
68
69    ///\todo It must have been commented out because of
70    ///setToId
71//     Edge te;
72//     for(int i=0;i<dim*(1<<dim);i++) {
73//       te.setToId(((long long int)(i)*93505)%(dim*(1<<dim)));
74//       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
75//       map[te]=P();
76//     }
77   
78//     for(int i=0;i<(1<<dim);i++) {
79//       int mul= (1<<(numOfZeros(i,dim)/4));
80//       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
81//      map[e]*=mul;
82//     }
83  }
84 
85  PrintTime("GENLENGTHS",T);
86
87  T.restart();
88  {
89    Dijkstra<Graph> Dij(G,map);
90    for(int i=0;i<10;i++)
91      Dij.run(nodes[0]);
92  }
93  PrintTime("DIJKSTRA",T);
94
95  T.restart();
96  {
97   Graph::EdgeMap<int> flow(G);
98   
99    Preflow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
100    for(int i=0;i<10;i++)
101      MF.run(MF.NO_FLOW);
102  }
103  PrintTime("PREFLOW",T);
104
105}
Note: See TracBrowser for help on using the repository browser.