COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/hcube.cc @ 718:75d36edc6bc4

Last change on this file since 718:75d36edc6bc4 was 718:75d36edc6bc4, checked in by Alpar Juttner, 16 years ago

Ready to run the first test series.

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