246 ///the number of the connected components minus one. Each values of the map |
247 ///the number of the connected components minus one. Each values of the map |
247 ///will be set exactly once, the values of a certain component will be |
248 ///will be set exactly once, the values of a certain component will be |
248 ///set continuously. |
249 ///set continuously. |
249 ///\return The number of components |
250 ///\return The number of components |
250 ///\todo Test required |
251 ///\todo Test required |
251 template<class UGraph, class WMap> |
252 template <class UndirGraph, class IntNodeMap> |
252 int connectedComponents(const UGraph &g, WMap &comp) |
253 int connectedComponents(const UndirGraph &g, IntNodeMap &comp) { |
253 { |
254 checkConcept<concept::UndirGraph, UndirGraph>(); |
254 int c=0; |
255 checkConcept<concept::WriteMap<typename UndirGraph::Node, int>, |
255 Bfs<Graph> bfs(g); |
256 IntNodeMap>(); |
|
257 int c = 0; |
|
258 Bfs<UndirGraph> bfs(g); |
256 bfs.init(); |
259 bfs.init(); |
257 for(typename Graph::NodeIt n(g);n!=INVALID;++n) |
260 for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) { |
258 if(!bfs.reached(n)) { |
261 if(!bfs.reached(n)) { |
259 bfs.addSource(n); |
262 bfs.addSource(n); |
260 while ( bfs.nextNode()!=INVALID ) { |
263 while (!bfs.emptyQueue()) { |
261 comp[bfs.nextNode()]=c; |
264 comp[bfs.nextNode()] = c; |
262 processNextNode(); |
265 bfs.processNextNode(); |
263 c++; |
266 } |
264 } |
267 ++c; |
|
268 } |
|
269 } |
265 return c; |
270 return c; |
266 } |
271 } |
267 |
272 |
|
273 namespace _components_bits { |
|
274 |
|
275 template <typename Key, typename IntMap> |
|
276 struct FillWriteMap : public MapBase<Key, bool> { |
|
277 public: |
|
278 FillWriteMap(IntMap& _map, int& _comp) |
|
279 : map(_map), comp(_comp) {} |
|
280 void set(Key key, bool value) { |
|
281 if (value) { map.set(key, comp); } |
|
282 } |
|
283 private: |
|
284 IntMap& map; |
|
285 int& comp; |
|
286 }; |
|
287 |
|
288 template <typename Key, typename Container = std::vector<Key> > |
|
289 struct BackInserterWriteMap : public MapBase<Key, bool> { |
|
290 public: |
|
291 BackInserterWriteMap(Container& _container) |
|
292 : container(_container) {} |
|
293 void set(Key key, bool value) { |
|
294 if (value) { container.push_back(key); } |
|
295 } |
|
296 private: |
|
297 Container& container; |
|
298 }; |
|
299 |
|
300 } |
|
301 |
|
302 /// \brief Count the strongly connected components of a directed graph |
|
303 /// |
|
304 /// Count the strongly connected components of a directed graph |
|
305 /// |
|
306 /// \param g The graph. |
|
307 /// \return The number of components |
|
308 template <typename Graph> |
|
309 int countStronglyConnectedComponents(const Graph& graph) { |
|
310 checkConcept<concept::StaticGraph, Graph>(); |
|
311 |
|
312 using namespace _components_bits; |
|
313 |
|
314 typedef typename Graph::Node Node; |
|
315 typedef typename Graph::Edge Edge; |
|
316 typedef typename Graph::NodeIt NodeIt; |
|
317 typedef typename Graph::EdgeIt EdgeIt; |
|
318 |
|
319 |
|
320 typename Dfs<Graph>:: |
|
321 template DefProcessedMap<BackInserterWriteMap<Node> >:: |
|
322 Create dfs(graph); |
|
323 |
|
324 std::vector<Node> nodes; |
|
325 BackInserterWriteMap<Node> processed(nodes); |
|
326 dfs.processedMap(processed); |
|
327 |
|
328 dfs.init(); |
|
329 for (NodeIt it(graph); it != INVALID; ++it) { |
|
330 if (!dfs.reached(it)) { |
|
331 dfs.addSource(it); |
|
332 dfs.start(); |
|
333 } |
|
334 } |
|
335 |
|
336 typedef RevGraphAdaptor<const Graph> RGraph; |
|
337 |
|
338 RGraph rgraph(graph); |
|
339 |
|
340 Dfs<RGraph> rdfs(rgraph); |
|
341 |
|
342 int num = 0; |
|
343 |
|
344 rdfs.init(); |
|
345 for (typename std::vector<Node>::reverse_iterator |
|
346 it = nodes.rbegin(); it != nodes.rend(); ++it) { |
|
347 if (!rdfs.reached(*it)) { |
|
348 rdfs.addSource(*it); |
|
349 rdfs.start(); |
|
350 ++num; |
|
351 } |
|
352 } |
|
353 return num; |
|
354 } |
|
355 |
|
356 /// \brief Find the strongly connected components of a directed graph |
|
357 /// |
|
358 /// Find the strongly connected components of a directed graph |
|
359 /// |
|
360 /// \param g The graph. |
|
361 /// \retval comp A writable node map. The values will be set from 0 to |
|
362 /// the number of the strongly connected components minus one. Each values |
|
363 /// of the map will be set exactly once, the values of a certain component |
|
364 /// will be set continuously. |
|
365 /// \return The number of components |
|
366 template <typename Graph, typename IntNodeMap> |
|
367 int stronglyConnectedComponents(const Graph& graph, IntNodeMap& comp) { |
|
368 checkConcept<concept::StaticGraph, Graph>(); |
|
369 checkConcept<concept::WriteMap<typename Graph::Node, int>, IntNodeMap>(); |
|
370 |
|
371 using namespace _components_bits; |
|
372 |
|
373 typedef typename Graph::Node Node; |
|
374 typedef typename Graph::Edge Edge; |
|
375 typedef typename Graph::NodeIt NodeIt; |
|
376 typedef typename Graph::EdgeIt EdgeIt; |
|
377 |
|
378 |
|
379 typename Dfs<Graph>:: |
|
380 template DefProcessedMap<BackInserterWriteMap<Node> >:: |
|
381 Create dfs(graph); |
|
382 |
|
383 std::vector<Node> nodes; |
|
384 BackInserterWriteMap<Node> processed(nodes); |
|
385 dfs.processedMap(processed); |
|
386 |
|
387 dfs.init(); |
|
388 for (NodeIt it(graph); it != INVALID; ++it) { |
|
389 if (!dfs.reached(it)) { |
|
390 dfs.addSource(it); |
|
391 dfs.start(); |
|
392 } |
|
393 } |
|
394 |
|
395 typedef RevGraphAdaptor<const Graph> RGraph; |
|
396 |
|
397 RGraph rgraph(graph); |
|
398 |
|
399 typename Dfs<RGraph>:: |
|
400 template DefProcessedMap<FillWriteMap<Node, IntNodeMap> >:: |
|
401 Create rdfs(rgraph); |
|
402 |
|
403 int num = 0; |
|
404 FillWriteMap<Node, IntNodeMap> rprocessed(comp, num); |
|
405 rdfs.processedMap(rprocessed); |
|
406 |
|
407 rdfs.init(); |
|
408 for (typename std::vector<Node>::reverse_iterator |
|
409 it = nodes.rbegin(); it != nodes.rend(); ++it) { |
|
410 if (!rdfs.reached(*it)) { |
|
411 rdfs.addSource(*it); |
|
412 rdfs.start(); |
|
413 ++num; |
|
414 } |
|
415 } |
|
416 return num; |
|
417 } |
|
418 |
268 } //namespace lemon |
419 } //namespace lemon |
269 |
420 |
270 #endif //LEMON_TOPOLOGY_H |
421 #endif //LEMON_TOPOLOGY_H |