benchmark/bfs-bench.cc
author deba
Wed, 17 May 2006 09:07:24 +0000
changeset 2089 fce8db723736
parent 1847 7cbc12e42482
child 2391 14a343be7a5a
permissions -rw-r--r--
SimpleBucketHeap added

It does not supports erasing, decreasing, increasing.
It contains single linked lists

It can be used to store levels for push-relabel algorithms
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include<queue>
    20 #include<cmath>
    21 #include<lemon/smart_graph.h>
    22 #include"bench_tools.h"
    23 
    24 using namespace std;
    25 using namespace lemon;
    26 
    27 inline int numOfOnes(int n,int dim)
    28 {
    29   int s=0;
    30   for(int i=0;i<dim;i++) {
    31     s+=n%2;
    32     n>>=1;
    33   }
    34   return s;
    35 }
    36 
    37 inline int numOfZeros(int n,int dim)
    38 {
    39   int s=dim;
    40   for(int i=0;i<dim;i++) {
    41     s-=n&1;
    42     n>>=1;
    43   }
    44   return s;
    45 }
    46 
    47 template<class Graph>
    48 void bfsStlQueue(Graph &G,typename Graph::Node source)
    49 {
    50   GRAPH_TYPEDEFS(typename Graph);
    51 
    52   using namespace std;
    53   
    54   typename Graph::template NodeMap<bool> visited(G,false);
    55     
    56   queue<typename Graph::Node> Q;
    57     
    58   Q.push(source);
    59   visited[source]=true;
    60   do {
    61     Node n(Q.front());
    62     Node m;
    63     Q.pop();
    64     for(OutEdgeIt e(G,n);e!=INVALID;++e)
    65       if(!visited[m=G.target(e)]) {
    66 	Q.push(m);
    67 	visited.set(m,true);
    68       }
    69   } while(!Q.empty());
    70 }
    71 
    72 template<class Graph>
    73 void bfsOwnQueue(Graph &G,typename Graph::Node source)
    74 {
    75   GRAPH_TYPEDEFS(typename Graph);
    76 
    77   using namespace std;
    78   
    79   typename Graph::template NodeMap<bool> visited(G,false);
    80   
    81   int N=G.nodeNum();
    82   vector<typename Graph::Node> Q(N);
    83   int Qh=0;
    84   int Qt=0;
    85   
    86 
    87   Q[Qh++]=source;
    88   visited.set(source,true);
    89   do {
    90     Node m;
    91     Node n=Q[Qt++];
    92     for(OutEdgeIt e(G,n);e!=INVALID;++e)
    93       if(!visited[m=G.target(e)]) {
    94 	Q[Qh++]=m;
    95 	visited.set(m,true);
    96       }
    97   } while(Qt!=Qh);
    98 }
    99 
   100 template<class Graph>
   101 void iteratorBench(Graph &G)
   102 {
   103   GRAPH_TYPEDEFS(typename Graph);
   104 
   105   int i=0;
   106   
   107   for(NodeIt n(G);n!=INVALID;++n)
   108     for(OutEdgeIt e(G,n);e!=INVALID;++e)
   109       i++;
   110 }
   111 
   112 int main(int argc, char *argv[])
   113 {
   114   typedef SmartGraph Graph;
   115 
   116   GRAPH_TYPEDEFS(Graph);
   117 
   118   Graph G;
   119   
   120   Timer T;
   121   
   122   if(argc!=3) {
   123     cout << "Usage: " << argv[0] << " dim mul\n";
   124     return 1;
   125   }
   126   
   127   int dim=atoi(argv[1]);
   128   int mul=atoi(argv[2]);
   129   
   130 //   cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
   131 //        << dim*(1<<dim) << " edges):";
   132 
   133   T.restart();
   134   vector<Node> nodes;
   135   addBiDirHyperCube(G,dim,nodes);
   136 
   137   PrintTime("GENGRAPH",T);
   138 
   139   T.restart();
   140   {
   141     for(int i=0;i<mul;i++)
   142       bfsStlQueue(G,nodes[0]);
   143   }
   144   PrintTime("BFS-STL",T);
   145   T.restart();
   146   {
   147     for(int i=0;i<mul;i++)
   148       bfsOwnQueue(G,nodes[0]);
   149   }
   150   PrintTime("BFS-OWN",T);
   151   T.restart();
   152   {
   153     for(int i=0;i<mul;i++)
   154       iteratorBench(G);
   155   }
   156   PrintTime("ITERATE",T);
   157 
   158 
   159 }