100 /// |
100 /// |
101 /// This function counts the items (nodes, edges etc) in the graph. |
101 /// This function counts the items (nodes, edges etc) in the graph. |
102 /// The complexity of the function is O(n) because |
102 /// The complexity of the function is O(n) because |
103 /// it iterates on all of the items. |
103 /// it iterates on all of the items. |
104 |
104 |
105 template <typename Graph, typename ItemIt> |
105 template <typename Graph, typename Item> |
106 inline int countItems(const Graph& g) { |
106 inline int countItems(const Graph& g) { |
|
107 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; |
107 int num = 0; |
108 int num = 0; |
108 for (ItemIt it(g); it != INVALID; ++it) { |
109 for (ItemIt it(g); it != INVALID; ++it) { |
109 ++num; |
110 ++num; |
110 } |
111 } |
111 return num; |
112 return num; |
112 } |
113 } |
113 |
114 |
114 // Node counting: |
115 // Node counting: |
115 |
116 |
116 template <typename Graph> |
117 namespace _graph_utils_bits { |
117 inline typename enable_if<typename Graph::NodeNumTag, int>::type |
118 |
118 _countNodes(const Graph &g) { |
119 template <typename Graph, typename Enable = void> |
119 return g.nodeNum(); |
120 struct CountNodesSelector { |
120 } |
121 static int count(const Graph &g) { |
121 |
122 return countItems<Graph, typename Graph::Node>(g); |
122 template <typename Graph> |
123 } |
123 inline int _countNodes(Wrap<Graph> w) { |
124 }; |
124 return countItems<Graph, typename Graph::NodeIt>(w.value); |
125 |
|
126 template <typename Graph> |
|
127 struct CountNodesSelector< |
|
128 Graph, typename |
|
129 enable_if<typename Graph::NodeNumTag, void>::type> |
|
130 { |
|
131 static int count(const Graph &g) { |
|
132 return g.nodeNum(); |
|
133 } |
|
134 }; |
125 } |
135 } |
126 |
136 |
127 /// \brief Function to count the nodes in the graph. |
137 /// \brief Function to count the nodes in the graph. |
128 /// |
138 /// |
129 /// This function counts the nodes in the graph. |
139 /// This function counts the nodes in the graph. |
132 /// |
142 /// |
133 /// \todo refer how to specialize it |
143 /// \todo refer how to specialize it |
134 |
144 |
135 template <typename Graph> |
145 template <typename Graph> |
136 inline int countNodes(const Graph& g) { |
146 inline int countNodes(const Graph& g) { |
137 return _countNodes<Graph>(g); |
147 return _graph_utils_bits::CountNodesSelector<Graph>::count(g); |
138 } |
148 } |
|
149 |
139 |
150 |
140 // Edge counting: |
151 // Edge counting: |
141 |
152 |
142 template <typename Graph> |
153 namespace _graph_utils_bits { |
143 inline typename enable_if<typename Graph::EdgeNumTag, int>::type |
154 |
144 _countEdges(const Graph &g) { |
155 template <typename Graph, typename Enable = void> |
145 return g.edgeNum(); |
156 struct CountEdgesSelector { |
146 } |
157 static int count(const Graph &g) { |
147 |
158 return countItems<Graph, typename Graph::Edge>(g); |
148 template <typename Graph> |
159 } |
149 inline int _countEdges(Wrap<Graph> w) { |
160 }; |
150 return countItems<Graph, typename Graph::EdgeIt>(w.value); |
161 |
|
162 template <typename Graph> |
|
163 struct CountEdgesSelector< |
|
164 Graph, |
|
165 typename enable_if<typename Graph::EdgeNumTag, void>::type> |
|
166 { |
|
167 static int count(const Graph &g) { |
|
168 return g.edgeNum(); |
|
169 } |
|
170 }; |
151 } |
171 } |
152 |
172 |
153 /// \brief Function to count the edges in the graph. |
173 /// \brief Function to count the edges in the graph. |
154 /// |
174 /// |
155 /// This function counts the edges in the graph. |
175 /// This function counts the edges in the graph. |
156 /// The complexity of the function is O(e) but for some |
176 /// The complexity of the function is O(e) but for some |
157 /// graph structures it is specialized to run in O(1). |
177 /// graph structures it is specialized to run in O(1). |
158 |
178 |
159 template <typename Graph> |
179 template <typename Graph> |
160 inline int countEdges(const Graph& g) { |
180 inline int countEdges(const Graph& g) { |
161 return _countEdges<Graph>(g); |
181 return _graph_utils_bits::CountEdgesSelector<Graph>::count(g); |
162 } |
182 } |
163 |
183 |
164 // Undirected edge counting: |
184 // Undirected edge counting: |
165 |
185 namespace _graph_utils_bits { |
166 template <typename Graph> |
186 |
167 inline |
187 template <typename Graph, typename Enable = void> |
168 typename enable_if<typename Graph::EdgeNumTag, int>::type |
188 struct CountUEdgesSelector { |
169 _countUEdges(const Graph &g) { |
189 static int count(const Graph &g) { |
170 return g.uEdgeNum(); |
190 return countItems<Graph, typename Graph::UEdge>(g); |
171 } |
191 } |
172 |
192 }; |
173 template <typename Graph> |
193 |
174 inline int _countUEdges(Wrap<Graph> w) { |
194 template <typename Graph> |
175 return countItems<Graph, typename Graph::UEdgeIt>(w.value); |
195 struct CountUEdgesSelector< |
|
196 Graph, |
|
197 typename enable_if<typename Graph::EdgeNumTag, void>::type> |
|
198 { |
|
199 static int count(const Graph &g) { |
|
200 return g.uEdgeNum(); |
|
201 } |
|
202 }; |
176 } |
203 } |
177 |
204 |
178 /// \brief Function to count the undirected edges in the graph. |
205 /// \brief Function to count the undirected edges in the graph. |
179 /// |
206 /// |
180 /// This function counts the undirected edges in the graph. |
207 /// This function counts the undirected edges in the graph. |
181 /// The complexity of the function is O(e) but for some |
208 /// The complexity of the function is O(e) but for some |
182 /// graph structures it is specialized to run in O(1). |
209 /// graph structures it is specialized to run in O(1). |
183 |
210 |
184 template <typename Graph> |
211 template <typename Graph> |
185 inline int countUEdges(const Graph& g) { |
212 inline int countUEdges(const Graph& g) { |
186 return _countUEdges<Graph>(g); |
213 return _graph_utils_bits::CountUEdgesSelector<Graph>::count(g); |
187 } |
214 |
188 |
215 } |
189 |
216 |
190 |
217 |
191 template <typename Graph, typename DegIt> |
218 template <typename Graph, typename DegIt> |
192 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { |
219 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { |
193 int num = 0; |
220 int num = 0; |
222 template <typename Graph> |
249 template <typename Graph> |
223 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { |
250 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { |
224 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n); |
251 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n); |
225 } |
252 } |
226 |
253 |
227 |
254 namespace _graph_utils_bits { |
228 template <typename Graph> |
255 |
229 inline |
256 template <typename Graph, typename Enable = void> |
230 typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type |
257 struct FindEdgeSelector { |
231 _findEdge(const Graph &g, |
258 typedef typename Graph::Node Node; |
232 typename Graph::Node u, typename Graph::Node v, |
259 typedef typename Graph::Edge Edge; |
233 typename Graph::Edge prev = INVALID) { |
260 static Edge find(const Graph &g, Node u, Node v, Edge e) { |
234 return g.findEdge(u, v, prev); |
261 if (e == INVALID) { |
235 } |
262 g.firstOut(e, u); |
236 |
263 } else { |
237 template <typename Graph> |
264 g.nextOut(e); |
238 inline typename Graph::Edge |
265 } |
239 _findEdge(Wrap<Graph> w, |
266 while (e != INVALID && g.target(e) != v) { |
240 typename Graph::Node u, |
267 g.nextOut(e); |
241 typename Graph::Node v, |
268 } |
242 typename Graph::Edge prev = INVALID) { |
269 return e; |
243 const Graph& g = w.value; |
270 } |
244 if (prev == INVALID) { |
271 }; |
245 typename Graph::OutEdgeIt e(g, u); |
272 |
246 while (e != INVALID && g.target(e) != v) ++e; |
273 template <typename Graph> |
247 return e; |
274 struct FindEdgeSelector< |
248 } else { |
275 Graph, |
249 typename Graph::OutEdgeIt e(g, prev); ++e; |
276 typename enable_if<typename Graph::FindEdgeTag, void>::type> |
250 while (e != INVALID && g.target(e) != v) ++e; |
277 { |
251 return e; |
278 typedef typename Graph::Node Node; |
252 } |
279 typedef typename Graph::Edge Edge; |
|
280 static Edge find(const Graph &g, Node u, Node v, Edge prev) { |
|
281 return g.findEdge(u, v, prev); |
|
282 } |
|
283 }; |
253 } |
284 } |
254 |
285 |
255 /// \brief Finds an edge between two nodes of a graph. |
286 /// \brief Finds an edge between two nodes of a graph. |
256 /// |
287 /// |
257 /// Finds an edge from node \c u to node \c v in graph \c g. |
288 /// Finds an edge from node \c u to node \c v in graph \c g. |
265 ///\code |
296 ///\code |
266 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) { |
297 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) { |
267 /// ... |
298 /// ... |
268 /// } |
299 /// } |
269 ///\endcode |
300 ///\endcode |
270 // /// \todo We may want to use the "GraphBase" |
|
271 // /// interface here... |
|
272 template <typename Graph> |
301 template <typename Graph> |
273 inline typename Graph::Edge findEdge(const Graph &g, |
302 inline typename Graph::Edge findEdge(const Graph &g, |
274 typename Graph::Node u, |
303 typename Graph::Node u, |
275 typename Graph::Node v, |
304 typename Graph::Node v, |
276 typename Graph::Edge prev = INVALID) { |
305 typename Graph::Edge prev = INVALID) { |
277 return _findEdge<Graph>(g, u, v, prev); |
306 return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, prev); |
278 } |
307 } |
279 |
308 |
280 /// \brief Iterator for iterating on edges connected the same nodes. |
309 /// \brief Iterator for iterating on edges connected the same nodes. |
281 /// |
310 /// |
282 /// Iterator for iterating on edges connected the same nodes. It is |
311 /// Iterator for iterating on edges connected the same nodes. It is |
323 } |
352 } |
324 private: |
353 private: |
325 const Graph& graph; |
354 const Graph& graph; |
326 }; |
355 }; |
327 |
356 |
328 template <typename Graph> |
357 namespace _graph_utils_bits { |
329 inline |
358 |
330 typename enable_if< |
359 template <typename Graph, typename Enable = void> |
331 typename Graph::FindEdgeTag, |
360 struct FindUEdgeSelector { |
332 typename Graph::UEdge>::type |
361 typedef typename Graph::Node Node; |
333 _findUEdge(const Graph &g, |
362 typedef typename Graph::UEdge UEdge; |
334 typename Graph::Node u, typename Graph::Node v, |
363 static UEdge find(const Graph &g, Node u, Node v, UEdge e) { |
335 typename Graph::UEdge prev = INVALID) { |
364 bool b; |
336 return g.findUEdge(u, v, prev); |
365 if (u != v) { |
337 } |
366 if (e == INVALID) { |
338 |
367 g.firstInc(e, u, b); |
339 template <typename Graph> |
368 } else { |
340 inline typename Graph::UEdge |
369 b = g.source(e) == u; |
341 _findUEdge(Wrap<Graph> w, |
370 g.nextInc(e, b); |
342 typename Graph::Node u, |
371 } |
343 typename Graph::Node v, |
372 while (e != INVALID && g.target(e) != v) { |
344 typename Graph::UEdge prev = INVALID) { |
373 g.nextInc(e, b); |
345 const Graph& g = w.value; |
374 } |
346 if (prev == INVALID) { |
375 } else { |
347 typename Graph::OutEdgeIt e(g, u); |
376 if (e == INVALID) { |
348 while (e != INVALID && g.target(e) != v) ++e; |
377 g.firstInc(e, u, b); |
349 return e; |
378 } else { |
350 } else { |
379 b = true; |
351 typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e; |
380 g.nextInc(e, b); |
352 while (e != INVALID && g.target(e) != v) ++e; |
381 } |
353 return e; |
382 while (e != INVALID && (!b || g.target(e) != v)) { |
354 } |
383 g.nextInc(e, b); |
|
384 } |
|
385 } |
|
386 return e; |
|
387 } |
|
388 }; |
|
389 |
|
390 template <typename Graph> |
|
391 struct FindUEdgeSelector< |
|
392 Graph, |
|
393 typename enable_if<typename Graph::FindEdgeTag, void>::type> |
|
394 { |
|
395 typedef typename Graph::Node Node; |
|
396 typedef typename Graph::UEdge UEdge; |
|
397 static UEdge find(const Graph &g, Node u, Node v, UEdge prev) { |
|
398 return g.findUEdge(u, v, prev); |
|
399 } |
|
400 }; |
355 } |
401 } |
356 |
402 |
357 /// \brief Finds an uedge between two nodes of a graph. |
403 /// \brief Finds an uedge between two nodes of a graph. |
358 /// |
404 /// |
359 /// Finds an uedge from node \c u to node \c v in graph \c g. |
405 /// Finds an uedge from node \c u to node \c v in graph \c g. |
|
406 /// If the node \c u and node \c v is equal then each loop edge |
|
407 /// will be enumerated. |
360 /// |
408 /// |
361 /// If \c prev is \ref INVALID (this is the default value), then |
409 /// If \c prev is \ref INVALID (this is the default value), then |
362 /// it finds the first edge from \c u to \c v. Otherwise it looks for |
410 /// it finds the first edge from \c u to \c v. Otherwise it looks for |
363 /// the next edge from \c u to \c v after \c prev. |
411 /// the next edge from \c u to \c v after \c prev. |
364 /// \return The found edge or \ref INVALID if there is no such an edge. |
412 /// \return The found edge or \ref INVALID if there is no such an edge. |
368 /// for(UEdge e = findUEdge(g,u,v); e != INVALID; |
416 /// for(UEdge e = findUEdge(g,u,v); e != INVALID; |
369 /// e = findUEdge(g,u,v,e)) { |
417 /// e = findUEdge(g,u,v,e)) { |
370 /// ... |
418 /// ... |
371 /// } |
419 /// } |
372 ///\endcode |
420 ///\endcode |
373 // /// \todo We may want to use the "GraphBase" |
|
374 // /// interface here... |
|
375 template <typename Graph> |
421 template <typename Graph> |
376 inline typename Graph::UEdge |
422 inline typename Graph::UEdge findEdge(const Graph &g, |
377 findUEdge(const Graph &g, |
423 typename Graph::Node u, |
378 typename Graph::Node u, |
424 typename Graph::Node v, |
379 typename Graph::Node v, |
425 typename Graph::UEdge prev = INVALID) { |
380 typename Graph::UEdge prev = INVALID) { |
426 return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, prev); |
381 return _findUEdge<Graph>(g, u, v, prev); |
|
382 } |
427 } |
383 |
428 |
384 /// \brief Iterator for iterating on uedges connected the same nodes. |
429 /// \brief Iterator for iterating on uedges connected the same nodes. |
385 /// |
430 /// |
386 /// Iterator for iterating on uedges connected the same nodes. It is |
431 /// Iterator for iterating on uedges connected the same nodes. It is |