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

 #include<lemon/math.h>

 #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);

 }