author Peter Kovacs Wed, 06 May 2009 14:44:05 +0200 changeset 695 4ff8041e9c2e parent 694 dcba640438c7 child 696 76cbcb3e9bbb
Doc improvements and fixes for connectivity tools (#285)
And add loopFree(), parallelFree(), simpleGraph() to the module doc.
 lemon/connectivity.h file | annotate | diff | comparison | revisions lemon/euler.h file | annotate | diff | comparison | revisions
     1.1 --- a/lemon/connectivity.h	Wed May 06 14:37:44 2009 +0200
1.2 +++ b/lemon/connectivity.h	Wed May 06 14:44:05 2009 +0200
1.3 @@ -42,12 +42,16 @@
1.4
1.5    /// \ingroup graph_properties
1.6    ///
1.7 -  /// \brief Check whether the given undirected graph is connected.
1.8 +  /// \brief Check whether an undirected graph is connected.
1.9    ///
1.10 -  /// Check whether the given undirected graph is connected.
1.11 -  /// \param graph The undirected graph.
1.12 -  /// \return \c true when there is path between any two nodes in the graph.
1.13 +  /// This function checks whether the given undirected graph is connected,
1.14 +  /// i.e. there is a path between any two nodes in the graph.
1.15 +  ///
1.16 +  /// \return \c true if the graph is connected.
1.17    /// \note By definition, the empty graph is connected.
1.18 +  ///
1.19 +  /// \see countConnectedComponents(), connectedComponents()
1.20 +  /// \see stronglyConnected()
1.21    template <typename Graph>
1.22    bool connected(const Graph& graph) {
1.23      checkConcept<concepts::Graph, Graph>();
1.24 @@ -67,12 +71,18 @@
1.25    ///
1.26    /// \brief Count the number of connected components of an undirected graph
1.27    ///
1.28 -  /// Count the number of connected components of an undirected graph
1.29 +  /// This function counts the number of connected components of the given
1.30 +  /// undirected graph.
1.31    ///
1.32 -  /// \param graph The graph. It must be undirected.
1.33 -  /// \return The number of components
1.34 +  /// The connected components are the classes of an equivalence relation
1.35 +  /// on the nodes of an undirected graph. Two nodes are in the same class
1.36 +  /// if they are connected with a path.
1.37 +  ///
1.38 +  /// \return The number of connected components.
1.39    /// \note By definition, the empty graph consists
1.40    /// of zero connected components.
1.41 +  ///
1.42 +  /// \see connected(), connectedComponents()
1.43    template <typename Graph>
1.44    int countConnectedComponents(const Graph &graph) {
1.45      checkConcept<concepts::Graph, Graph>();
1.46 @@ -109,17 +119,26 @@
1.47    ///
1.48    /// \brief Find the connected components of an undirected graph
1.49    ///
1.50 -  /// Find the connected components of an undirected graph.
1.51 +  /// This function finds the connected components of the given undirected
1.52 +  /// graph.
1.53 +  ///
1.54 +  /// The connected components are the classes of an equivalence relation
1.55 +  /// on the nodes of an undirected graph. Two nodes are in the same class
1.56 +  /// if they are connected with a path.
1.57    ///
1.58    /// \image html connected_components.png
1.59    /// \image latex connected_components.eps "Connected components" width=\textwidth
1.60    ///
1.61 -  /// \param graph The graph. It must be undirected.
1.62 +  /// \param graph The undirected graph.
1.63    /// \retval compMap A writable node map. The values will be set from 0 to
1.64 -  /// the number of the connected components minus one. Each values of the map
1.65 -  /// will be set exactly once, the values of a certain component will be
1.66 +  /// the number of the connected components minus one. Each value of the map
1.67 +  /// will be set exactly once, and the values of a certain component will be
1.68    /// set continuously.
1.69 -  /// \return The number of components
1.70 +  /// \return The number of connected components.
1.71 +  /// \note By definition, the empty graph consists
1.72 +  /// of zero connected components.
1.73 +  ///
1.74 +  /// \see connected(), countConnectedComponents()
1.75    template <class Graph, class NodeMap>
1.76    int connectedComponents(const Graph &graph, NodeMap &compMap) {
1.77      checkConcept<concepts::Graph, Graph>();
1.78 @@ -231,15 +250,17 @@
1.79
1.80    /// \ingroup graph_properties
1.81    ///
1.82 -  /// \brief Check whether the given directed graph is strongly connected.
1.83 +  /// \brief Check whether a directed graph is strongly connected.
1.84    ///
1.85 -  /// Check whether the given directed graph is strongly connected. The
1.86 -  /// graph is strongly connected when any two nodes of the graph are
1.87 +  /// This function checks whether the given directed graph is strongly
1.88 +  /// connected, i.e. any two nodes of the digraph are
1.89    /// connected with directed paths in both direction.
1.90 -  /// \return \c false when the graph is not strongly connected.
1.91 -  /// \see connected
1.92    ///
1.93 -  /// \note By definition, the empty graph is strongly connected.
1.94 +  /// \return \c true if the digraph is strongly connected.
1.95 +  /// \note By definition, the empty digraph is strongly connected.
1.96 +  ///
1.97 +  /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
1.98 +  /// \see connected()
1.99    template <typename Digraph>
1.100    bool stronglyConnected(const Digraph& digraph) {
1.101      checkConcept<concepts::Digraph, Digraph>();
1.102 @@ -270,7 +291,7 @@
1.103      typedef typename RDigraph::NodeIt RNodeIt;
1.104      RDigraph rdigraph(digraph);
1.105
1.106 -    typedef DfsVisitor<Digraph> RVisitor;
1.107 +    typedef DfsVisitor<RDigraph> RVisitor;
1.108      RVisitor rvisitor;
1.109
1.110      DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
1.111 @@ -289,18 +310,22 @@
1.112
1.113    /// \ingroup graph_properties
1.114    ///
1.115 -  /// \brief Count the strongly connected components of a directed graph
1.116 +  /// \brief Count the number of strongly connected components of a
1.117 +  /// directed graph
1.118    ///
1.119 -  /// Count the strongly connected components of a directed graph.
1.120 +  /// This function counts the number of strongly connected components of
1.121 +  /// the given directed graph.
1.122 +  ///
1.123    /// The strongly connected components are the classes of an
1.124 -  /// equivalence relation on the nodes of the graph. Two nodes are in
1.125 +  /// equivalence relation on the nodes of a digraph. Two nodes are in
1.126    /// the same class if they are connected with directed paths in both
1.127    /// direction.
1.128    ///
1.129 -  /// \param digraph The graph.
1.130 -  /// \return The number of components
1.131 -  /// \note By definition, the empty graph has zero
1.132 +  /// \return The number of strongly connected components.
1.133 +  /// \note By definition, the empty digraph has zero
1.134    /// strongly connected components.
1.135 +  ///
1.136 +  /// \see stronglyConnected(), stronglyConnectedComponents()
1.137    template <typename Digraph>
1.138    int countStronglyConnectedComponents(const Digraph& digraph) {
1.139      checkConcept<concepts::Digraph, Digraph>();
1.140 @@ -355,13 +380,15 @@
1.141    ///
1.142    /// \brief Find the strongly connected components of a directed graph
1.143    ///
1.144 -  /// Find the strongly connected components of a directed graph.  The
1.145 -  /// strongly connected components are the classes of an equivalence
1.146 -  /// relation on the nodes of the graph. Two nodes are in
1.147 -  /// relationship when there are directed paths between them in both
1.148 -  /// direction. In addition, the numbering of components will satisfy
1.149 -  /// that there is no arc going from a higher numbered component to
1.150 -  /// a lower.
1.151 +  /// This function finds the strongly connected components of the given
1.152 +  /// directed graph. In addition, the numbering of the components will
1.153 +  /// satisfy that there is no arc going from a higher numbered component
1.154 +  /// to a lower one (i.e. it provides a topological order of the components).
1.155 +  ///
1.156 +  /// The strongly connected components are the classes of an
1.157 +  /// equivalence relation on the nodes of a digraph. Two nodes are in
1.158 +  /// the same class if they are connected with directed paths in both
1.159 +  /// direction.
1.160    ///
1.161    /// \image html strongly_connected_components.png
1.162    /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
1.163 @@ -369,9 +396,13 @@
1.164    /// \param digraph The digraph.
1.165    /// \retval compMap A writable node map. The values will be set from 0 to
1.166    /// the number of the strongly connected components minus one. Each value
1.167 -  /// of the map will be set exactly once, the values of a certain component
1.168 -  /// will be set continuously.
1.169 -  /// \return The number of components
1.170 +  /// of the map will be set exactly once, and the values of a certain
1.171 +  /// component will be set continuously.
1.172 +  /// \return The number of strongly connected components.
1.173 +  /// \note By definition, the empty digraph has zero
1.174 +  /// strongly connected components.
1.175 +  ///
1.176 +  /// \see stronglyConnected(), countStronglyConnectedComponents()
1.177    template <typename Digraph, typename NodeMap>
1.178    int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
1.179      checkConcept<concepts::Digraph, Digraph>();
1.180 @@ -424,19 +455,24 @@
1.181    ///
1.182    /// \brief Find the cut arcs of the strongly connected components.
1.183    ///
1.184 -  /// Find the cut arcs of the strongly connected components.
1.185 -  /// The strongly connected components are the classes of an equivalence
1.186 -  /// relation on the nodes of the graph. Two nodes are in relationship
1.187 -  /// when there are directed paths between them in both direction.
1.188 +  /// This function finds the cut arcs of the strongly connected components
1.189 +  /// of the given digraph.
1.190 +  ///
1.191 +  /// The strongly connected components are the classes of an
1.192 +  /// equivalence relation on the nodes of a digraph. Two nodes are in
1.193 +  /// the same class if they are connected with directed paths in both
1.194 +  /// direction.
1.195    /// The strongly connected components are separated by the cut arcs.
1.196    ///
1.197 -  /// \param graph The graph.
1.198 -  /// \retval cutMap A writable node map. The values will be set true when the
1.199 -  /// arc is a cut arc.
1.200 +  /// \param digraph The digraph.
1.201 +  /// \retval cutMap A writable arc map. The values will be set to \c true
1.202 +  /// for the cut arcs (exactly once for each cut arc), and will not be
1.203 +  /// changed for other arcs.
1.204 +  /// \return The number of cut arcs.
1.205    ///
1.206 -  /// \return The number of cut arcs
1.207 +  /// \see stronglyConnected(), stronglyConnectedComponents()
1.208    template <typename Digraph, typename ArcMap>
1.209 -  int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
1.210 +  int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
1.211      checkConcept<concepts::Digraph, Digraph>();
1.212      typedef typename Digraph::Node Node;
1.213      typedef typename Digraph::Arc Arc;
1.214 @@ -448,13 +484,13 @@
1.215      typedef std::vector<Node> Container;
1.216      typedef typename Container::iterator Iterator;
1.217
1.218 -    Container nodes(countNodes(graph));
1.219 +    Container nodes(countNodes(digraph));
1.220      typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
1.221      Visitor visitor(nodes.begin());
1.222
1.223 -    DfsVisit<Digraph, Visitor> dfs(graph, visitor);
1.224 +    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
1.225      dfs.init();
1.226 -    for (NodeIt it(graph); it != INVALID; ++it) {
1.227 +    for (NodeIt it(digraph); it != INVALID; ++it) {
1.228        if (!dfs.reached(it)) {
1.230          dfs.start();
1.231 @@ -464,14 +500,14 @@
1.232      typedef typename Container::reverse_iterator RIterator;
1.233      typedef ReverseDigraph<const Digraph> RDigraph;
1.234
1.235 -    RDigraph rgraph(graph);
1.236 +    RDigraph rdigraph(digraph);
1.237
1.238      int cutNum = 0;
1.239
1.240      typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
1.241 -    RVisitor rvisitor(rgraph, cutMap, cutNum);
1.242 +    RVisitor rvisitor(rdigraph, cutMap, cutNum);
1.243
1.244 -    DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
1.245 +    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
1.246
1.247      rdfs.init();
1.248      for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
1.249 @@ -706,14 +742,15 @@
1.250
1.251    /// \ingroup graph_properties
1.252    ///
1.253 -  /// \brief Checks the graph is bi-node-connected.
1.254 +  /// \brief Check whether an undirected graph is bi-node-connected.
1.255    ///
1.256 -  /// This function checks that the undirected graph is bi-node-connected
1.257 -  /// graph. The graph is bi-node-connected if any two undirected edge is
1.258 -  /// on same circle.
1.259 +  /// This function checks whether the given undirected graph is
1.260 +  /// bi-node-connected, i.e. any two edges are on same circle.
1.261    ///
1.262 -  /// \param graph The graph.
1.263 -  /// \return \c true when the graph bi-node-connected.
1.264 +  /// \return \c true if the graph bi-node-connected.
1.265 +  /// \note By definition, the empty graph is bi-node-connected.
1.266 +  ///
1.267 +  /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
1.268    template <typename Graph>
1.269    bool biNodeConnected(const Graph& graph) {
1.270      return countBiNodeConnectedComponents(graph) <= 1;
1.271 @@ -721,15 +758,19 @@
1.272
1.273    /// \ingroup graph_properties
1.274    ///
1.275 -  /// \brief Count the biconnected components.
1.276 +  /// \brief Count the number of bi-node-connected components of an
1.277 +  /// undirected graph.
1.278    ///
1.279 -  /// This function finds the bi-node-connected components in an undirected
1.280 -  /// graph. The biconnected components are the classes of an equivalence
1.281 -  /// relation on the undirected edges. Two undirected edge is in relationship
1.282 -  /// when they are on same circle.
1.283 +  /// This function counts the number of bi-node-connected components of
1.284 +  /// the given undirected graph.
1.285    ///
1.286 -  /// \param graph The graph.
1.287 -  /// \return The number of components.
1.288 +  /// The bi-node-connected components are the classes of an equivalence
1.289 +  /// relation on the edges of a undirected graph. Two edges are in the
1.290 +  /// same class if they are on same circle.
1.291 +  ///
1.292 +  /// \return The number of bi-node-connected components.
1.293 +  ///
1.294 +  /// \see biNodeConnected(), biNodeConnectedComponents()
1.295    template <typename Graph>
1.296    int countBiNodeConnectedComponents(const Graph& graph) {
1.297      checkConcept<concepts::Graph, Graph>();
1.298 @@ -756,22 +797,26 @@
1.299
1.300    /// \ingroup graph_properties
1.301    ///
1.302 -  /// \brief Find the bi-node-connected components.
1.303 +  /// \brief Find the bi-node-connected components of an undirected graph.
1.304    ///
1.305 -  /// This function finds the bi-node-connected components in an undirected
1.306 -  /// graph. The bi-node-connected components are the classes of an equivalence
1.307 -  /// relation on the undirected edges. Two undirected edge are in relationship
1.308 -  /// when they are on same circle.
1.309 +  /// This function finds the bi-node-connected components of the given
1.310 +  /// undirected graph.
1.311 +  ///
1.312 +  /// The bi-node-connected components are the classes of an equivalence
1.313 +  /// relation on the edges of a undirected graph. Two edges are in the
1.314 +  /// same class if they are on same circle.
1.315    ///
1.316    /// \image html node_biconnected_components.png
1.317    /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
1.318    ///
1.319 -  /// \param graph The graph.
1.320 -  /// \retval compMap A writable uedge map. The values will be set from 0
1.321 -  /// to the number of the biconnected components minus one. Each values
1.322 -  /// of the map will be set exactly once, the values of a certain component
1.323 -  /// will be set continuously.
1.324 -  /// \return The number of components.
1.325 +  /// \param graph The undirected graph.
1.326 +  /// \retval compMap A writable edge map. The values will be set from 0
1.327 +  /// to the number of the bi-node-connected components minus one. Each
1.328 +  /// value of the map will be set exactly once, and the values of a
1.329 +  /// certain component will be set continuously.
1.330 +  /// \return The number of bi-node-connected components.
1.331 +  ///
1.332 +  /// \see biNodeConnected(), countBiNodeConnectedComponents()
1.333    template <typename Graph, typename EdgeMap>
1.334    int biNodeConnectedComponents(const Graph& graph,
1.335                                  EdgeMap& compMap) {
1.336 @@ -801,18 +846,25 @@
1.337
1.338    /// \ingroup graph_properties
1.339    ///
1.340 -  /// \brief Find the bi-node-connected cut nodes.
1.341 +  /// \brief Find the bi-node-connected cut nodes in an undirected graph.
1.342    ///
1.343 -  /// This function finds the bi-node-connected cut nodes in an undirected
1.344 -  /// graph. The bi-node-connected components are the classes of an equivalence
1.345 -  /// relation on the undirected edges. Two undirected edges are in
1.346 -  /// relationship when they are on same circle. The biconnected components
1.347 -  /// are separted by nodes which are the cut nodes of the components.
1.348 +  /// This function finds the bi-node-connected cut nodes in the given
1.349 +  /// undirected graph.
1.350    ///
1.351 -  /// \param graph The graph.
1.352 -  /// \retval cutMap A writable edge map. The values will be set true when
1.353 -  /// the node separate two or more components.
1.354 +  /// The bi-node-connected components are the classes of an equivalence
1.355 +  /// relation on the edges of a undirected graph. Two edges are in the
1.356 +  /// same class if they are on same circle.
1.357 +  /// The bi-node-connected components are separted by the cut nodes of
1.358 +  /// the components.
1.359 +  ///
1.360 +  /// \param graph The undirected graph.
1.361 +  /// \retval cutMap A writable node map. The values will be set to
1.362 +  /// \c true for the nodes that separate two or more components
1.363 +  /// (exactly once for each cut node), and will not be changed for
1.364 +  /// other nodes.
1.365    /// \return The number of the cut nodes.
1.366 +  ///
1.367 +  /// \see biNodeConnected(), biNodeConnectedComponents()
1.368    template <typename Graph, typename NodeMap>
1.369    int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
1.370      checkConcept<concepts::Graph, Graph>();
1.371 @@ -1031,14 +1083,16 @@
1.372
1.373    /// \ingroup graph_properties
1.374    ///
1.375 -  /// \brief Checks that the graph is bi-edge-connected.
1.376 +  /// \brief Check whether an undirected graph is bi-edge-connected.
1.377    ///
1.378 -  /// This function checks that the graph is bi-edge-connected. The undirected
1.379 -  /// graph is bi-edge-connected when any two nodes are connected with two
1.380 -  /// edge-disjoint paths.
1.381 +  /// This function checks whether the given undirected graph is
1.382 +  /// bi-edge-connected, i.e. any two nodes are connected with at least
1.383 +  /// two edge-disjoint paths.
1.384    ///
1.385 -  /// \param graph The undirected graph.
1.386 -  /// \return The number of components.
1.387 +  /// \return \c true if the graph is bi-edge-connected.
1.388 +  /// \note By definition, the empty graph is bi-edge-connected.
1.389 +  ///
1.390 +  /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
1.391    template <typename Graph>
1.392    bool biEdgeConnected(const Graph& graph) {
1.393      return countBiEdgeConnectedComponents(graph) <= 1;
1.394 @@ -1046,15 +1100,20 @@
1.395
1.396    /// \ingroup graph_properties
1.397    ///
1.398 -  /// \brief Count the bi-edge-connected components.
1.399 +  /// \brief Count the number of bi-edge-connected components of an
1.400 +  /// undirected graph.
1.401    ///
1.402 -  /// This function count the bi-edge-connected components in an undirected
1.403 -  /// graph. The bi-edge-connected components are the classes of an equivalence
1.404 -  /// relation on the nodes. Two nodes are in relationship when they are
1.405 -  /// connected with at least two edge-disjoint paths.
1.406 +  /// This function counts the number of bi-edge-connected components of
1.407 +  /// the given undirected graph.
1.408    ///
1.409 -  /// \param graph The undirected graph.
1.410 -  /// \return The number of components.
1.411 +  /// The bi-edge-connected components are the classes of an equivalence
1.412 +  /// relation on the nodes of an undirected graph. Two nodes are in the
1.413 +  /// same class if they are connected with at least two edge-disjoint
1.414 +  /// paths.
1.415 +  ///
1.416 +  /// \return The number of bi-edge-connected components.
1.417 +  ///
1.418 +  /// \see biEdgeConnected(), biEdgeConnectedComponents()
1.419    template <typename Graph>
1.420    int countBiEdgeConnectedComponents(const Graph& graph) {
1.421      checkConcept<concepts::Graph, Graph>();
1.422 @@ -1081,22 +1140,27 @@
1.423
1.424    /// \ingroup graph_properties
1.425    ///
1.426 -  /// \brief Find the bi-edge-connected components.
1.427 +  /// \brief Find the bi-edge-connected components of an undirected graph.
1.428    ///
1.429 -  /// This function finds the bi-edge-connected components in an undirected
1.430 -  /// graph. The bi-edge-connected components are the classes of an equivalence
1.431 -  /// relation on the nodes. Two nodes are in relationship when they are
1.432 -  /// connected at least two edge-disjoint paths.
1.433 +  /// This function finds the bi-edge-connected components of the given
1.434 +  /// undirected graph.
1.435 +  ///
1.436 +  /// The bi-edge-connected components are the classes of an equivalence
1.437 +  /// relation on the nodes of an undirected graph. Two nodes are in the
1.438 +  /// same class if they are connected with at least two edge-disjoint
1.439 +  /// paths.
1.440    ///
1.441    /// \image html edge_biconnected_components.png
1.442    /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1.443    ///
1.444 -  /// \param graph The graph.
1.445 +  /// \param graph The undirected graph.
1.446    /// \retval compMap A writable node map. The values will be set from 0 to
1.447 -  /// the number of the biconnected components minus one. Each values
1.448 -  /// of the map will be set exactly once, the values of a certain component
1.449 -  /// will be set continuously.
1.450 -  /// \return The number of components.
1.451 +  /// the number of the bi-edge-connected components minus one. Each value
1.452 +  /// of the map will be set exactly once, and the values of a certain
1.453 +  /// component will be set continuously.
1.454 +  /// \return The number of bi-edge-connected components.
1.455 +  ///
1.456 +  /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
1.457    template <typename Graph, typename NodeMap>
1.458    int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
1.459      checkConcept<concepts::Graph, Graph>();
1.460 @@ -1125,19 +1189,25 @@
1.461
1.462    /// \ingroup graph_properties
1.463    ///
1.464 -  /// \brief Find the bi-edge-connected cut edges.
1.465 +  /// \brief Find the bi-edge-connected cut edges in an undirected graph.
1.466    ///
1.467 -  /// This function finds the bi-edge-connected components in an undirected
1.468 -  /// graph. The bi-edge-connected components are the classes of an equivalence
1.469 -  /// relation on the nodes. Two nodes are in relationship when they are
1.470 -  /// connected with at least two edge-disjoint paths. The bi-edge-connected
1.471 -  /// components are separted by edges which are the cut edges of the
1.472 -  /// components.
1.473 +  /// This function finds the bi-edge-connected cut edges in the given
1.474 +  /// undirected graph.
1.475    ///
1.476 -  /// \param graph The graph.
1.477 -  /// \retval cutMap A writable node map. The values will be set true when the
1.478 -  /// edge is a cut edge.
1.479 +  /// The bi-edge-connected components are the classes of an equivalence
1.480 +  /// relation on the nodes of an undirected graph. Two nodes are in the
1.481 +  /// same class if they are connected with at least two edge-disjoint
1.482 +  /// paths.
1.483 +  /// The bi-edge-connected components are separted by the cut edges of
1.484 +  /// the components.
1.485 +  ///
1.486 +  /// \param graph The undirected graph.
1.487 +  /// \retval cutMap A writable edge map. The values will be set to \c true
1.488 +  /// for the cut edges (exactly once for each cut edge), and will not be
1.489 +  /// changed for other edges.
1.490    /// \return The number of cut edges.
1.491 +  ///
1.492 +  /// \see biEdgeConnected(), biEdgeConnectedComponents()
1.493    template <typename Graph, typename EdgeMap>
1.494    int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
1.495      checkConcept<concepts::Graph, Graph>();
1.496 @@ -1189,19 +1259,62 @@
1.497
1.498    /// \ingroup graph_properties
1.499    ///
1.500 +  /// \brief Check whether a digraph is DAG.
1.501 +  ///
1.502 +  /// This function checks whether the given digraph is DAG, i.e.
1.503 +  /// \e Directed \e Acyclic \e Graph.
1.504 +  /// \return \c true if there is no directed cycle in the digraph.
1.505 +  /// \see acyclic()
1.506 +  template <typename Digraph>
1.507 +  bool dag(const Digraph& digraph) {
1.508 +
1.509 +    checkConcept<concepts::Digraph, Digraph>();
1.510 +
1.511 +    typedef typename Digraph::Node Node;
1.512 +    typedef typename Digraph::NodeIt NodeIt;
1.513 +    typedef typename Digraph::Arc Arc;
1.514 +
1.515 +    typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.516 +
1.517 +    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
1.518 +      Create dfs(digraph);
1.519 +
1.520 +    ProcessedMap processed(digraph);
1.521 +    dfs.processedMap(processed);
1.522 +
1.523 +    dfs.init();
1.524 +    for (NodeIt it(digraph); it != INVALID; ++it) {
1.525 +      if (!dfs.reached(it)) {
1.527 +        while (!dfs.emptyQueue()) {
1.528 +          Arc arc = dfs.nextArc();
1.529 +          Node target = digraph.target(arc);
1.530 +          if (dfs.reached(target) && !processed[target]) {
1.531 +            return false;
1.532 +          }
1.533 +          dfs.processNextArc();
1.534 +        }
1.535 +      }
1.536 +    }
1.537 +    return true;
1.538 +  }
1.539 +
1.540 +  /// \ingroup graph_properties
1.541 +  ///
1.542    /// \brief Sort the nodes of a DAG into topolgical order.
1.543    ///
1.544 -  /// Sort the nodes of a DAG into topolgical order.
1.545 +  /// This function sorts the nodes of the given acyclic digraph (DAG)
1.546 +  /// into topolgical order.
1.547    ///
1.548 -  /// \param graph The graph. It must be directed and acyclic.
1.549 +  /// \param digraph The digraph, which must be DAG.
1.550    /// \retval order A writable node map. The values will be set from 0 to
1.551 -  /// the number of the nodes in the graph minus one. Each values of the map
1.552 -  /// will be set exactly once, the values  will be set descending order.
1.553 +  /// the number of the nodes in the digraph minus one. Each value of the
1.554 +  /// map will be set exactly once, and the values will be set descending
1.555 +  /// order.
1.556    ///
1.557 -  /// \see checkedTopologicalSort
1.558 -  /// \see dag
1.559 +  /// \see dag(), checkedTopologicalSort()
1.560    template <typename Digraph, typename NodeMap>
1.561 -  void topologicalSort(const Digraph& graph, NodeMap& order) {
1.562 +  void topologicalSort(const Digraph& digraph, NodeMap& order) {
1.563      using namespace _connectivity_bits;
1.564
1.565      checkConcept<concepts::Digraph, Digraph>();
1.566 @@ -1212,13 +1325,13 @@
1.567      typedef typename Digraph::Arc Arc;
1.568
1.569      TopologicalSortVisitor<Digraph, NodeMap>
1.570 -      visitor(order, countNodes(graph));
1.571 +      visitor(order, countNodes(digraph));
1.572
1.573      DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
1.574 -      dfs(graph, visitor);
1.575 +      dfs(digraph, visitor);
1.576
1.577      dfs.init();
1.578 -    for (NodeIt it(graph); it != INVALID; ++it) {
1.579 +    for (NodeIt it(digraph); it != INVALID; ++it) {
1.580        if (!dfs.reached(it)) {
1.582          dfs.start();
1.583 @@ -1230,18 +1343,18 @@
1.584    ///
1.585    /// \brief Sort the nodes of a DAG into topolgical order.
1.586    ///
1.587 -  /// Sort the nodes of a DAG into topolgical order. It also checks
1.588 -  /// that the given graph is DAG.
1.589 +  /// This function sorts the nodes of the given acyclic digraph (DAG)
1.590 +  /// into topolgical order and also checks whether the given digraph
1.591 +  /// is DAG.
1.592    ///
1.593 -  /// \param digraph The graph. It must be directed and acyclic.
1.594 -  /// \retval order A readable - writable node map. The values will be set
1.595 -  /// from 0 to the number of the nodes in the graph minus one. Each values
1.596 -  /// of the map will be set exactly once, the values will be set descending
1.597 -  /// order.
1.598 -  /// \return \c false when the graph is not DAG.
1.599 +  /// \param digraph The digraph.
1.600 +  /// \retval order A readable and writable node map. The values will be
1.601 +  /// set from 0 to the number of the nodes in the digraph minus one.
1.602 +  /// Each value of the map will be set exactly once, and the values will
1.603 +  /// be set descending order.
1.604 +  /// \return \c false if the digraph is not DAG.
1.605    ///
1.606 -  /// \see topologicalSort
1.607 -  /// \see dag
1.608 +  /// \see dag(), topologicalSort()
1.609    template <typename Digraph, typename NodeMap>
1.610    bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
1.611      using namespace _connectivity_bits;
1.612 @@ -1283,54 +1396,11 @@
1.613
1.614    /// \ingroup graph_properties
1.615    ///
1.616 -  /// \brief Check that the given directed graph is a DAG.
1.617 +  /// \brief Check whether an undirected graph is acyclic.
1.618    ///
1.619 -  /// Check that the given directed graph is a DAG. The DAG is
1.620 -  /// an Directed Acyclic Digraph.
1.621 -  /// \return \c false when the graph is not DAG.
1.622 -  /// \see acyclic
1.623 -  template <typename Digraph>
1.624 -  bool dag(const Digraph& digraph) {
1.625 -
1.626 -    checkConcept<concepts::Digraph, Digraph>();
1.627 -
1.628 -    typedef typename Digraph::Node Node;
1.629 -    typedef typename Digraph::NodeIt NodeIt;
1.630 -    typedef typename Digraph::Arc Arc;
1.631 -
1.632 -    typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.633 -
1.634 -    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
1.635 -      Create dfs(digraph);
1.636 -
1.637 -    ProcessedMap processed(digraph);
1.638 -    dfs.processedMap(processed);
1.639 -
1.640 -    dfs.init();
1.641 -    for (NodeIt it(digraph); it != INVALID; ++it) {
1.642 -      if (!dfs.reached(it)) {
1.644 -        while (!dfs.emptyQueue()) {
1.645 -          Arc edge = dfs.nextArc();
1.646 -          Node target = digraph.target(edge);
1.647 -          if (dfs.reached(target) && !processed[target]) {
1.648 -            return false;
1.649 -          }
1.650 -          dfs.processNextArc();
1.651 -        }
1.652 -      }
1.653 -    }
1.654 -    return true;
1.655 -  }
1.656 -
1.657 -  /// \ingroup graph_properties
1.658 -  ///
1.659 -  /// \brief Check that the given undirected graph is acyclic.
1.660 -  ///
1.661 -  /// Check that the given undirected graph acyclic.
1.662 -  /// \param graph The undirected graph.
1.663 -  /// \return \c true when there is no circle in the graph.
1.664 -  /// \see dag
1.665 +  /// This function checks whether the given undirected graph is acyclic.
1.666 +  /// \return \c true if there is no cycle in the graph.
1.667 +  /// \see dag()
1.668    template <typename Graph>
1.669    bool acyclic(const Graph& graph) {
1.670      checkConcept<concepts::Graph, Graph>();
1.671 @@ -1343,11 +1413,11 @@
1.672        if (!dfs.reached(it)) {
1.674          while (!dfs.emptyQueue()) {
1.675 -          Arc edge = dfs.nextArc();
1.676 -          Node source = graph.source(edge);
1.677 -          Node target = graph.target(edge);
1.678 +          Arc arc = dfs.nextArc();
1.679 +          Node source = graph.source(arc);
1.680 +          Node target = graph.target(arc);
1.681            if (dfs.reached(target) &&
1.682 -              dfs.predArc(source) != graph.oppositeArc(edge)) {
1.683 +              dfs.predArc(source) != graph.oppositeArc(arc)) {
1.684              return false;
1.685            }
1.686            dfs.processNextArc();
1.687 @@ -1359,11 +1429,11 @@
1.688
1.689    /// \ingroup graph_properties
1.690    ///
1.691 -  /// \brief Check that the given undirected graph is tree.
1.692 +  /// \brief Check whether an undirected graph is tree.
1.693    ///
1.694 -  /// Check that the given undirected graph is tree.
1.695 -  /// \param graph The undirected graph.
1.696 -  /// \return \c true when the graph is acyclic and connected.
1.697 +  /// This function checks whether the given undirected graph is tree.
1.698 +  /// \return \c true if the graph is acyclic and connected.
1.699 +  /// \see acyclic(), connected()
1.700    template <typename Graph>
1.701    bool tree(const Graph& graph) {
1.702      checkConcept<concepts::Graph, Graph>();
1.703 @@ -1375,11 +1445,11 @@
1.704      dfs.init();
1.706      while (!dfs.emptyQueue()) {
1.707 -      Arc edge = dfs.nextArc();
1.708 -      Node source = graph.source(edge);
1.709 -      Node target = graph.target(edge);
1.710 +      Arc arc = dfs.nextArc();
1.711 +      Node source = graph.source(arc);
1.712 +      Node target = graph.target(arc);
1.713        if (dfs.reached(target) &&
1.714 -          dfs.predArc(source) != graph.oppositeArc(edge)) {
1.715 +          dfs.predArc(source) != graph.oppositeArc(arc)) {
1.716          return false;
1.717        }
1.718        dfs.processNextArc();
1.719 @@ -1452,15 +1522,14 @@
1.720
1.721    /// \ingroup graph_properties
1.722    ///
1.723 -  /// \brief Check if the given undirected graph is bipartite or not
1.724 +  /// \brief Check whether an undirected graph is bipartite.
1.725    ///
1.726 -  /// The function checks if the given undirected \c graph graph is bipartite
1.727 -  /// or not. The \ref Bfs algorithm is used to calculate the result.
1.728 -  /// \param graph The undirected graph.
1.729 -  /// \return \c true if \c graph is bipartite, \c false otherwise.
1.730 -  /// \sa bipartitePartitions
1.731 +  /// The function checks whether the given undirected graph is bipartite.
1.732 +  /// \return \c true if the graph is bipartite.
1.733 +  ///
1.734 +  /// \see bipartitePartitions()
1.735    template<typename Graph>
1.736 -  inline bool bipartite(const Graph &graph){
1.737 +  bool bipartite(const Graph &graph){
1.738      using namespace _connectivity_bits;
1.739
1.740      checkConcept<concepts::Graph, Graph>();
1.741 @@ -1489,25 +1558,27 @@
1.742
1.743    /// \ingroup graph_properties
1.744    ///
1.745 -  /// \brief Check if the given undirected graph is bipartite or not
1.746 +  /// \brief Find the bipartite partitions of an undirected graph.
1.747    ///
1.748 -  /// The function checks if the given undirected graph is bipartite
1.749 -  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
1.750 -  /// During the execution, the \c partMap will be set as the two
1.751 -  /// partitions of the graph.
1.752 +  /// This function checks whether the given undirected graph is bipartite
1.753 +  /// and gives back the bipartite partitions.
1.754    ///
1.755    /// \image html bipartite_partitions.png
1.756    /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1.757    ///
1.758    /// \param graph The undirected graph.
1.759 -  /// \retval partMap A writable bool map of nodes. It will be set as the
1.760 -  /// two partitions of the graph.
1.761 -  /// \return \c true if \c graph is bipartite, \c false otherwise.
1.762 +  /// \retval partMap A writable node map of \c bool (or convertible) value
1.763 +  /// type. The values will be set to \c true for one component and
1.764 +  /// \c false for the other one.
1.765 +  /// \return \c true if the graph is bipartite, \c false otherwise.
1.766 +  ///
1.767 +  /// \see bipartite()
1.768    template<typename Graph, typename NodeMap>
1.769 -  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
1.770 +  bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
1.771      using namespace _connectivity_bits;
1.772
1.773      checkConcept<concepts::Graph, Graph>();
1.774 +    checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
1.775
1.776      typedef typename Graph::Node Node;
1.777      typedef typename Graph::NodeIt NodeIt;
1.778 @@ -1532,20 +1603,26 @@
1.779      return true;
1.780    }
1.781
1.782 -  /// \brief Returns true when there are not loop edges in the graph.
1.783 +  /// \ingroup graph_properties
1.784    ///
1.785 -  /// Returns true when there are not loop edges in the graph.
1.786 -  template <typename Digraph>
1.787 -  bool loopFree(const Digraph& digraph) {
1.788 -    for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
1.789 -      if (digraph.source(it) == digraph.target(it)) return false;
1.790 +  /// \brief Check whether the given graph contains no loop arcs/edges.
1.791 +  ///
1.792 +  /// This function returns \c true if there are no loop arcs/edges in
1.793 +  /// the given graph. It works for both directed and undirected graphs.
1.794 +  template <typename Graph>
1.795 +  bool loopFree(const Graph& graph) {
1.796 +    for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
1.797 +      if (graph.source(it) == graph.target(it)) return false;
1.798      }
1.799      return true;
1.800    }
1.801
1.802 -  /// \brief Returns true when there are not parallel edges in the graph.
1.803 +  /// \ingroup graph_properties
1.804    ///
1.805 -  /// Returns true when there are not parallel edges in the graph.
1.806 +  /// \brief Check whether the given graph contains no parallel arcs/edges.
1.807 +  ///
1.808 +  /// This function returns \c true if there are no parallel arcs/edges in
1.809 +  /// the given graph. It works for both directed and undirected graphs.
1.810    template <typename Graph>
1.811    bool parallelFree(const Graph& graph) {
1.812      typename Graph::template NodeMap<int> reached(graph, 0);
1.813 @@ -1560,11 +1637,14 @@
1.814      return true;
1.815    }
1.816
1.817 -  /// \brief Returns true when there are not loop edges and parallel
1.818 -  /// edges in the graph.
1.819 +  /// \ingroup graph_properties
1.820    ///
1.821 -  /// Returns true when there are not loop edges and parallel edges in
1.822 -  /// the graph.
1.823 +  /// \brief Check whether the given graph is simple.
1.824 +  ///
1.825 +  /// This function returns \c true if the given graph is simple, i.e.
1.826 +  /// it contains no loop arcs/edges and no parallel arcs/edges.
1.827 +  /// The function works for both directed and undirected graphs.
1.828 +  /// \see loopFree(), parallelFree()
1.829    template <typename Graph>
1.830    bool simpleGraph(const Graph& graph) {
1.831      typename Graph::template NodeMap<int> reached(graph, 0);

     2.1 --- a/lemon/euler.h	Wed May 06 14:37:44 2009 +0200
2.2 +++ b/lemon/euler.h	Wed May 06 14:44:05 2009 +0200
2.3 @@ -244,10 +244,10 @@
2.4    };
2.5
2.6
2.7 -  ///Check if the given graph is \e Eulerian
2.8 +  ///Check if the given graph is Eulerian
2.9
2.10    /// \ingroup graph_properties
2.11 -  ///This function checks if the given graph is \e Eulerian.
2.12 +  ///This function checks if the given graph is Eulerian.
2.13    ///It works for both directed and undirected graphs.
2.14    ///
2.15    ///By definition, a digraph is called \e Eulerian if