108 /// |
108 /// |
109 /// \brief Find the connected components of an undirected graph |
109 /// \brief Find the connected components of an undirected graph |
110 /// |
110 /// |
111 /// Find the connected components of an undirected graph. |
111 /// Find the connected components of an undirected graph. |
112 /// |
112 /// |
|
113 /// \image html connected_components.png |
|
114 /// \image latex connected_components.eps "Connected components" width=\textwidth |
|
115 /// |
113 /// \param g The graph. In must be undirected. |
116 /// \param g The graph. In must be undirected. |
114 /// \retval comp A writable node map. The values will be set from 0 to |
117 /// \retval comp A writable node map. The values will be set from 0 to |
115 /// the number of the connected components minus one. Each values of the map |
118 /// the number of the connected components minus one. Each values of the map |
116 /// will be set exactly once, the values of a certain component will be |
119 /// will be set exactly once, the values of a certain component will be |
117 /// set continuously. |
120 /// set continuously. |
118 /// \return The number of components |
121 /// \return The number of components |
|
122 /// |
119 template <class UndirGraph, class NodeMap> |
123 template <class UndirGraph, class NodeMap> |
120 int connectedComponents(const UndirGraph &graph, NodeMap &compMap) { |
124 int connectedComponents(const UndirGraph &graph, NodeMap &compMap) { |
121 checkConcept<concept::UndirGraph, UndirGraph>(); |
125 checkConcept<concept::UndirGraph, UndirGraph>(); |
122 typedef typename UndirGraph::Node Node; |
126 typedef typename UndirGraph::Node Node; |
123 typedef typename UndirGraph::Edge Edge; |
127 typedef typename UndirGraph::Edge Edge; |
346 /// Find the strongly connected components of a directed graph. |
350 /// Find the strongly connected components of a directed graph. |
347 /// The strongly connected components are the classes of an equivalence |
351 /// The strongly connected components are the classes of an equivalence |
348 /// relation on the nodes of the graph. Two nodes are in relationship |
352 /// relation on the nodes of the graph. Two nodes are in relationship |
349 /// when there are directed paths between them in both direction. |
353 /// when there are directed paths between them in both direction. |
350 /// |
354 /// |
|
355 /// \image html strongly_connected_components.png |
|
356 /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth |
|
357 /// |
351 /// \param g The graph. |
358 /// \param g The graph. |
352 /// \retval comp A writable node map. The values will be set from 0 to |
359 /// \retval comp A writable node map. The values will be set from 0 to |
353 /// the number of the strongly connected components minus one. Each values |
360 /// the number of the strongly connected components minus one. Each values |
354 /// of the map will be set exactly once, the values of a certain component |
361 /// of the map will be set exactly once, the values of a certain component |
355 /// will be set continuously. |
362 /// will be set continuously. |
356 /// \return The number of components |
363 /// \return The number of components |
|
364 /// |
357 template <typename Graph, typename NodeMap> |
365 template <typename Graph, typename NodeMap> |
358 int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) { |
366 int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) { |
359 checkConcept<concept::StaticGraph, Graph>(); |
367 checkConcept<concept::StaticGraph, Graph>(); |
360 typedef typename Graph::Node Node; |
368 typedef typename Graph::Node Node; |
361 typedef typename Graph::NodeIt NodeIt; |
369 typedef typename Graph::NodeIt NodeIt; |
744 /// This function finds the node biconnected components in an undirected |
752 /// This function finds the node biconnected components in an undirected |
745 /// graph. The node biconnected components are the classes of an equivalence |
753 /// graph. The node biconnected components are the classes of an equivalence |
746 /// relation on the undirected edges. Two undirected edge are in relationship |
754 /// relation on the undirected edges. Two undirected edge are in relationship |
747 /// when they are on same circle. |
755 /// when they are on same circle. |
748 /// |
756 /// |
|
757 /// \image html node_biconnected_components.png |
|
758 /// \image latex node_biconnected_components.eps "Node biconnected components" width=\textwidth |
|
759 /// |
749 /// \param graph The graph. |
760 /// \param graph The graph. |
750 /// \retval comp A writable undir edge map. The values will be set from 0 to |
761 /// \retval comp A writable undir edge map. The values will be set from 0 to |
751 /// the number of the biconnected components minus one. Each values |
762 /// the number of the biconnected components minus one. Each values |
752 /// of the map will be set exactly once, the values of a certain component |
763 /// of the map will be set exactly once, the values of a certain component |
753 /// will be set continuously. |
764 /// will be set continuously. |
754 /// \return The number of components. |
765 /// \return The number of components. |
|
766 /// |
755 template <typename UndirGraph, typename UndirEdgeMap> |
767 template <typename UndirGraph, typename UndirEdgeMap> |
756 int nodeBiconnectedComponents(const UndirGraph& graph, |
768 int nodeBiconnectedComponents(const UndirGraph& graph, |
757 UndirEdgeMap& compMap) { |
769 UndirEdgeMap& compMap) { |
758 checkConcept<concept::UndirGraph, UndirGraph>(); |
770 checkConcept<concept::UndirGraph, UndirGraph>(); |
759 typedef typename UndirGraph::NodeIt NodeIt; |
771 typedef typename UndirGraph::NodeIt NodeIt; |
1067 /// This function finds the edge biconnected components in an undirected |
1079 /// This function finds the edge biconnected components in an undirected |
1068 /// graph. The edge biconnected components are the classes of an equivalence |
1080 /// graph. The edge biconnected components are the classes of an equivalence |
1069 /// relation on the nodes. Two nodes are in relationship when they are |
1081 /// relation on the nodes. Two nodes are in relationship when they are |
1070 /// connected at least two edge-disjoint paths. |
1082 /// connected at least two edge-disjoint paths. |
1071 /// |
1083 /// |
|
1084 /// \image html edge_biconnected_components.png |
|
1085 /// \image latex edge_biconnected_components.eps "Edge biconnected components" width=\textwidth |
|
1086 /// |
1072 /// \param graph The graph. |
1087 /// \param graph The graph. |
1073 /// \retval comp A writable node map. The values will be set from 0 to |
1088 /// \retval comp A writable node map. The values will be set from 0 to |
1074 /// the number of the biconnected components minus one. Each values |
1089 /// the number of the biconnected components minus one. Each values |
1075 /// of the map will be set exactly once, the values of a certain component |
1090 /// of the map will be set exactly once, the values of a certain component |
1076 /// will be set continuously. |
1091 /// will be set continuously. |
1077 /// \return The number of components. |
1092 /// \return The number of components. |
|
1093 /// |
1078 template <typename UndirGraph, typename NodeMap> |
1094 template <typename UndirGraph, typename NodeMap> |
1079 int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) { |
1095 int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) { |
1080 checkConcept<concept::UndirGraph, UndirGraph>(); |
1096 checkConcept<concept::UndirGraph, UndirGraph>(); |
1081 typedef typename UndirGraph::NodeIt NodeIt; |
1097 typedef typename UndirGraph::NodeIt NodeIt; |
1082 typedef typename UndirGraph::Node Node; |
1098 typedef typename UndirGraph::Node Node; |
1320 while (!dfs.emptyQueue()) { |
1336 while (!dfs.emptyQueue()) { |
1321 Edge edge = dfs.nextEdge(); |
1337 Edge edge = dfs.nextEdge(); |
1322 Node source = graph.source(edge); |
1338 Node source = graph.source(edge); |
1323 Node target = graph.target(edge); |
1339 Node target = graph.target(edge); |
1324 if (dfs.reached(target) && |
1340 if (dfs.reached(target) && |
1325 dfs.pred(source) != graph.oppositeEdge(edge)) { |
1341 dfs.predEdge(source) != graph.oppositeEdge(edge)) { |
1326 return false; |
1342 return false; |
1327 } |
1343 } |
1328 dfs.processNextEdge(); |
1344 dfs.processNextEdge(); |
1329 } |
1345 } |
1330 } |
1346 } |
1351 while (!dfs.emptyQueue()) { |
1367 while (!dfs.emptyQueue()) { |
1352 Edge edge = dfs.nextEdge(); |
1368 Edge edge = dfs.nextEdge(); |
1353 Node source = graph.source(edge); |
1369 Node source = graph.source(edge); |
1354 Node target = graph.target(edge); |
1370 Node target = graph.target(edge); |
1355 if (dfs.reached(target) && |
1371 if (dfs.reached(target) && |
1356 dfs.pred(source) != graph.oppositeEdge(edge)) { |
1372 dfs.predEdge(source) != graph.oppositeEdge(edge)) { |
1357 return false; |
1373 return false; |
1358 } |
1374 } |
1359 dfs.processNextEdge(); |
1375 dfs.processNextEdge(); |
1360 } |
1376 } |
1361 for (NodeIt it(graph); it != INVALID; ++it) { |
1377 for (NodeIt it(graph); it != INVALID; ++it) { |