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@708: #include<hugo/time_measure.h>
alpar@708: #include<iostream>
alpar@711: //#include<../work/jacint/max_flow.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@708:     for(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@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@708:   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
alpar@708:        << dim*(1<<dim) << " edges):";
alpar@708: 
alpar@708:   vector<Node> nodes;
alpar@708:   addBiDirHiperCube(G,dim,nodes);
alpar@708:   cout << T;
alpar@708:   cout << "\nGenerating the lengths: ";
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@708:   }
alpar@708:   
alpar@708:   cout << T;
alpar@708:   cout << "\nRunning Dijkstra: ";
alpar@708:   T.reset();
alpar@708:   {
alpar@708:     Dijkstra<Graph> Dij(G,map);
alpar@708:     Dij.run(nodes[0]);
alpar@708:   }
alpar@708:   cout << T;
alpar@708: //   cout << "\nRunning MaxFlow: ";
alpar@708: //   T.reset();
alpar@708: //   {
alpar@708: //    Graph::EdgeMap<int> flow(G);
alpar@708:    
alpar@708: //     MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);
alpar@708: //     MF.run(MF.NO_FLOW);
alpar@708: //   }
alpar@708: //   cout << T;
alpar@708:   cout << "\n";
alpar@708: }