COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/hcube.cc @ 2514:57143c09dc20

Last change on this file since 2514:57143c09dc20 was 2514:57143c09dc20, checked in by Balazs Dezso, 17 years ago

Redesign the maximum flow algorithms

Redesigned interface
Preflow changed to use elevator
Edmonds-Karp does not use the ResGraphAdaptor?
Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)

File size: 2.5 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include<cmath>
20#include<lemon/list_graph.h>
21#include<lemon/smart_graph.h>
22#include<lemon/dijkstra.h>
23#include<lemon/preflow.h>
24
25#include"bench_tools.h"
26
27using namespace std;
28using namespace lemon;
29
30inline int numOfOnes(int n,int dim)
31{
32  int s=0;
33  for(int i=0;i<dim;i++) {
34    s+=n%2;
35    n>>=1;
36  }
37  return s;
38}
39
40inline int numOfZeros(int n,int dim)
41{
42  int s=dim;
43  for(int i=0;i<dim;i++) {
44    s-=n&1;
45    n>>=1;
46  }
47  return s;
48}
49
50int main(int argc, char *argv[])
51{
52  //  typedef ListGraph Graph;
53  typedef SmartGraph Graph;
54
55  GRAPH_TYPEDEFS(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  T.restart();
72  vector<Node> nodes;
73  addBiDirHyperCube(G,dim,nodes);
74
75  PrintTime("GENGRAPH",T);
76
77  T.restart();
78  Graph::EdgeMap<int> map(G);
79  for(int i=0;i<5;i++) {
80    Primes P;
81    for(int j=0;j<dim*(1<<dim);j++) P();
82   
83    //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
84
85    ///\todo It must have been commented out because of
86    ///setToId
87//     Edge te;
88//     for(int i=0;i<dim*(1<<dim);i++) {
89//       te.setToId(((long long int)(i)*93505)%(dim*(1<<dim)));
90//       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
91//       map[te]=P();
92//     }
93   
94//     for(int i=0;i<(1<<dim);i++) {
95//       int mul= (1<<(numOfZeros(i,dim)/4));
96//       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
97//      map[e]*=mul;
98//     }
99  }
100 
101  PrintTime("GENLENGTHS",T);
102
103  T.restart();
104  {
105    Dijkstra<Graph> Dij(G,map);
106    for(int i=0;i<10;i++)
107      Dij.run(nodes[0]);
108  }
109  PrintTime("DIJKSTRA",T);
110
111  T.restart();
112  {
113   Graph::EdgeMap<int> flow(G);
114   
115    Preflow<Graph> MF(G,map,nodes[0],nodes[1<<dim-1]);
116    for(int i=0;i<10;i++)
117      MF.run();
118  }
119  PrintTime("PREFLOW",T);
120
121}
Note: See TracBrowser for help on using the repository browser.