COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/hcube.cc @ 900:fc7bc2dacee5

Last change on this file since 900:fc7bc2dacee5 was 840:10002fa8847a, checked in by Alpar Juttner, 20 years ago

Change MaxFlow? to Preflow.

File size: 1.8 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/preflow.h>
8
9#include"bench_tools.h"
10
11using namespace std;
12using namespace hugo;
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    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();
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//     }
78  }
79 
80  PrintTime("GENLENGTHS",T);
81
82  T.reset();
83  {
84    Dijkstra<Graph> Dij(G,map);
85    for(int i=0;i<10;i++)
86      Dij.run(nodes[0]);
87  }
88  PrintTime("DIJKSTRA",T);
89
90  T.reset();
91  {
92   Graph::EdgeMap<int> flow(G);
93   
94    Preflow<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);
97  }
98  PrintTime("PREFLOW",T);
99
100}
Note: See TracBrowser for help on using the repository browser.