alpar@742: // -*- mode:C++ -*- alpar@742: alpar@839: #include alpar@742: #include alpar@921: #include alpar@742: #include"bench_tools.h" alpar@742: alpar@742: using namespace std; alpar@921: using namespace lemon; 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>=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>=1; alpar@742: } alpar@742: return s; alpar@742: } alpar@742: alpar@742: template 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@751: typename Graph::template NodeMap visited(G,false); alpar@742: alpar@742: queue 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@774: for(OutEdgeIt e(G,n);e!=INVALID;++e) alpar@986: if(!visited[m=G.target(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 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@751: typename Graph::template NodeMap visited(G,false); alpar@742: alpar@742: int N=G.nodeNum(); alpar@742: vector 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@774: for(OutEdgeIt e(G,n);e!=INVALID;++e) alpar@986: if(!visited[m=G.target(e)]) { alpar@742: Q[Qh++]=m; alpar@742: visited.set(m,true); alpar@742: } alpar@742: } while(Qt!=Qh); alpar@742: } alpar@742: alpar@751: template alpar@751: void iteratorBench(Graph &G) alpar@751: { alpar@751: GRAPH_TYPEDEF_FACTORY(Graph); alpar@751: alpar@751: int i=0; alpar@751: alpar@774: for(NodeIt n(G);n!=INVALID;++n) alpar@774: for(OutEdgeIt e(G,n);e!=INVALID;++e) alpar@751: i++; alpar@751: } alpar@751: alpar@742: int main(int argc, char *argv[]) alpar@742: { 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@751: if(argc!=3) { alpar@751: cout << "Usage: " << argv[0] << " dim mul\n"; alpar@742: return 1; alpar@742: } alpar@742: alpar@742: int dim=atoi(argv[1]); alpar@751: int mul=atoi(argv[2]); alpar@742: alpar@742: // cout << "Creating Hipercube ("<< (1< nodes; alpar@742: addBiDirHiperCube(G,dim,nodes); alpar@742: alpar@742: PrintTime("GENGRAPH",T); alpar@742: alpar@742: T.reset(); alpar@742: { alpar@751: for(int i=0;i