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

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

     3 #include<math.h>

     4 #include<hugo/list_graph.h>

     5 #include<hugo/smart_graph.h>

     6 #include<hugo/dijkstra.h>

     7 #include<hugo/max_flow.h>

     9 #include"bench_tools.h"

    11 using namespace std;

    12 using namespace hugo;

    14 inline int numOfOnes(int n,int dim)

    15 {

    16   int s=0;

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

    18     s+=n%2;

    19     n>>=1;

    20   }

    21   return s;

    22 }

    24 inline int numOfZeros(int n,int dim)

    25 {

    26   int s=dim;

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

    28     s-=n&1;

    29     n>>=1;

    30   }

    31   return s;

    32 }

    34 template<class Graph>

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

    36 {

    37   GRAPH_TYPEDEF_FACTORY(Graph);

    39   using namespace std;

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

    43   queue<typename Graph::Node> Q;

    45   Q.push(source);

    46   visited[source]=true;

    47   do {

    48     Node n(Q.front());

    49     Node m;

    50     Q.pop();

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

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

    53 	Q.push(m);

    54 	visited.set(m,true);

    55       }

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

    57 }

    59 template<class Graph>

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

    61 {

    62   GRAPH_TYPEDEF_FACTORY(Graph);

    64   using namespace std;

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

    68   int N=G.nodeNum();

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

    70   int Qh=0;

    71   int Qt=0;

    74   Q[Qh++]=source;

    75   visited.set(source,true);

    76   do {

    77     Node m;

    78     Node n=Q[Qt++];

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

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

    81 	Q[Qh++]=m;

    82 	visited.set(m,true);

    83       }

    84   } while(Qt!=Qh);

    85 }

    87 template<class Graph>

    88 void iteratorBench(Graph &G)

    89 {

    90   GRAPH_TYPEDEF_FACTORY(Graph);

    92   int i=0;

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

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

    96       i++;

    97 }

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

   100 {

   101   //  typedef ListGraph Graph;

   102   typedef SmartGraph Graph;

   104   ///\bug GRAPH_TYPEDEF_FACTORY(Graph);

   105   GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph);

   107   Graph G;

   109   Timer T;

   111   if(argc!=3) {

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

   113     return 1;

   114   }

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

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

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

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

   122   T.reset();

   123   vector<Node> nodes;

   124   addBiDirHiperCube(G,dim,nodes);

   126   PrintTime("GENGRAPH",T);

   128   T.reset();

   129   {

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

   131       bfsStlQueue(G,nodes[0]);

   132   }

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

   134   T.reset();

   135   {

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

   137       bfsOwnQueue(G,nodes[0]);

   138   }

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

   140   T.reset();

   141   {

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

   143       iteratorBench(G);

   144   }

   145   PrintTime("ITERATE",T);

   148 }

author	alpar
	Sun, 05 Sep 2004 20:13:48 +0000
changeset 803	c3d832275e69
parent 751	e742d383fffc
child 839	3edf35893a90
permissions	-rw-r--r--