More documented file.
4 #include<hugo/list_graph.h>
5 #include<hugo/smart_graph.h>
6 #include<hugo/dijkstra.h>
7 #include<../work/jacint/max_flow_no_stack.h>
8 #include"bench_tools.h"
14 void addHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
16 GRAPH_TYPEDEF_FACTORY(Graph);
18 vector<int> bits(dim+1);
20 for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
22 for(int i=0;i<bits[dim];i++) {
23 nodes.push_back(G.addNode());
24 for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
29 void addBiDirHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
31 GRAPH_TYPEDEF_FACTORY(Graph);
33 vector<int> bits(dim+1);
35 for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
37 for(int i=0;i<bits[dim];i++) {
38 nodes.push_back(G.addNode());
39 for(int j=0;j<dim;j++) if(i&bits[j]) {
40 G.addEdge(nodes[i-bits[j]],nodes[i]);
41 G.addEdge(nodes[i],nodes[i-bits[j]]);
47 inline int numOfOnes(int n,int dim)
50 for(int i=0;i<dim;i++) {
57 inline int numOfZeros(int n,int dim)
60 for(int i=0;i<dim;i++) {
67 int main(int argc, char *argv[])
69 // typedef ListGraph Graph;
70 typedef SmartGraph Graph;
72 ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
73 GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
80 cout << "Usage: " << argv[0] << " dim\n";
84 int dim=atoi(argv[1]);
86 // cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
87 // << dim*(1<<dim) << " edges):";
91 addBiDirHiperCube(G,dim,nodes);
93 PrintTime("GENGRAPH",T);
96 Graph::EdgeMap<int> map(G);
99 for(int i=0;i<dim*(1<<dim);i++) P();
101 // for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
102 for(int i=0;i<dim*(1<<dim);i++)
103 // map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
104 map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
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))
113 PrintTime("GENLENGTHS",T);
117 Dijkstra<Graph> Dij(G,map);
120 PrintTime("DIJKSTRA",T);
124 Graph::EdgeMap<int> flow(G);
126 MaxFlowNoStack<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
129 PrintTime("PREFLOW",T);