/* -*- C++ -*-

 *

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

 *

 * Copyright (C) 2003-2006

 * 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<cmath>

#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 i=0;i<dim*(1<<dim);i++) 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,int> MF(G,nodes[0],nodes[1<<dim-1],map,flow);

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

      MF.run(MF.NO_FLOW);

  }

  PrintTime("PREFLOW",T);

}