// -*- 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";

}