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

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

     3 #include <queue>

     4 #include<math.h>

     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_TYPEDEF_FACTORY(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_TYPEDEF_FACTORY(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_TYPEDEF_FACTORY(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   ///\bug GRAPH_TYPEDEF_FACTORY(Graph);

   101   GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);

   103   Graph G;

   105   Timer T;

   107   if(argc!=3) {

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

   109     return 1;

   110   }

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

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

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

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

   118   T.reset();

   119   vector<Node> nodes;

   120   addBiDirHiperCube(G,dim,nodes);

   122   PrintTime("GENGRAPH",T);

   124   T.reset();

   125   {

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

   127       bfsStlQueue(G,nodes[0]);

   128   }

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

   130   T.reset();

   131   {

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

   133       bfsOwnQueue(G,nodes[0]);

   134   }

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

   136   T.reset();

   137   {

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

   139       iteratorBench(G);

   140   }

   141   PrintTime("ITERATE",T);

   144 }

author	athos
	Mon, 04 Apr 2005 14:45:23 +0000
changeset 1298	d1ca90316b59
parent 921	818510fa3d99
permissions	-rw-r--r--