alpar@708: // -*- mode:C++ -*-
alpar@708: 
alpar@708: #include<math.h>
alpar@708: #include<hugo/list_graph.h>
alpar@708: #include<hugo/smart_graph.h>
alpar@708: #include<hugo/dijkstra.h>
alpar@718: #include<../work/jacint/max_flow_no_stack.h>
alpar@711: #include"bench_tools.h"
alpar@708: 
alpar@708: using namespace std;
alpar@708: using namespace hugo;
alpar@708: 
alpar@708: template<class Graph>
alpar@708: void addHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
alpar@708: {
alpar@708:   GRAPH_TYPEDEF_FACTORY(Graph);
alpar@708:   
alpar@708:   vector<int> bits(dim+1);
alpar@708:   bits[0]=1;
alpar@708:   for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
alpar@708:   
alpar@708:   for(int i=0;i<bits[dim];i++) {
alpar@708:     nodes.push_back(G.addNode());
alpar@718:     for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
alpar@708:   }
alpar@708: }
alpar@708: 
alpar@708: template<class Graph>
alpar@708: void addBiDirHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)
alpar@708: {
alpar@708:   GRAPH_TYPEDEF_FACTORY(Graph);
alpar@708:   
alpar@708:   vector<int> bits(dim+1);
alpar@708:   bits[0]=1;
alpar@708:   for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
alpar@708:   
alpar@708:   for(int i=0;i<bits[dim];i++) {
alpar@708:     nodes.push_back(G.addNode());
alpar@708:     for(int j=0;j<dim;j++) if(i&bits[j]) {
alpar@708:       G.addEdge(nodes[i-bits[j]],nodes[i]);
alpar@708:       G.addEdge(nodes[i],nodes[i-bits[j]]);
alpar@708:     }
alpar@708:     
alpar@708:   }
alpar@708: }
alpar@708: 
alpar@718: inline int numOfOnes(int n,int dim)
alpar@718: {
alpar@718:   int s=0;
alpar@718:   for(int i=0;i<dim;i++) {
alpar@718:     s+=n%2;
alpar@718:     n>>=1;
alpar@718:   }
alpar@718:   return s;
alpar@718: }
alpar@718: 
alpar@718: inline int numOfZeros(int n,int dim)
alpar@718: {
alpar@718:   int s=dim;
alpar@718:   for(int i=0;i<dim;i++) {
alpar@718:     s-=n&1;
alpar@718:     n>>=1;
alpar@718:   }
alpar@718:   return s;
alpar@718: }
alpar@718: 
alpar@708: int main(int argc, char *argv[])
alpar@708: {
alpar@708:   //  typedef ListGraph Graph;
alpar@708:   typedef SmartGraph Graph;
alpar@708: 
alpar@708:   ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
alpar@708:   GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
alpar@708: 
alpar@708:   Graph G;
alpar@708:   
alpar@708:   Timer T;
alpar@708:   
alpar@708:   if(argc!=2) {
alpar@708:     cout << "Usage: " << argv[0] << " dim\n";
alpar@708:     return 1;
alpar@708:   }
alpar@708:   
alpar@708:   int dim=atoi(argv[1]);
alpar@708:   
alpar@718: //   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
alpar@718: //        << dim*(1<<dim) << " edges):";
alpar@708: 
alpar@718:   T.reset();
alpar@708:   vector<Node> nodes;
alpar@708:   addBiDirHiperCube(G,dim,nodes);
alpar@718: 
alpar@718:   PrintTime("GENGRAPH",T);
alpar@718: 
alpar@708:   T.reset();
alpar@708:   Graph::EdgeMap<int> map(G);
alpar@708:   {
alpar@708:     Primes P;
alpar@708:     for(int i=0;i<dim*(1<<dim);i++) P();
alpar@708:     
alpar@708:     //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
alpar@708:     for(int i=0;i<dim*(1<<dim);i++)
alpar@708:       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
alpar@708:       map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();
alpar@718:   
alpar@718: //     for(int i=0;i<(1<<dim);i++) {
alpar@718: //       int mul= (1<<(numOfZeros(i,dim)/4));
alpar@718: //       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))
alpar@718: // 	map[e]*=mul;
alpar@718: //     }
alpar@708:   }
alpar@708:   
alpar@718:   PrintTime("GENLENGTHS",T);
alpar@718: 
alpar@708:   T.reset();
alpar@708:   {
alpar@708:     Dijkstra<Graph> Dij(G,map);
alpar@708:     Dij.run(nodes[0]);
alpar@708:   }
alpar@718:   PrintTime("DIJKSTRA",T);
alpar@718: 
alpar@718:   T.reset();
alpar@718:   {
alpar@718:    Graph::EdgeMap<int> flow(G);
alpar@708:    
alpar@718:     MaxFlowNoStack<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
alpar@718:     MF.run(MF.NO_FLOW);
alpar@718:   }
alpar@718:   PrintTime("PREFLOW",T);
alpar@718: 
alpar@708: }