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