COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/hcube.cc @ 711:b6c56353832c

Last change on this file since 711:b6c56353832c was 711:b6c56353832c, checked in by Alpar Juttner, 20 years ago

Some tools of common usage was put to bench_tool.h

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