alpar@742: // -*- mode:C++ -*-
alpar@742: 
alpar@742: #include<math.h>
alpar@742: #include<hugo/list_graph.h>
alpar@742: #include<hugo/smart_graph.h>
alpar@742: #include<hugo/dijkstra.h>
alpar@742: #include<hugo/max_flow.h>
alpar@742: 
alpar@742: #include"bench_tools.h"
alpar@742: 
alpar@742: using namespace std;
alpar@742: using namespace hugo;
alpar@742: 
alpar@742: inline int numOfOnes(int n,int dim)
alpar@742: {
alpar@742:   int s=0;
alpar@742:   for(int i=0;i<dim;i++) {
alpar@742:     s+=n%2;
alpar@742:     n>>=1;
alpar@742:   }
alpar@742:   return s;
alpar@742: }
alpar@742: 
alpar@742: inline int numOfZeros(int n,int dim)
alpar@742: {
alpar@742:   int s=dim;
alpar@742:   for(int i=0;i<dim;i++) {
alpar@742:     s-=n&1;
alpar@742:     n>>=1;
alpar@742:   }
alpar@742:   return s;
alpar@742: }
alpar@742: 
alpar@742: template<class Graph>
alpar@742: void bfsStlQueue(Graph &G,typename Graph::Node source)
alpar@742: {
alpar@742:   GRAPH_TYPEDEF_FACTORY(Graph);
alpar@742: 
alpar@742:   using namespace std;
alpar@742:   
alpar@742:   typename Graph::NodeMap<bool> visited(G,false);
alpar@742:     
alpar@742:   queue<typename Graph::Node> Q;
alpar@742:     
alpar@742:   Q.push(source);
alpar@742:   visited[source]=true;
alpar@742:   do {
alpar@742:     Node n(Q.front());
alpar@742:     Node m;
alpar@742:     Q.pop();
alpar@742:     for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
alpar@742:       if(!visited[m=G.head(e)]) {
alpar@742: 	Q.push(m);
alpar@742: 	visited.set(m,true);
alpar@742:       }
alpar@742:   } while(!Q.empty());
alpar@742: }
alpar@742: 
alpar@742: template<class Graph>
alpar@742: void bfsOwnQueue(Graph &G,typename Graph::Node source)
alpar@742: {
alpar@742:   GRAPH_TYPEDEF_FACTORY(Graph);
alpar@742: 
alpar@742:   using namespace std;
alpar@742:   
alpar@742:   typename Graph::NodeMap<bool> visited(G,false);
alpar@742:   
alpar@742:   int N=G.nodeNum();
alpar@742:   vector<typename Graph::Node> Q(N);
alpar@742:   int Qh=0;
alpar@742:   int Qt=0;
alpar@742:   
alpar@742: 
alpar@742:   Q[Qh++]=source;
alpar@742:   visited.set(source,true);
alpar@742:   do {
alpar@742:     Node m;
alpar@742:     Node n=Q[Qt++];
alpar@742:     for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
alpar@742:       if(!visited[m=G.head(e)]) {
alpar@742: 	Q[Qh++]=m;
alpar@742: 	visited.set(m,true);
alpar@742:       }
alpar@742:   } while(Qt!=Qh);
alpar@742: }
alpar@742: 
alpar@742: int main(int argc, char *argv[])
alpar@742: {
alpar@742:   //  typedef ListGraph Graph;
alpar@742:   typedef SmartGraph Graph;
alpar@742: 
alpar@742:   ///\bug GRAPH_TYPEDEF_FACTORY(Graph);
alpar@742:   GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);
alpar@742: 
alpar@742:   Graph G;
alpar@742:   
alpar@742:   Timer T;
alpar@742:   
alpar@742:   if(argc!=2) {
alpar@742:     cout << "Usage: " << argv[0] << " dim\n";
alpar@742:     return 1;
alpar@742:   }
alpar@742:   
alpar@742:   int dim=atoi(argv[1]);
alpar@742:   
alpar@742: //   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
alpar@742: //        << dim*(1<<dim) << " edges):";
alpar@742: 
alpar@742:   T.reset();
alpar@742:   vector<Node> nodes;
alpar@742:   addBiDirHiperCube(G,dim,nodes);
alpar@742: 
alpar@742:   PrintTime("GENGRAPH",T);
alpar@742: 
alpar@742:   T.reset();
alpar@742:   {
alpar@742:     for(int i=0;i<50000;i++)
alpar@742:       bfsStlQueue(G,nodes[0]);
alpar@742:   }
alpar@742:   PrintTime("BFS-STL",T);
alpar@742:   T.reset();
alpar@742:   {
alpar@742:     for(int i=0;i<50000;i++)
alpar@742:       bfsOwnQueue(G,nodes[0]);
alpar@742:   }
alpar@742:   PrintTime("BFS-OWN",T);
alpar@742: }