/* -*- 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<queue>

#include<cmath>

#include<lemon/smart_graph.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;

}

template<class Graph>

void bfsStlQueue(Graph &G,typename Graph::Node source)

{

  GRAPH_TYPEDEFS(typename Graph);

  using namespace std;

  typename Graph::template NodeMap<bool> visited(G,false);

  queue<typename Graph::Node> Q;

  Q.push(source);

  visited[source]=true;

  do {

    Node n(Q.front());

    Node m;

    Q.pop();

    for(OutEdgeIt e(G,n);e!=INVALID;++e)

      if(!visited[m=G.target(e)]) {

	Q.push(m);

	visited.set(m,true);

      }

  } while(!Q.empty());

}

template<class Graph>

void bfsOwnQueue(Graph &G,typename Graph::Node source)

{

  GRAPH_TYPEDEFS(typename Graph);

  using namespace std;

  typename Graph::template NodeMap<bool> visited(G,false);

  int N=G.nodeNum();

  vector<typename Graph::Node> Q(N);

  int Qh=0;

  int Qt=0;

  Q[Qh++]=source;

  visited.set(source,true);

  do {

    Node m;

    Node n=Q[Qt++];

    for(OutEdgeIt e(G,n);e!=INVALID;++e)

      if(!visited[m=G.target(e)]) {

	Q[Qh++]=m;

	visited.set(m,true);

      }

  } while(Qt!=Qh);

}

template<class Graph>

void iteratorBench(Graph &G)

{

  GRAPH_TYPEDEFS(typename Graph);

  int i=0;

  for(NodeIt n(G);n!=INVALID;++n)

    for(OutEdgeIt e(G,n);e!=INVALID;++e)

      i++;

}

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

{

  typedef SmartGraph Graph;

  GRAPH_TYPEDEFS(Graph);

  Graph G;

  Timer T;

  if(argc!=3) {

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

    return 1;

  }

  int dim=atoi(argv[1]);

  int mul=atoi(argv[2]);

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

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

  T.restart();

  vector<Node> nodes;

  addBiDirHyperCube(G,dim,nodes);

  PrintTime("GENGRAPH",T);

  T.restart();

  {

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

      bfsStlQueue(G,nodes[0]);

  }

  PrintTime("BFS-STL",T);

  T.restart();

  {

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

      bfsOwnQueue(G,nodes[0]);

  }

  PrintTime("BFS-OWN",T);

  T.restart();

  {

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

      iteratorBench(G);

  }

  PrintTime("ITERATE",T);

}