lemon/connectivity.h
changeset 599 f63e87b9748e
parent 559 c5fd2d996909
child 647 dcba640438c7
     1.1 --- a/lemon/connectivity.h	Sat Apr 18 21:54:30 2009 +0200
     1.2 +++ b/lemon/connectivity.h	Tue Apr 21 10:34:49 2009 +0100
     1.3 @@ -32,7 +32,7 @@
     1.4  #include <stack>
     1.5  #include <functional>
     1.6  
     1.7 -/// \ingroup connectivity
     1.8 +/// \ingroup graph_properties
     1.9  /// \file
    1.10  /// \brief Connectivity algorithms
    1.11  ///
    1.12 @@ -40,7 +40,7 @@
    1.13  
    1.14  namespace lemon {
    1.15  
    1.16 -  /// \ingroup connectivity
    1.17 +  /// \ingroup graph_properties
    1.18    ///
    1.19    /// \brief Check whether the given undirected graph is connected.
    1.20    ///
    1.21 @@ -63,7 +63,7 @@
    1.22      return true;
    1.23    }
    1.24  
    1.25 -  /// \ingroup connectivity
    1.26 +  /// \ingroup graph_properties
    1.27    ///
    1.28    /// \brief Count the number of connected components of an undirected graph
    1.29    ///
    1.30 @@ -105,19 +105,21 @@
    1.31      return compNum;
    1.32    }
    1.33  
    1.34 -  /// \ingroup connectivity
    1.35 +  /// \ingroup graph_properties
    1.36    ///
    1.37    /// \brief Find the connected components of an undirected graph
    1.38    ///
    1.39    /// Find the connected components of an undirected graph.
    1.40    ///
    1.41 +  /// \image html connected_components.png
    1.42 +  /// \image latex connected_components.eps "Connected components" width=\textwidth
    1.43 +  ///
    1.44    /// \param graph The graph. It must be undirected.
    1.45    /// \retval compMap A writable node map. The values will be set from 0 to
    1.46    /// the number of the connected components minus one. Each values of the map
    1.47    /// will be set exactly once, the values of a certain component will be
    1.48    /// set continuously.
    1.49    /// \return The number of components
    1.50 -  ///
    1.51    template <class Graph, class NodeMap>
    1.52    int connectedComponents(const Graph &graph, NodeMap &compMap) {
    1.53      checkConcept<concepts::Graph, Graph>();
    1.54 @@ -227,7 +229,7 @@
    1.55    }
    1.56  
    1.57  
    1.58 -  /// \ingroup connectivity
    1.59 +  /// \ingroup graph_properties
    1.60    ///
    1.61    /// \brief Check whether the given directed graph is strongly connected.
    1.62    ///
    1.63 @@ -285,7 +287,7 @@
    1.64      return true;
    1.65    }
    1.66  
    1.67 -  /// \ingroup connectivity
    1.68 +  /// \ingroup graph_properties
    1.69    ///
    1.70    /// \brief Count the strongly connected components of a directed graph
    1.71    ///
    1.72 @@ -349,7 +351,7 @@
    1.73      return compNum;
    1.74    }
    1.75  
    1.76 -  /// \ingroup connectivity
    1.77 +  /// \ingroup graph_properties
    1.78    ///
    1.79    /// \brief Find the strongly connected components of a directed graph
    1.80    ///
    1.81 @@ -361,13 +363,15 @@
    1.82    /// that there is no arc going from a higher numbered component to
    1.83    /// a lower.
    1.84    ///
    1.85 +  /// \image html strongly_connected_components.png
    1.86 +  /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
    1.87 +  ///
    1.88    /// \param digraph The digraph.
    1.89    /// \retval compMap A writable node map. The values will be set from 0 to
    1.90    /// the number of the strongly connected components minus one. Each value
    1.91    /// of the map will be set exactly once, the values of a certain component
    1.92    /// will be set continuously.
    1.93    /// \return The number of components
    1.94 -  ///
    1.95    template <typename Digraph, typename NodeMap>
    1.96    int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
    1.97      checkConcept<concepts::Digraph, Digraph>();
    1.98 @@ -416,7 +420,7 @@
    1.99      return compNum;
   1.100    }
   1.101  
   1.102 -  /// \ingroup connectivity
   1.103 +  /// \ingroup graph_properties
   1.104    ///
   1.105    /// \brief Find the cut arcs of the strongly connected components.
   1.106    ///
   1.107 @@ -700,7 +704,7 @@
   1.108    template <typename Graph>
   1.109    int countBiNodeConnectedComponents(const Graph& graph);
   1.110  
   1.111 -  /// \ingroup connectivity
   1.112 +  /// \ingroup graph_properties
   1.113    ///
   1.114    /// \brief Checks the graph is bi-node-connected.
   1.115    ///
   1.116 @@ -715,7 +719,7 @@
   1.117      return countBiNodeConnectedComponents(graph) <= 1;
   1.118    }
   1.119  
   1.120 -  /// \ingroup connectivity
   1.121 +  /// \ingroup graph_properties
   1.122    ///
   1.123    /// \brief Count the biconnected components.
   1.124    ///
   1.125 @@ -750,7 +754,7 @@
   1.126      return compNum;
   1.127    }
   1.128  
   1.129 -  /// \ingroup connectivity
   1.130 +  /// \ingroup graph_properties
   1.131    ///
   1.132    /// \brief Find the bi-node-connected components.
   1.133    ///
   1.134 @@ -759,13 +763,15 @@
   1.135    /// relation on the undirected edges. Two undirected edge are in relationship
   1.136    /// when they are on same circle.
   1.137    ///
   1.138 +  /// \image html node_biconnected_components.png
   1.139 +  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
   1.140 +  ///
   1.141    /// \param graph The graph.
   1.142    /// \retval compMap A writable uedge map. The values will be set from 0
   1.143    /// to the number of the biconnected components minus one. Each values
   1.144    /// of the map will be set exactly once, the values of a certain component
   1.145    /// will be set continuously.
   1.146    /// \return The number of components.
   1.147 -  ///
   1.148    template <typename Graph, typename EdgeMap>
   1.149    int biNodeConnectedComponents(const Graph& graph,
   1.150                                  EdgeMap& compMap) {
   1.151 @@ -793,7 +799,7 @@
   1.152      return compNum;
   1.153    }
   1.154  
   1.155 -  /// \ingroup connectivity
   1.156 +  /// \ingroup graph_properties
   1.157    ///
   1.158    /// \brief Find the bi-node-connected cut nodes.
   1.159    ///
   1.160 @@ -1023,7 +1029,7 @@
   1.161    template <typename Graph>
   1.162    int countBiEdgeConnectedComponents(const Graph& graph);
   1.163  
   1.164 -  /// \ingroup connectivity
   1.165 +  /// \ingroup graph_properties
   1.166    ///
   1.167    /// \brief Checks that the graph is bi-edge-connected.
   1.168    ///
   1.169 @@ -1038,7 +1044,7 @@
   1.170      return countBiEdgeConnectedComponents(graph) <= 1;
   1.171    }
   1.172  
   1.173 -  /// \ingroup connectivity
   1.174 +  /// \ingroup graph_properties
   1.175    ///
   1.176    /// \brief Count the bi-edge-connected components.
   1.177    ///
   1.178 @@ -1073,7 +1079,7 @@
   1.179      return compNum;
   1.180    }
   1.181  
   1.182 -  /// \ingroup connectivity
   1.183 +  /// \ingroup graph_properties
   1.184    ///
   1.185    /// \brief Find the bi-edge-connected components.
   1.186    ///
   1.187 @@ -1082,13 +1088,15 @@
   1.188    /// relation on the nodes. Two nodes are in relationship when they are
   1.189    /// connected at least two edge-disjoint paths.
   1.190    ///
   1.191 +  /// \image html edge_biconnected_components.png
   1.192 +  /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
   1.193 +  ///
   1.194    /// \param graph The graph.
   1.195    /// \retval compMap A writable node map. The values will be set from 0 to
   1.196    /// the number of the biconnected components minus one. Each values
   1.197    /// of the map will be set exactly once, the values of a certain component
   1.198    /// will be set continuously.
   1.199    /// \return The number of components.
   1.200 -  ///
   1.201    template <typename Graph, typename NodeMap>
   1.202    int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
   1.203      checkConcept<concepts::Graph, Graph>();
   1.204 @@ -1115,7 +1123,7 @@
   1.205      return compNum;
   1.206    }
   1.207  
   1.208 -  /// \ingroup connectivity
   1.209 +  /// \ingroup graph_properties
   1.210    ///
   1.211    /// \brief Find the bi-edge-connected cut edges.
   1.212    ///
   1.213 @@ -1179,7 +1187,7 @@
   1.214  
   1.215    }
   1.216  
   1.217 -  /// \ingroup connectivity
   1.218 +  /// \ingroup graph_properties
   1.219    ///
   1.220    /// \brief Sort the nodes of a DAG into topolgical order.
   1.221    ///
   1.222 @@ -1218,7 +1226,7 @@
   1.223      }
   1.224    }
   1.225  
   1.226 -  /// \ingroup connectivity
   1.227 +  /// \ingroup graph_properties
   1.228    ///
   1.229    /// \brief Sort the nodes of a DAG into topolgical order.
   1.230    ///
   1.231 @@ -1273,7 +1281,7 @@
   1.232      return true;
   1.233    }
   1.234  
   1.235 -  /// \ingroup connectivity
   1.236 +  /// \ingroup graph_properties
   1.237    ///
   1.238    /// \brief Check that the given directed graph is a DAG.
   1.239    ///
   1.240 @@ -1315,7 +1323,7 @@
   1.241      return true;
   1.242    }
   1.243  
   1.244 -  /// \ingroup connectivity
   1.245 +  /// \ingroup graph_properties
   1.246    ///
   1.247    /// \brief Check that the given undirected graph is acyclic.
   1.248    ///
   1.249 @@ -1349,7 +1357,7 @@
   1.250      return true;
   1.251    }
   1.252  
   1.253 -  /// \ingroup connectivity
   1.254 +  /// \ingroup graph_properties
   1.255    ///
   1.256    /// \brief Check that the given undirected graph is tree.
   1.257    ///
   1.258 @@ -1441,7 +1449,7 @@
   1.259      };
   1.260    }
   1.261  
   1.262 -  /// \ingroup connectivity
   1.263 +  /// \ingroup graph_properties
   1.264    ///
   1.265    /// \brief Check if the given undirected graph is bipartite or not
   1.266    ///
   1.267 @@ -1478,7 +1486,7 @@
   1.268      return true;
   1.269    }
   1.270  
   1.271 -  /// \ingroup connectivity
   1.272 +  /// \ingroup graph_properties
   1.273    ///
   1.274    /// \brief Check if the given undirected graph is bipartite or not
   1.275    ///
   1.276 @@ -1486,6 +1494,10 @@
   1.277    /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
   1.278    /// During the execution, the \c partMap will be set as the two
   1.279    /// partitions of the graph.
   1.280 +  ///
   1.281 +  /// \image html bipartite_partitions.png
   1.282 +  /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
   1.283 +  ///
   1.284    /// \param graph The undirected graph.
   1.285    /// \retval partMap A writable bool map of nodes. It will be set as the
   1.286    /// two partitions of the graph.