/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2008

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #include<lemon/math.h>

 #include<lemon/list_graph.h>

 #include<lemon/smart_graph.h>

 #include<lemon/dijkstra.h>

 #include<lemon/preflow.h>

 #include"bench_tools.h"

 using namespace std;

 using namespace lemon;

 inline int numOfOnes(int n,int dim)

 {

   int s=0;

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

     s+=n%2;

     n>>=1;

   }

   return s;

 }

 inline int numOfZeros(int n,int dim)

 {

   int s=dim;

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

     s-=n&1;

     n>>=1;

   }

   return s;

 }

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

 {

   //  typedef ListGraph Graph;

   typedef SmartGraph Graph;

   GRAPH_TYPEDEFS(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):";

   T.restart();

   vector<Node> nodes;

   addBiDirHyperCube(G,dim,nodes);

   PrintTime("GENGRAPH",T);

   T.restart();

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

   for(int i=0;i<5;i++) {

     Primes P;

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

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

     ///\todo It must have been commented out because of

     ///setToId

 //     Edge te;

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

 //       te.setToId(((long long int)(i)*93505)%(dim*(1<<dim)));

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

 //       map[te]=P();

 //     }

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

 //       int mul= (1<<(numOfZeros(i,dim)/4));

 //       for(OutEdgeIt e(G,nodes[i]);G.valid(e);G.next(e))

 // 	map[e]*=mul;

 //     }

   }

   PrintTime("GENLENGTHS",T);

   T.restart();

   {

     Dijkstra<Graph> Dij(G,map);

     for(int i=0;i<10;i++)

       Dij.run(nodes[0]);

   }

   PrintTime("DIJKSTRA",T);

   T.restart();

   {

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

     Preflow<Graph> MF(G,map,nodes[0],nodes[1<<dim-1]);

     for(int i=0;i<10;i++)

       MF.run();

   }

   PrintTime("PREFLOW",T);

 }