alpar@708
|
1 |
// -*- mode:C++ -*-
|
alpar@708
|
2 |
|
alpar@708
|
3 |
#include<math.h>
|
alpar@708
|
4 |
#include<hugo/list_graph.h>
|
alpar@708
|
5 |
#include<hugo/smart_graph.h>
|
alpar@708
|
6 |
#include<hugo/dijkstra.h>
|
alpar@729
|
7 |
#include<hugo/max_flow.h>
|
alpar@729
|
8 |
|
alpar@711
|
9 |
#include"bench_tools.h"
|
alpar@708
|
10 |
|
alpar@708
|
11 |
using namespace std;
|
alpar@708
|
12 |
using namespace hugo;
|
alpar@708
|
13 |
|
alpar@708
|
14 |
template<class Graph>
|
alpar@708
|
15 |
void addHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
|
alpar@708
|
16 |
{
|
alpar@708
|
17 |
GRAPH_TYPEDEF_FACTORY(Graph);
|
alpar@708
|
18 |
|
alpar@708
|
19 |
vector<int> bits(dim+1);
|
alpar@708
|
20 |
bits[0]=1;
|
alpar@708
|
21 |
for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
|
alpar@708
|
22 |
|
alpar@708
|
23 |
for(int i=0;i<bits[dim];i++) {
|
alpar@708
|
24 |
nodes.push_back(G.addNode());
|
alpar@718
|
25 |
for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
|
alpar@708
|
26 |
}
|
alpar@708
|
27 |
}
|
alpar@708
|
28 |
|
alpar@708
|
29 |
template<class Graph>
|
alpar@708
|
30 |
void addBiDirHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
|
alpar@708
|
31 |
{
|
alpar@708
|
32 |
GRAPH_TYPEDEF_FACTORY(Graph);
|
alpar@708
|
33 |
|
alpar@708
|
34 |
vector<int> bits(dim+1);
|
alpar@708
|
35 |
bits[0]=1;
|
alpar@708
|
36 |
for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
|
alpar@708
|
37 |
|
alpar@708
|
38 |
for(int i=0;i<bits[dim];i++) {
|
alpar@708
|
39 |
nodes.push_back(G.addNode());
|
alpar@708
|
40 |
for(int j=0;j<dim;j++) if(i&bits[j]) {
|
alpar@708
|
41 |
G.addEdge(nodes[i-bits[j]],nodes[i]);
|
alpar@708
|
42 |
G.addEdge(nodes[i],nodes[i-bits[j]]);
|
alpar@708
|
43 |
}
|
alpar@708
|
44 |
|
alpar@708
|
45 |
}
|
alpar@708
|
46 |
}
|
alpar@708
|
47 |
|
alpar@718
|
48 |
inline int numOfOnes(int n,int dim)
|
alpar@718
|
49 |
{
|
alpar@718
|
50 |
int s=0;
|
alpar@718
|
51 |
for(int i=0;i<dim;i++) {
|
alpar@718
|
52 |
s+=n%2;
|
alpar@718
|
53 |
n>>=1;
|
alpar@718
|
54 |
}
|
alpar@718
|
55 |
return s;
|
alpar@718
|
56 |
}
|
alpar@718
|
57 |
|
alpar@718
|
58 |
inline int numOfZeros(int n,int dim)
|
alpar@718
|
59 |
{
|
alpar@718
|
60 |
int s=dim;
|
alpar@718
|
61 |
for(int i=0;i<dim;i++) {
|
alpar@718
|
62 |
s-=n&1;
|
alpar@718
|
63 |
n>>=1;
|
alpar@718
|
64 |
}
|
alpar@718
|
65 |
return s;
|
alpar@718
|
66 |
}
|
alpar@718
|
67 |
|
alpar@708
|
68 |
int main(int argc, char *argv[])
|
alpar@708
|
69 |
{
|
alpar@708
|
70 |
// typedef ListGraph Graph;
|
alpar@708
|
71 |
typedef SmartGraph Graph;
|
alpar@708
|
72 |
|
alpar@708
|
73 |
///\bug GRAPH_TYPEDEF_FACTORY(Graph);
|
alpar@708
|
74 |
GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
|
alpar@708
|
75 |
|
alpar@708
|
76 |
Graph G;
|
alpar@708
|
77 |
|
alpar@708
|
78 |
Timer T;
|
alpar@708
|
79 |
|
alpar@708
|
80 |
if(argc!=2) {
|
alpar@708
|
81 |
cout << "Usage: " << argv[0] << " dim\n";
|
alpar@708
|
82 |
return 1;
|
alpar@708
|
83 |
}
|
alpar@708
|
84 |
|
alpar@708
|
85 |
int dim=atoi(argv[1]);
|
alpar@708
|
86 |
|
alpar@718
|
87 |
// cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
|
alpar@718
|
88 |
// << dim*(1<<dim) << " edges):";
|
alpar@708
|
89 |
|
alpar@718
|
90 |
T.reset();
|
alpar@708
|
91 |
vector<Node> nodes;
|
alpar@708
|
92 |
addBiDirHiperCube(G,dim,nodes);
|
alpar@718
|
93 |
|
alpar@718
|
94 |
PrintTime("GENGRAPH",T);
|
alpar@718
|
95 |
|
alpar@708
|
96 |
T.reset();
|
alpar@708
|
97 |
Graph::EdgeMap<int> map(G);
|
alpar@729
|
98 |
for(int i=0;i<5;i++) {
|
alpar@708
|
99 |
Primes P;
|
alpar@708
|
100 |
for(int i=0;i<dim*(1<<dim);i++) P();
|
alpar@708
|
101 |
|
alpar@708
|
102 |
// for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
|
alpar@708
|
103 |
for(int i=0;i<dim*(1<<dim);i++)
|
alpar@708
|
104 |
// map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
|
alpar@708
|
105 |
map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
|
alpar@718
|
106 |
|
alpar@718
|
107 |
// for(int i=0;i<(1<<dim);i++) {
|
alpar@718
|
108 |
// int mul= (1<<(numOfZeros(i,dim)/4));
|
alpar@718
|
109 |
// for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
|
alpar@718
|
110 |
// map[e]*=mul;
|
alpar@718
|
111 |
// }
|
alpar@708
|
112 |
}
|
alpar@708
|
113 |
|
alpar@718
|
114 |
PrintTime("GENLENGTHS",T);
|
alpar@718
|
115 |
|
alpar@708
|
116 |
T.reset();
|
alpar@708
|
117 |
{
|
alpar@708
|
118 |
Dijkstra<Graph> Dij(G,map);
|
alpar@729
|
119 |
for(int i=0;i<10;i++)
|
alpar@729
|
120 |
Dij.run(nodes[0]);
|
alpar@708
|
121 |
}
|
alpar@718
|
122 |
PrintTime("DIJKSTRA",T);
|
alpar@718
|
123 |
|
alpar@718
|
124 |
T.reset();
|
alpar@718
|
125 |
{
|
alpar@718
|
126 |
Graph::EdgeMap<int> flow(G);
|
alpar@708
|
127 |
|
alpar@729
|
128 |
MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
|
alpar@729
|
129 |
for(int i=0;i<10;i++)
|
alpar@729
|
130 |
MF.run(MF.NO_FLOW);
|
alpar@718
|
131 |
}
|
alpar@718
|
132 |
PrintTime("PREFLOW",T);
|
alpar@718
|
133 |
|
alpar@708
|
134 |
}
|