equal
deleted
inserted
replaced
36 { |
36 { |
37 GRAPH_TYPEDEF_FACTORY(Graph); |
37 GRAPH_TYPEDEF_FACTORY(Graph); |
38 |
38 |
39 using namespace std; |
39 using namespace std; |
40 |
40 |
41 typename Graph::NodeMap<bool> visited(G,false); |
41 typename Graph::template NodeMap<bool> visited(G,false); |
42 |
42 |
43 queue<typename Graph::Node> Q; |
43 queue<typename Graph::Node> Q; |
44 |
44 |
45 Q.push(source); |
45 Q.push(source); |
46 visited[source]=true; |
46 visited[source]=true; |
61 { |
61 { |
62 GRAPH_TYPEDEF_FACTORY(Graph); |
62 GRAPH_TYPEDEF_FACTORY(Graph); |
63 |
63 |
64 using namespace std; |
64 using namespace std; |
65 |
65 |
66 typename Graph::NodeMap<bool> visited(G,false); |
66 typename Graph::template NodeMap<bool> visited(G,false); |
67 |
67 |
68 int N=G.nodeNum(); |
68 int N=G.nodeNum(); |
69 vector<typename Graph::Node> Q(N); |
69 vector<typename Graph::Node> Q(N); |
70 int Qh=0; |
70 int Qh=0; |
71 int Qt=0; |
71 int Qt=0; |
82 visited.set(m,true); |
82 visited.set(m,true); |
83 } |
83 } |
84 } while(Qt!=Qh); |
84 } while(Qt!=Qh); |
85 } |
85 } |
86 |
86 |
|
87 template<class Graph> |
|
88 void iteratorBench(Graph &G) |
|
89 { |
|
90 GRAPH_TYPEDEF_FACTORY(Graph); |
|
91 |
|
92 int i=0; |
|
93 |
|
94 for(NodeIt n(G);G.valid(n);G.next(n)) |
|
95 for(OutEdgeIt e(G,n);G.valid(e);G.next(e)) |
|
96 i++; |
|
97 } |
|
98 |
87 int main(int argc, char *argv[]) |
99 int main(int argc, char *argv[]) |
88 { |
100 { |
89 // typedef ListGraph Graph; |
101 // typedef ListGraph Graph; |
90 typedef SmartGraph Graph; |
102 typedef SmartGraph Graph; |
91 |
103 |
94 |
106 |
95 Graph G; |
107 Graph G; |
96 |
108 |
97 Timer T; |
109 Timer T; |
98 |
110 |
99 if(argc!=2) { |
111 if(argc!=3) { |
100 cout << "Usage: " << argv[0] << " dim\n"; |
112 cout << "Usage: " << argv[0] << " dim mul\n"; |
101 return 1; |
113 return 1; |
102 } |
114 } |
103 |
115 |
104 int dim=atoi(argv[1]); |
116 int dim=atoi(argv[1]); |
|
117 int mul=atoi(argv[2]); |
105 |
118 |
106 // cout << "Creating Hipercube ("<< (1<<dim) << " nodes, " |
119 // cout << "Creating Hipercube ("<< (1<<dim) << " nodes, " |
107 // << dim*(1<<dim) << " edges):"; |
120 // << dim*(1<<dim) << " edges):"; |
108 |
121 |
109 T.reset(); |
122 T.reset(); |
112 |
125 |
113 PrintTime("GENGRAPH",T); |
126 PrintTime("GENGRAPH",T); |
114 |
127 |
115 T.reset(); |
128 T.reset(); |
116 { |
129 { |
117 for(int i=0;i<50000;i++) |
130 for(int i=0;i<mul;i++) |
118 bfsStlQueue(G,nodes[0]); |
131 bfsStlQueue(G,nodes[0]); |
119 } |
132 } |
120 PrintTime("BFS-STL",T); |
133 PrintTime("BFS-STL",T); |
121 T.reset(); |
134 T.reset(); |
122 { |
135 { |
123 for(int i=0;i<50000;i++) |
136 for(int i=0;i<mul;i++) |
124 bfsOwnQueue(G,nodes[0]); |
137 bfsOwnQueue(G,nodes[0]); |
125 } |
138 } |
126 PrintTime("BFS-OWN",T); |
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); |
|
146 |
|
147 |
127 } |
148 } |