[742] | 1 | // -*- mode:C++ -*- |
---|
| 2 | |
---|
| 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> |
---|
| 8 | |
---|
| 9 | #include"bench_tools.h" |
---|
| 10 | |
---|
| 11 | using namespace std; |
---|
| 12 | using namespace hugo; |
---|
| 13 | |
---|
| 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 | } |
---|
| 23 | |
---|
| 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 | } |
---|
| 33 | |
---|
| 34 | template<class Graph> |
---|
| 35 | void bfsStlQueue(Graph &G,typename Graph::Node source) |
---|
| 36 | { |
---|
| 37 | GRAPH_TYPEDEF_FACTORY(Graph); |
---|
| 38 | |
---|
| 39 | using namespace std; |
---|
| 40 | |
---|
| 41 | typename Graph::NodeMap<bool> visited(G,false); |
---|
| 42 | |
---|
| 43 | queue<typename Graph::Node> Q; |
---|
| 44 | |
---|
| 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);G.valid(e);G.next(e)) |
---|
| 52 | if(!visited[m=G.head(e)]) { |
---|
| 53 | Q.push(m); |
---|
| 54 | visited.set(m,true); |
---|
| 55 | } |
---|
| 56 | } while(!Q.empty()); |
---|
| 57 | } |
---|
| 58 | |
---|
| 59 | template<class Graph> |
---|
| 60 | void bfsOwnQueue(Graph &G,typename Graph::Node source) |
---|
| 61 | { |
---|
| 62 | GRAPH_TYPEDEF_FACTORY(Graph); |
---|
| 63 | |
---|
| 64 | using namespace std; |
---|
| 65 | |
---|
| 66 | typename Graph::NodeMap<bool> visited(G,false); |
---|
| 67 | |
---|
| 68 | int N=G.nodeNum(); |
---|
| 69 | vector<typename Graph::Node> Q(N); |
---|
| 70 | int Qh=0; |
---|
| 71 | int Qt=0; |
---|
| 72 | |
---|
| 73 | |
---|
| 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);G.valid(e);G.next(e)) |
---|
| 80 | if(!visited[m=G.head(e)]) { |
---|
| 81 | Q[Qh++]=m; |
---|
| 82 | visited.set(m,true); |
---|
| 83 | } |
---|
| 84 | } while(Qt!=Qh); |
---|
| 85 | } |
---|
| 86 | |
---|
| 87 | int main(int argc, char *argv[]) |
---|
| 88 | { |
---|
| 89 | // typedef ListGraph Graph; |
---|
| 90 | typedef SmartGraph Graph; |
---|
| 91 | |
---|
| 92 | ///\bug GRAPH_TYPEDEF_FACTORY(Graph); |
---|
| 93 | GRAPH_TYPEDEF_FACTORY_NOTYPENAME(Graph); |
---|
| 94 | |
---|
| 95 | Graph G; |
---|
| 96 | |
---|
| 97 | Timer T; |
---|
| 98 | |
---|
| 99 | if(argc!=2) { |
---|
| 100 | cout << "Usage: " << argv[0] << " dim\n"; |
---|
| 101 | return 1; |
---|
| 102 | } |
---|
| 103 | |
---|
| 104 | int dim=atoi(argv[1]); |
---|
| 105 | |
---|
| 106 | // cout << "Creating Hipercube ("<< (1<<dim) << " nodes, " |
---|
| 107 | // << dim*(1<<dim) << " edges):"; |
---|
| 108 | |
---|
| 109 | T.reset(); |
---|
| 110 | vector<Node> nodes; |
---|
| 111 | addBiDirHiperCube(G,dim,nodes); |
---|
| 112 | |
---|
| 113 | PrintTime("GENGRAPH",T); |
---|
| 114 | |
---|
| 115 | T.reset(); |
---|
| 116 | { |
---|
| 117 | for(int i=0;i<50000;i++) |
---|
| 118 | bfsStlQueue(G,nodes[0]); |
---|
| 119 | } |
---|
| 120 | PrintTime("BFS-STL",T); |
---|
| 121 | T.reset(); |
---|
| 122 | { |
---|
| 123 | for(int i=0;i<50000;i++) |
---|
| 124 | bfsOwnQueue(G,nodes[0]); |
---|
| 125 | } |
---|
| 126 | PrintTime("BFS-OWN",T); |
---|
| 127 | } |
---|