COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/hcube.cc @ 708:429dfcbbf47d

Last change on this file since 708:429dfcbbf47d was 708:429dfcbbf47d, checked in by Alpar Juttner, 16 years ago

A new benchmark (hcube)
and other minor changes

File size: 3.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
11using namespace std;
12using namespace hugo;
13
14///An experimental typedef factory
15#define GRAPH_TYPEDEF_FACTORY(Graph) \
16   typedef typename Graph::   Node      Node;\
17   typedef typename Graph::   NodeIt    NodeIn;\
18   typedef typename Graph::   Edge      Edge;\
19   typedef typename Graph::   EdgeIt    EdgeIt;\
20   typedef typename Graph:: InEdgeIt  InEdgeIt;\
21   typedef typename Graph::OutEdgeIt OutEdgeIt;
22
23#define GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph) \
24   typedef Graph::   Node      Node;\
25   typedef Graph::   NodeIt    NodeIn;\
26   typedef Graph::   Edge      Edge;\
27   typedef Graph::   EdgeIt    EdgeIt;\
28   typedef Graph:: InEdgeIt  InEdgeIt;\
29   typedef Graph::OutEdgeIt OutEdgeIt;
30
31
32class Primes
33{
34  vector<int> primes;
35  int n;
36 
37  bool isPrime(int m)
38  {
39    for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false;
40    return true;
41  }
42public:
43  Primes() : n(1) {}
44 
45  int operator() ()
46    {
47      if(primes.size()==0) {
48        primes.push_back(2);
49        return 2;
50      }
51      else {
52        do n+=2; while(!isPrime(n));
53        primes.push_back(n);
54        return n;
55      }
56    }
57};
58
59template<class Graph>
60void addHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
61{
62  GRAPH_TYPEDEF_FACTORY(Graph);
63 
64  vector<int> bits(dim+1);
65  bits[0]=1;
66  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
67 
68  for(int i=0;i<bits[dim];i++) {
69    nodes.push_back(G.addNode());
70    for(j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
71  }
72}
73
74template<class Graph>
75void addBiDirHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
76{
77  GRAPH_TYPEDEF_FACTORY(Graph);
78 
79  vector<int> bits(dim+1);
80  bits[0]=1;
81  for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
82 
83  for(int i=0;i<bits[dim];i++) {
84    nodes.push_back(G.addNode());
85    for(int j=0;j<dim;j++) if(i&bits[j]) {
86      G.addEdge(nodes[i-bits[j]],nodes[i]);
87      G.addEdge(nodes[i],nodes[i-bits[j]]);
88    }
89   
90  }
91}
92
93int main(int argc, char *argv[])
94{
95  //  typedef ListGraph Graph;
96  typedef SmartGraph Graph;
97
98  ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
99  GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
100
101  Graph G;
102 
103  Timer T;
104 
105  if(argc!=2) {
106    cout << "Usage: " << argv[0] << " dim\n";
107    return 1;
108  }
109 
110  int dim=atoi(argv[1]);
111 
112  cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
113       << dim*(1<<dim) << " edges):";
114
115  vector<Node> nodes;
116  addBiDirHiperCube(G,dim,nodes);
117  cout << T;
118  cout << "\nGenerating the lengths: ";
119  T.reset();
120  Graph::EdgeMap<int> map(G);
121  {
122    Primes P;
123    for(int i=0;i<dim*(1<<dim);i++) P();
124   
125    //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
126    for(int i=0;i<dim*(1<<dim);i++)
127      //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
128      map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
129  }
130 
131  cout << T;
132  cout << "\nRunning Dijkstra: ";
133  T.reset();
134  {
135    Dijkstra<Graph> Dij(G,map);
136    Dij.run(nodes[0]);
137  }
138  cout << T;
139//   cout << "\nRunning MaxFlow: ";
140//   T.reset();
141//   {
142//    Graph::EdgeMap<int> flow(G);
143   
144//     MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
145//     MF.run(MF.NO_FLOW);
146//   }
147//   cout << T;
148  cout << "\n";
149}
Note: See TracBrowser for help on using the repository browser.