COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/hcube.cc @ 945:f2ea4aac9ada

Last change on this file since 945:f2ea4aac9ada was 921:818510fa3d99, checked in by Alpar Juttner, 20 years ago

hugo -> lemon

File size: 1.9 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    Edge te;
70    for(int i=0;i<dim*(1<<dim);i++) {
71      te.setToId(((long long int)(i)*93505)%(dim*(1<<dim)));
72      //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
73      map[te]=P();
74    }
75   
76//     for(int i=0;i<(1<<dim);i++) {
77//       int mul= (1<<(numOfZeros(i,dim)/4));
78//       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
79//      map[e]*=mul;
80//     }
81  }
82 
83  PrintTime("GENLENGTHS",T);
84
85  T.reset();
86  {
87    Dijkstra<Graph> Dij(G,map);
88    for(int i=0;i<10;i++)
89      Dij.run(nodes[0]);
90  }
91  PrintTime("DIJKSTRA",T);
92
93  T.reset();
94  {
95   Graph::EdgeMap<int> flow(G);
96   
97    Preflow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
98    for(int i=0;i<10;i++)
99      MF.run(MF.NO_FLOW);
100  }
101  PrintTime("PREFLOW",T);
102
103}
Note: See TracBrowser for help on using the repository browser.