46 /// \brief Check that the given undirected graph is connected. |
46 /// \brief Check that the given undirected graph is connected. |
47 /// |
47 /// |
48 /// Check that the given undirected graph connected. |
48 /// Check that the given undirected graph connected. |
49 /// \param graph The undirected graph. |
49 /// \param graph The undirected graph. |
50 /// \return %True when there is path between any two nodes in the graph. |
50 /// \return %True when there is path between any two nodes in the graph. |
51 /// \warning The empty graph is not connected. |
51 /// \note By definition, the empty graph is connected. |
52 template <typename UndirGraph> |
52 template <typename UndirGraph> |
53 bool connected(const UndirGraph& graph) { |
53 bool connected(const UndirGraph& graph) { |
54 checkConcept<concept::UndirGraph, UndirGraph>(); |
54 checkConcept<concept::UndirGraph, UndirGraph>(); |
55 typedef typename UndirGraph::NodeIt NodeIt; |
55 typedef typename UndirGraph::NodeIt NodeIt; |
56 if (NodeIt(graph) == INVALID) return false; |
56 if (NodeIt(graph) == INVALID) return true; |
57 Dfs<UndirGraph> dfs(graph); |
57 Dfs<UndirGraph> dfs(graph); |
58 dfs.run(NodeIt(graph)); |
58 dfs.run(NodeIt(graph)); |
59 for (NodeIt it(graph); it != INVALID; ++it) { |
59 for (NodeIt it(graph); it != INVALID; ++it) { |
60 if (!dfs.reached(it)) { |
60 if (!dfs.reached(it)) { |
61 return false; |
61 return false; |
70 /// |
70 /// |
71 /// Count the number of connected components of an undirected graph |
71 /// Count the number of connected components of an undirected graph |
72 /// |
72 /// |
73 /// \param graph The graph. It should be undirected. |
73 /// \param graph The graph. It should be undirected. |
74 /// \return The number of components |
74 /// \return The number of components |
|
75 /// \note By definition, the empty graph consists |
|
76 /// of zero connected components. |
75 template <typename UndirGraph> |
77 template <typename UndirGraph> |
76 int countConnectedComponents(const UndirGraph &graph) { |
78 int countConnectedComponents(const UndirGraph &graph) { |
77 checkConcept<concept::UndirGraph, UndirGraph>(); |
79 checkConcept<concept::UndirGraph, UndirGraph>(); |
78 typedef typename UndirGraph::Node Node; |
80 typedef typename UndirGraph::Node Node; |
79 typedef typename UndirGraph::Edge Edge; |
81 typedef typename UndirGraph::Edge Edge; |
235 /// graph is strongly connected when any two nodes of the graph are |
237 /// graph is strongly connected when any two nodes of the graph are |
236 /// connected with directed pathes in both direction. |
238 /// connected with directed pathes in both direction. |
237 /// \return %False when the graph is not strongly connected. |
239 /// \return %False when the graph is not strongly connected. |
238 /// \see connected |
240 /// \see connected |
239 /// |
241 /// |
240 /// \warning Empty graph is not strongly connected. |
242 /// \note By definition, the empty graph is strongly connected. |
241 template <typename Graph> |
243 template <typename Graph> |
242 bool stronglyConnected(const Graph& graph) { |
244 bool stronglyConnected(const Graph& graph) { |
243 checkConcept<concept::StaticGraph, Graph>(); |
245 checkConcept<concept::StaticGraph, Graph>(); |
244 if (NodeIt(graph) == INVALID) return false; |
246 if (NodeIt(graph) == INVALID) return true; |
245 |
247 |
246 typedef typename Graph::Node Node; |
248 typedef typename Graph::Node Node; |
247 typedef typename Graph::NodeIt NodeIt; |
249 typedef typename Graph::NodeIt NodeIt; |
248 |
250 |
249 using namespace _topology_bits; |
251 using namespace _topology_bits; |
291 /// relation on the nodes of the graph. Two nodes are connected with |
293 /// relation on the nodes of the graph. Two nodes are connected with |
292 /// directed paths in both direction. |
294 /// directed paths in both direction. |
293 /// |
295 /// |
294 /// \param graph The graph. |
296 /// \param graph The graph. |
295 /// \return The number of components |
297 /// \return The number of components |
|
298 /// \note By definition, the empty graph has zero |
|
299 /// strongly connected components. |
296 template <typename Graph> |
300 template <typename Graph> |
297 int countStronglyConnectedComponents(const Graph& graph) { |
301 int countStronglyConnectedComponents(const Graph& graph) { |
298 checkConcept<concept::StaticGraph, Graph>(); |
302 checkConcept<concept::StaticGraph, Graph>(); |
299 |
303 |
300 using namespace _topology_bits; |
304 using namespace _topology_bits; |
354 /// |
358 /// |
355 /// \image html strongly_connected_components.png |
359 /// \image html strongly_connected_components.png |
356 /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth |
360 /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth |
357 /// |
361 /// |
358 /// \param graph The graph. |
362 /// \param graph The graph. |
359 /// \param compMap A writable node map. The values will be set from 0 to |
|
360 /// the number of the connected components minus one. Each values of the map |
|
361 /// will be set exactly once, the values of a certain component will be |
|
362 /// set continuously. |
|
363 /// \retval compMap A writable node map. The values will be set from 0 to |
363 /// \retval compMap A writable node map. The values will be set from 0 to |
364 /// the number of the strongly connected components minus one. Each values |
364 /// the number of the strongly connected components minus one. Each values |
365 /// of the map will be set exactly once, the values of a certain component |
365 /// of the map will be set exactly once, the values of a certain component |
366 /// will be set continuously. |
366 /// will be set continuously. |
367 /// \return The number of components |
367 /// \return The number of components |