// -*- mode:C++ -*-

 #include<math.h>

 #include<hugo/list_graph.h>

 #include<hugo/smart_graph.h>

 #include<hugo/dijkstra.h>

 #include<hugo/time_measure.h>

 #include<iostream>

 #include<../work/jacint/max_flow.h>

 using namespace std;

 using namespace hugo;

 ///An experimental typedef factory

 #define GRAPH_TYPEDEF_FACTORY(Graph) \

    typedef typename Graph::   Node      Node;\

    typedef typename Graph::   NodeIt    NodeIn;\

    typedef typename Graph::   Edge      Edge;\

    typedef typename Graph::   EdgeIt    EdgeIt;\

    typedef typename Graph:: InEdgeIt  InEdgeIt;\

    typedef typename Graph::OutEdgeIt OutEdgeIt;

 #define GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph) \

    typedef Graph::   Node      Node;\

    typedef Graph::   NodeIt    NodeIn;\

    typedef Graph::   Edge      Edge;\

    typedef Graph::   EdgeIt    EdgeIt;\

    typedef Graph:: InEdgeIt  InEdgeIt;\

    typedef Graph::OutEdgeIt OutEdgeIt;

 class Primes 

 {

   vector<int> primes;

   int n;

   bool isPrime(int m) 

   {

     for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false;

     return true;

   }

 public:

   Primes() : n(1) {}

   int operator() ()

     {

       if(primes.size()==0) {

 	primes.push_back(2);

 	return 2;

       }

       else {

 	do n+=2; while(!isPrime(n));

 	primes.push_back(n);

 	return n;

       }

     }

 };

 template<class Graph>

 void addHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)

 {

   GRAPH_TYPEDEF_FACTORY(Graph);

   vector<int> bits(dim+1);

   bits[0]=1;

   for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];

   for(int i=0;i<bits[dim];i++) {

     nodes.push_back(G.addNode());

     for(j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);

   }

 }

 template<class Graph>

 void addBiDirHiperCube(Graph &G,int dim,vector<typename Graph::Node> &nodes)

 {

   GRAPH_TYPEDEF_FACTORY(Graph);

   vector<int> bits(dim+1);

   bits[0]=1;

   for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];

   for(int i=0;i<bits[dim];i++) {

     nodes.push_back(G.addNode());

     for(int j=0;j<dim;j++) if(i&bits[j]) {

       G.addEdge(nodes[i-bits[j]],nodes[i]);

       G.addEdge(nodes[i],nodes[i-bits[j]]);

     }

   }

 }

 int main(int argc, char *argv[])

 {

   //  typedef ListGraph Graph;

   typedef SmartGraph Graph;

   ///\bug GRAPH_TYPEDEF_FACTORY(Graph);

   GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);

   Graph G;

   Timer T;

   if(argc!=2) {

     cout << "Usage: " << argv[0] << " dim\n";

     return 1;

   }

   int dim=atoi(argv[1]);

   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "

        << dim*(1<<dim) << " edges):";

   vector<Node> nodes;

   addBiDirHiperCube(G,dim,nodes);

   cout << T;

   cout << "\nGenerating the lengths: ";

   T.reset();

   Graph::EdgeMap<int> map(G);

   {

     Primes P;

     for(int i=0;i<dim*(1<<dim);i++) P();

     //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();

     for(int i=0;i<dim*(1<<dim);i++)

       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();

       map[Edge(((long long int)(i)*93505)%(dim*(1<<dim)))]=P();

   }

   cout << T;

   cout << "\nRunning Dijkstra: ";

   T.reset();

   {

     Dijkstra<Graph> Dij(G,map);

     Dij.run(nodes[0]);

   }

   cout << T;

 //   cout << "\nRunning MaxFlow: ";

 //   T.reset();

 //   {

 //    Graph::EdgeMap<int> flow(G);

 //     MaxFlow<Graph,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);

 //     MF.run(MF.NO_FLOW);

 //   }

 //   cout << T;

   cout << "\n";

 }