alpar@1956: /* -*- C++ -*- alpar@1956: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1956: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@1956: * alpar@1956: * Permission to use, modify and distribute this software is granted alpar@1956: * provided that this copyright notice appears in all copies. For alpar@1956: * precise terms see the accompanying LICENSE file. alpar@1956: * alpar@1956: * This software is provided "AS IS" with no warranty of any kind, alpar@1956: * express or implied, and with no claim as to its suitability for any alpar@1956: * purpose. alpar@1956: * alpar@1956: */ alpar@742: alpar@1632: #include alpar@1632: #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@1756: GRAPH_TYPEDEFS(typename 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@1756: GRAPH_TYPEDEFS(typename 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@1756: GRAPH_TYPEDEFS(typename 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@1756: GRAPH_TYPEDEFS(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@1689: addBiDirHyperCube(G,dim,nodes); alpar@742: alpar@742: PrintTime("GENGRAPH",T); alpar@742: alpar@1847: T.restart(); alpar@742: { alpar@751: for(int i=0;i