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