lemon-0.x: benchmark/bfs-bench.cc@cb082cdf3667

     1 // -*- mode:C++ -*-

     3 #include<queue>

     4 #include<cmath>

     5 #include<lemon/smart_graph.h>

     6 #include"bench_tools.h"

     8 using namespace std;

     9 using namespace lemon;

    11 inline int numOfOnes(int n,int dim)

    12 {

    13   int s=0;

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

    15     s+=n%2;

    16     n>>=1;

    17   }

    18   return s;

    19 }

    21 inline int numOfZeros(int n,int dim)

    22 {

    23   int s=dim;

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

    25     s-=n&1;

    26     n>>=1;

    27   }

    28   return s;

    29 }

    31 template<class Graph>

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

    33 {

    34   GRAPH_TYPEDEFS(typename Graph);

    36   using namespace std;

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

    40   queue<typename Graph::Node> Q;

    42   Q.push(source);

    43   visited[source]=true;

    44   do {

    45     Node n(Q.front());

    46     Node m;

    47     Q.pop();

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

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

    50 	Q.push(m);

    51 	visited.set(m,true);

    52       }

    53   } while(!Q.empty());

    54 }

    56 template<class Graph>

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

    58 {

    59   GRAPH_TYPEDEFS(typename Graph);

    61   using namespace std;

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

    65   int N=G.nodeNum();

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

    67   int Qh=0;

    68   int Qt=0;

    71   Q[Qh++]=source;

    72   visited.set(source,true);

    73   do {

    74     Node m;

    75     Node n=Q[Qt++];

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

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

    78 	Q[Qh++]=m;

    79 	visited.set(m,true);

    80       }

    81   } while(Qt!=Qh);

    82 }

    84 template<class Graph>

    85 void iteratorBench(Graph &G)

    86 {

    87   GRAPH_TYPEDEFS(typename Graph);

    89   int i=0;

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

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

    93       i++;

    94 }

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

    97 {

    98   typedef SmartGraph Graph;

   100   GRAPH_TYPEDEFS(Graph);

   102   Graph G;

   104   Timer T;

   106   if(argc!=3) {

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

   108     return 1;

   109   }

   111   int dim=atoi(argv[1]);

   112   int mul=atoi(argv[2]);

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

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

   117   T.reset();

   118   vector<Node> nodes;

   119   addBiDirHyperCube(G,dim,nodes);

   121   PrintTime("GENGRAPH",T);

   123   T.reset();

   124   {

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

   126       bfsStlQueue(G,nodes[0]);

   127   }

   128   PrintTime("BFS-STL",T);

   129   T.reset();

   130   {

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

   132       bfsOwnQueue(G,nodes[0]);

   133   }

   134   PrintTime("BFS-OWN",T);

   135   T.reset();

   136   {

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

   138       iteratorBench(G);

   139   }

   140   PrintTime("ITERATE",T);

   143 }

author	hegyi
	Mon, 21 Nov 2005 18:03:20 +0000
changeset 1823	cb082cdf3667
parent 1689	f1795dafe42c
child 1847	7cbc12e42482
permissions	-rw-r--r--