COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/hcube.cc @ 1768:1e2e0238e7c8

Last change on this file since 1768:1e2e0238e7c8 was 1756:b1f441f24d08, checked in by Alpar Juttner, 19 years ago

GRAPH_TYPEDEFS and UNDIRGRAPH_TYPEDEFS macros added to graph_utils.h.

File size: 1.9 KB
RevLine 
[708]1// -*- mode:C++ -*-
2
[1632]3#include<cmath>
[921]4#include<lemon/list_graph.h>
5#include<lemon/smart_graph.h>
6#include<lemon/dijkstra.h>
7#include<lemon/preflow.h>
[729]8
[711]9#include"bench_tools.h"
[708]10
11using namespace std;
[921]12using namespace lemon;
[708]13
[718]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
[708]34int main(int argc, char *argv[])
35{
36  //  typedef ListGraph Graph;
37  typedef SmartGraph Graph;
38
[1756]39  GRAPH_TYPEDEFS(Graph);
[708]40
41  Graph G;
42 
43  Timer T;
44 
45  if(argc!=2) {
46    cout << "Usage: " << argv[0] << " dim\n";
47    return 1;
48  }
49 
50  int dim=atoi(argv[1]);
51 
[718]52//   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
53//        << dim*(1<<dim) << " edges):";
[708]54
[718]55  T.reset();
[708]56  vector<Node> nodes;
[1689]57  addBiDirHyperCube(G,dim,nodes);
[718]58
59  PrintTime("GENGRAPH",T);
60
[708]61  T.reset();
62  Graph::EdgeMap<int> map(G);
[729]63  for(int i=0;i<5;i++) {
[708]64    Primes P;
65    for(int i=0;i<dim*(1<<dim);i++) P();
66   
67    //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
[946]68
69    ///\todo It must have been commented out because of
70    ///setToId
71//     Edge te;
72//     for(int i=0;i<dim*(1<<dim);i++) {
73//       te.setToId(((long long int)(i)*93505)%(dim*(1<<dim)));
74//       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
75//       map[te]=P();
76//     }
[905]77   
[718]78//     for(int i=0;i<(1<<dim);i++) {
79//       int mul= (1<<(numOfZeros(i,dim)/4));
80//       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
81//      map[e]*=mul;
82//     }
[708]83  }
84 
[718]85  PrintTime("GENLENGTHS",T);
86
[708]87  T.reset();
88  {
89    Dijkstra<Graph> Dij(G,map);
[729]90    for(int i=0;i<10;i++)
91      Dij.run(nodes[0]);
[708]92  }
[718]93  PrintTime("DIJKSTRA",T);
94
95  T.reset();
96  {
97   Graph::EdgeMap<int> flow(G);
[708]98   
[840]99    Preflow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
[729]100    for(int i=0;i<10;i++)
101      MF.run(MF.NO_FLOW);
[718]102  }
103  PrintTime("PREFLOW",T);
104
[708]105}
Note: See TracBrowser for help on using the repository browser.