Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Thu, 07 May 2009 12:19:41 +0100
changeset 652e2f99a473998
parent 651 3adf5e2d1e62
parent 649 76cbcb3e9bbb
child 653 682941948726
Merge
     1.1 --- a/lemon/connectivity.h	Thu May 07 02:07:59 2009 +0200
     1.2 +++ b/lemon/connectivity.h	Thu May 07 12:19:41 2009 +0100
     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.229          dfs.addSource(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.526 +        dfs.addSource(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.581          dfs.addSource(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.643 -        dfs.addSource(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.673          dfs.addSource(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,26 +1429,27 @@
   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      typedef typename Graph::Node Node;
   1.704      typedef typename Graph::NodeIt NodeIt;
   1.705      typedef typename Graph::Arc Arc;
   1.706 +    if (NodeIt(graph) == INVALID) return true;
   1.707      Dfs<Graph> dfs(graph);
   1.708      dfs.init();
   1.709      dfs.addSource(NodeIt(graph));
   1.710      while (!dfs.emptyQueue()) {
   1.711 -      Arc edge = dfs.nextArc();
   1.712 -      Node source = graph.source(edge);
   1.713 -      Node target = graph.target(edge);
   1.714 +      Arc arc = dfs.nextArc();
   1.715 +      Node source = graph.source(arc);
   1.716 +      Node target = graph.target(arc);
   1.717        if (dfs.reached(target) &&
   1.718 -          dfs.predArc(source) != graph.oppositeArc(edge)) {
   1.719 +          dfs.predArc(source) != graph.oppositeArc(arc)) {
   1.720          return false;
   1.721        }
   1.722        dfs.processNextArc();
   1.723 @@ -1451,15 +1522,14 @@
   1.724  
   1.725    /// \ingroup graph_properties
   1.726    ///
   1.727 -  /// \brief Check if the given undirected graph is bipartite or not
   1.728 +  /// \brief Check whether an undirected graph is bipartite.
   1.729    ///
   1.730 -  /// The function checks if the given undirected \c graph graph is bipartite
   1.731 -  /// or not. The \ref Bfs algorithm is used to calculate the result.
   1.732 -  /// \param graph The undirected graph.
   1.733 -  /// \return \c true if \c graph is bipartite, \c false otherwise.
   1.734 -  /// \sa bipartitePartitions
   1.735 +  /// The function checks whether the given undirected graph is bipartite.
   1.736 +  /// \return \c true if the graph is bipartite.
   1.737 +  ///
   1.738 +  /// \see bipartitePartitions()
   1.739    template<typename Graph>
   1.740 -  inline bool bipartite(const Graph &graph){
   1.741 +  bool bipartite(const Graph &graph){
   1.742      using namespace _connectivity_bits;
   1.743  
   1.744      checkConcept<concepts::Graph, Graph>();
   1.745 @@ -1488,25 +1558,27 @@
   1.746  
   1.747    /// \ingroup graph_properties
   1.748    ///
   1.749 -  /// \brief Check if the given undirected graph is bipartite or not
   1.750 +  /// \brief Find the bipartite partitions of an undirected graph.
   1.751    ///
   1.752 -  /// The function checks if the given undirected graph is bipartite
   1.753 -  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
   1.754 -  /// During the execution, the \c partMap will be set as the two
   1.755 -  /// partitions of the graph.
   1.756 +  /// This function checks whether the given undirected graph is bipartite
   1.757 +  /// and gives back the bipartite partitions.
   1.758    ///
   1.759    /// \image html bipartite_partitions.png
   1.760    /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
   1.761    ///
   1.762    /// \param graph The undirected graph.
   1.763 -  /// \retval partMap A writable bool map of nodes. It will be set as the
   1.764 -  /// two partitions of the graph.
   1.765 -  /// \return \c true if \c graph is bipartite, \c false otherwise.
   1.766 +  /// \retval partMap A writable node map of \c bool (or convertible) value
   1.767 +  /// type. The values will be set to \c true for one component and
   1.768 +  /// \c false for the other one.
   1.769 +  /// \return \c true if the graph is bipartite, \c false otherwise.
   1.770 +  ///
   1.771 +  /// \see bipartite()
   1.772    template<typename Graph, typename NodeMap>
   1.773 -  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
   1.774 +  bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
   1.775      using namespace _connectivity_bits;
   1.776  
   1.777      checkConcept<concepts::Graph, Graph>();
   1.778 +    checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
   1.779  
   1.780      typedef typename Graph::Node Node;
   1.781      typedef typename Graph::NodeIt NodeIt;
   1.782 @@ -1531,53 +1603,59 @@
   1.783      return true;
   1.784    }
   1.785  
   1.786 -  /// \brief Returns true when there are not loop edges in the graph.
   1.787 +  /// \ingroup graph_properties
   1.788    ///
   1.789 -  /// Returns true when there are not loop edges in the graph.
   1.790 -  template <typename Digraph>
   1.791 -  bool loopFree(const Digraph& digraph) {
   1.792 -    for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
   1.793 -      if (digraph.source(it) == digraph.target(it)) return false;
   1.794 +  /// \brief Check whether the given graph contains no loop arcs/edges.
   1.795 +  ///
   1.796 +  /// This function returns \c true if there are no loop arcs/edges in
   1.797 +  /// the given graph. It works for both directed and undirected graphs.
   1.798 +  template <typename Graph>
   1.799 +  bool loopFree(const Graph& graph) {
   1.800 +    for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
   1.801 +      if (graph.source(it) == graph.target(it)) return false;
   1.802      }
   1.803      return true;
   1.804    }
   1.805  
   1.806 -  /// \brief Returns true when there are not parallel edges in the graph.
   1.807 +  /// \ingroup graph_properties
   1.808    ///
   1.809 -  /// Returns true when there are not parallel edges in the graph.
   1.810 -  template <typename Digraph>
   1.811 -  bool parallelFree(const Digraph& digraph) {
   1.812 -    typename Digraph::template NodeMap<bool> reached(digraph, false);
   1.813 -    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
   1.814 -      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
   1.815 -        if (reached[digraph.target(a)]) return false;
   1.816 -        reached.set(digraph.target(a), true);
   1.817 +  /// \brief Check whether the given graph contains no parallel arcs/edges.
   1.818 +  ///
   1.819 +  /// This function returns \c true if there are no parallel arcs/edges in
   1.820 +  /// the given graph. It works for both directed and undirected graphs.
   1.821 +  template <typename Graph>
   1.822 +  bool parallelFree(const Graph& graph) {
   1.823 +    typename Graph::template NodeMap<int> reached(graph, 0);
   1.824 +    int cnt = 1;
   1.825 +    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
   1.826 +      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
   1.827 +        if (reached[graph.target(a)] == cnt) return false;
   1.828 +        reached[graph.target(a)] = cnt;
   1.829        }
   1.830 -      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
   1.831 -        reached.set(digraph.target(a), false);
   1.832 -      }
   1.833 +      ++cnt;
   1.834      }
   1.835      return true;
   1.836    }
   1.837  
   1.838 -  /// \brief Returns true when there are not loop edges and parallel
   1.839 -  /// edges in the graph.
   1.840 +  /// \ingroup graph_properties
   1.841    ///
   1.842 -  /// Returns true when there are not loop edges and parallel edges in
   1.843 -  /// the graph.
   1.844 -  template <typename Digraph>
   1.845 -  bool simpleDigraph(const Digraph& digraph) {
   1.846 -    typename Digraph::template NodeMap<bool> reached(digraph, false);
   1.847 -    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
   1.848 -      reached.set(n, true);
   1.849 -      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
   1.850 -        if (reached[digraph.target(a)]) return false;
   1.851 -        reached.set(digraph.target(a), true);
   1.852 +  /// \brief Check whether the given graph is simple.
   1.853 +  ///
   1.854 +  /// This function returns \c true if the given graph is simple, i.e.
   1.855 +  /// it contains no loop arcs/edges and no parallel arcs/edges.
   1.856 +  /// The function works for both directed and undirected graphs.
   1.857 +  /// \see loopFree(), parallelFree()
   1.858 +  template <typename Graph>
   1.859 +  bool simpleGraph(const Graph& graph) {
   1.860 +    typename Graph::template NodeMap<int> reached(graph, 0);
   1.861 +    int cnt = 1;
   1.862 +    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
   1.863 +      reached[n] = cnt;
   1.864 +      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
   1.865 +        if (reached[graph.target(a)] == cnt) return false;
   1.866 +        reached[graph.target(a)] = cnt;
   1.867        }
   1.868 -      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
   1.869 -        reached.set(digraph.target(a), false);
   1.870 -      }
   1.871 -      reached.set(n, false);
   1.872 +      ++cnt;
   1.873      }
   1.874      return true;
   1.875    }
     2.1 --- a/lemon/euler.h	Thu May 07 02:07:59 2009 +0200
     2.2 +++ b/lemon/euler.h	Thu May 07 12:19:41 2009 +0100
     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
     3.1 --- a/test/CMakeLists.txt	Thu May 07 02:07:59 2009 +0200
     3.2 +++ b/test/CMakeLists.txt	Thu May 07 12:19:41 2009 +0100
     3.3 @@ -9,6 +9,7 @@
     3.4    adaptors_test
     3.5    bfs_test
     3.6    circulation_test
     3.7 +  connectivity_test
     3.8    counter_test
     3.9    dfs_test
    3.10    digraph_test
     4.1 --- a/test/Makefile.am	Thu May 07 02:07:59 2009 +0200
     4.2 +++ b/test/Makefile.am	Thu May 07 12:19:41 2009 +0100
     4.3 @@ -9,6 +9,7 @@
     4.4  	test/adaptors_test \
     4.5  	test/bfs_test \
     4.6  	test/circulation_test \
     4.7 +	test/connectivity_test \
     4.8  	test/counter_test \
     4.9  	test/dfs_test \
    4.10  	test/digraph_test \
    4.11 @@ -54,6 +55,7 @@
    4.12  test_bfs_test_SOURCES = test/bfs_test.cc
    4.13  test_circulation_test_SOURCES = test/circulation_test.cc
    4.14  test_counter_test_SOURCES = test/counter_test.cc
    4.15 +test_connectivity_test_SOURCES = test/connectivity_test.cc
    4.16  test_dfs_test_SOURCES = test/dfs_test.cc
    4.17  test_digraph_test_SOURCES = test/digraph_test.cc
    4.18  test_dijkstra_test_SOURCES = test/dijkstra_test.cc
     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/test/connectivity_test.cc	Thu May 07 12:19:41 2009 +0100
     5.3 @@ -0,0 +1,297 @@
     5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     5.5 + *
     5.6 + * This file is a part of LEMON, a generic C++ optimization library.
     5.7 + *
     5.8 + * Copyright (C) 2003-2009
     5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    5.11 + *
    5.12 + * Permission to use, modify and distribute this software is granted
    5.13 + * provided that this copyright notice appears in all copies. For
    5.14 + * precise terms see the accompanying LICENSE file.
    5.15 + *
    5.16 + * This software is provided "AS IS" with no warranty of any kind,
    5.17 + * express or implied, and with no claim as to its suitability for any
    5.18 + * purpose.
    5.19 + *
    5.20 + */
    5.21 +
    5.22 +#include <lemon/connectivity.h>
    5.23 +#include <lemon/list_graph.h>
    5.24 +#include <lemon/adaptors.h>
    5.25 +
    5.26 +#include "test_tools.h"
    5.27 +
    5.28 +using namespace lemon;
    5.29 +
    5.30 +
    5.31 +int main()
    5.32 +{
    5.33 +  typedef ListDigraph Digraph;
    5.34 +  typedef Undirector<Digraph> Graph;
    5.35 +  
    5.36 +  {
    5.37 +    Digraph d;
    5.38 +    Digraph::NodeMap<int> order(d);
    5.39 +    Graph g(d);
    5.40 +    
    5.41 +    check(stronglyConnected(d), "The empty digraph is strongly connected");
    5.42 +    check(countStronglyConnectedComponents(d) == 0,
    5.43 +          "The empty digraph has 0 strongly connected component");
    5.44 +    check(connected(g), "The empty graph is connected");
    5.45 +    check(countConnectedComponents(g) == 0,
    5.46 +          "The empty graph has 0 connected component");
    5.47 +
    5.48 +    check(biNodeConnected(g), "The empty graph is bi-node-connected");
    5.49 +    check(countBiNodeConnectedComponents(g) == 0,
    5.50 +          "The empty graph has 0 bi-node-connected component");
    5.51 +    check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
    5.52 +    check(countBiEdgeConnectedComponents(g) == 0,
    5.53 +          "The empty graph has 0 bi-edge-connected component");
    5.54 +          
    5.55 +    check(dag(d), "The empty digraph is DAG.");
    5.56 +    check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
    5.57 +    check(loopFree(d), "The empty digraph is loop-free.");
    5.58 +    check(parallelFree(d), "The empty digraph is parallel-free.");
    5.59 +    check(simpleGraph(d), "The empty digraph is simple.");
    5.60 +
    5.61 +    check(acyclic(g), "The empty graph is acyclic.");
    5.62 +    check(tree(g), "The empty graph is tree.");
    5.63 +    check(bipartite(g), "The empty graph is bipartite.");
    5.64 +    check(loopFree(g), "The empty graph is loop-free.");
    5.65 +    check(parallelFree(g), "The empty graph is parallel-free.");
    5.66 +    check(simpleGraph(g), "The empty graph is simple.");
    5.67 +  }
    5.68 +
    5.69 +  {
    5.70 +    Digraph d;
    5.71 +    Digraph::NodeMap<int> order(d);
    5.72 +    Graph g(d);
    5.73 +    Digraph::Node n = d.addNode();
    5.74 +
    5.75 +    check(stronglyConnected(d), "This digraph is strongly connected");
    5.76 +    check(countStronglyConnectedComponents(d) == 1,
    5.77 +          "This digraph has 1 strongly connected component");
    5.78 +    check(connected(g), "This graph is connected");
    5.79 +    check(countConnectedComponents(g) == 1,
    5.80 +          "This graph has 1 connected component");
    5.81 +
    5.82 +    check(biNodeConnected(g), "This graph is bi-node-connected");
    5.83 +    check(countBiNodeConnectedComponents(g) == 0,
    5.84 +          "This graph has 0 bi-node-connected component");
    5.85 +    check(biEdgeConnected(g), "This graph is bi-edge-connected");
    5.86 +    check(countBiEdgeConnectedComponents(g) == 1,
    5.87 +          "This graph has 1 bi-edge-connected component");
    5.88 +          
    5.89 +    check(dag(d), "This digraph is DAG.");
    5.90 +    check(checkedTopologicalSort(d, order), "This digraph is DAG.");
    5.91 +    check(loopFree(d), "This digraph is loop-free.");
    5.92 +    check(parallelFree(d), "This digraph is parallel-free.");
    5.93 +    check(simpleGraph(d), "This digraph is simple.");
    5.94 +
    5.95 +    check(acyclic(g), "This graph is acyclic.");
    5.96 +    check(tree(g), "This graph is tree.");
    5.97 +    check(bipartite(g), "This graph is bipartite.");
    5.98 +    check(loopFree(g), "This graph is loop-free.");
    5.99 +    check(parallelFree(g), "This graph is parallel-free.");
   5.100 +    check(simpleGraph(g), "This graph is simple.");
   5.101 +  }
   5.102 +
   5.103 +  {
   5.104 +    Digraph d;
   5.105 +    Digraph::NodeMap<int> order(d);
   5.106 +    Graph g(d);
   5.107 +    
   5.108 +    Digraph::Node n1 = d.addNode();
   5.109 +    Digraph::Node n2 = d.addNode();
   5.110 +    Digraph::Node n3 = d.addNode();
   5.111 +    Digraph::Node n4 = d.addNode();
   5.112 +    Digraph::Node n5 = d.addNode();
   5.113 +    Digraph::Node n6 = d.addNode();
   5.114 +    
   5.115 +    d.addArc(n1, n3);
   5.116 +    d.addArc(n3, n2);
   5.117 +    d.addArc(n2, n1);
   5.118 +    d.addArc(n4, n2);
   5.119 +    d.addArc(n4, n3);
   5.120 +    d.addArc(n5, n6);
   5.121 +    d.addArc(n6, n5);
   5.122 +
   5.123 +    check(!stronglyConnected(d), "This digraph is not strongly connected");
   5.124 +    check(countStronglyConnectedComponents(d) == 3,
   5.125 +          "This digraph has 3 strongly connected components");
   5.126 +    check(!connected(g), "This graph is not connected");
   5.127 +    check(countConnectedComponents(g) == 2,
   5.128 +          "This graph has 2 connected components");
   5.129 +
   5.130 +    check(!dag(d), "This digraph is not DAG.");
   5.131 +    check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");
   5.132 +    check(loopFree(d), "This digraph is loop-free.");
   5.133 +    check(parallelFree(d), "This digraph is parallel-free.");
   5.134 +    check(simpleGraph(d), "This digraph is simple.");
   5.135 +
   5.136 +    check(!acyclic(g), "This graph is not acyclic.");
   5.137 +    check(!tree(g), "This graph is not tree.");
   5.138 +    check(!bipartite(g), "This graph is not bipartite.");
   5.139 +    check(loopFree(g), "This graph is loop-free.");
   5.140 +    check(!parallelFree(g), "This graph is not parallel-free.");
   5.141 +    check(!simpleGraph(g), "This graph is not simple.");
   5.142 +    
   5.143 +    d.addArc(n3, n3);
   5.144 +    
   5.145 +    check(!loopFree(d), "This digraph is not loop-free.");
   5.146 +    check(!loopFree(g), "This graph is not loop-free.");
   5.147 +    check(!simpleGraph(d), "This digraph is not simple.");
   5.148 +    
   5.149 +    d.addArc(n3, n2);
   5.150 +    
   5.151 +    check(!parallelFree(d), "This digraph is not parallel-free.");
   5.152 +  }
   5.153 +  
   5.154 +  {
   5.155 +    Digraph d;
   5.156 +    Digraph::ArcMap<bool> cutarcs(d, false);
   5.157 +    Graph g(d);
   5.158 +    
   5.159 +    Digraph::Node n1 = d.addNode();
   5.160 +    Digraph::Node n2 = d.addNode();
   5.161 +    Digraph::Node n3 = d.addNode();
   5.162 +    Digraph::Node n4 = d.addNode();
   5.163 +    Digraph::Node n5 = d.addNode();
   5.164 +    Digraph::Node n6 = d.addNode();
   5.165 +    Digraph::Node n7 = d.addNode();
   5.166 +    Digraph::Node n8 = d.addNode();
   5.167 +
   5.168 +    d.addArc(n1, n2);
   5.169 +    d.addArc(n5, n1);
   5.170 +    d.addArc(n2, n8);
   5.171 +    d.addArc(n8, n5);
   5.172 +    d.addArc(n6, n4);
   5.173 +    d.addArc(n4, n6);
   5.174 +    d.addArc(n2, n5);
   5.175 +    d.addArc(n1, n8);
   5.176 +    d.addArc(n6, n7);
   5.177 +    d.addArc(n7, n6);
   5.178 +   
   5.179 +    check(!stronglyConnected(d), "This digraph is not strongly connected");
   5.180 +    check(countStronglyConnectedComponents(d) == 3,
   5.181 +          "This digraph has 3 strongly connected components");
   5.182 +    Digraph::NodeMap<int> scomp1(d);
   5.183 +    check(stronglyConnectedComponents(d, scomp1) == 3,
   5.184 +          "This digraph has 3 strongly connected components");
   5.185 +    check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&
   5.186 +          scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");
   5.187 +    check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&
   5.188 +          scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");
   5.189 +    check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],
   5.190 +          "Wrong stronglyConnectedComponents()");
   5.191 +    Digraph::ArcMap<bool> scut1(d, false);
   5.192 +    check(stronglyConnectedCutArcs(d, scut1) == 0,
   5.193 +          "This digraph has 0 strongly connected cut arc.");
   5.194 +    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
   5.195 +      check(!scut1[a], "Wrong stronglyConnectedCutArcs()");
   5.196 +    }
   5.197 +
   5.198 +    check(!connected(g), "This graph is not connected");
   5.199 +    check(countConnectedComponents(g) == 3,
   5.200 +          "This graph has 3 connected components");
   5.201 +    Graph::NodeMap<int> comp(g);
   5.202 +    check(connectedComponents(g, comp) == 3,
   5.203 +          "This graph has 3 connected components");
   5.204 +    check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&
   5.205 +          comp[n3] != comp[n4], "Wrong connectedComponents()");
   5.206 +    check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&
   5.207 +          comp[n1] == comp[n8], "Wrong connectedComponents()");
   5.208 +    check(comp[n4] == comp[n6] && comp[n4] == comp[n7],
   5.209 +          "Wrong connectedComponents()");
   5.210 +
   5.211 +    cutarcs[d.addArc(n3, n1)] = true;
   5.212 +    cutarcs[d.addArc(n3, n5)] = true;
   5.213 +    cutarcs[d.addArc(n3, n8)] = true;
   5.214 +    cutarcs[d.addArc(n8, n6)] = true;
   5.215 +    cutarcs[d.addArc(n8, n7)] = true;
   5.216 +
   5.217 +    check(!stronglyConnected(d), "This digraph is not strongly connected");
   5.218 +    check(countStronglyConnectedComponents(d) == 3,
   5.219 +          "This digraph has 3 strongly connected components");
   5.220 +    Digraph::NodeMap<int> scomp2(d);
   5.221 +    check(stronglyConnectedComponents(d, scomp2) == 3,
   5.222 +          "This digraph has 3 strongly connected components");
   5.223 +    check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");
   5.224 +    check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&
   5.225 +          scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");
   5.226 +    check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,
   5.227 +          "Wrong stronglyConnectedComponents()");
   5.228 +    Digraph::ArcMap<bool> scut2(d, false);
   5.229 +    check(stronglyConnectedCutArcs(d, scut2) == 5,
   5.230 +          "This digraph has 5 strongly connected cut arcs.");
   5.231 +    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
   5.232 +      check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");
   5.233 +    }
   5.234 +  }
   5.235 +
   5.236 +  {
   5.237 +    // DAG example for topological sort from the book New Algorithms
   5.238 +    // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
   5.239 +    Digraph d;
   5.240 +    Digraph::NodeMap<int> order(d);
   5.241 +    
   5.242 +    Digraph::Node belt = d.addNode();
   5.243 +    Digraph::Node trousers = d.addNode();
   5.244 +    Digraph::Node necktie = d.addNode();
   5.245 +    Digraph::Node coat = d.addNode();
   5.246 +    Digraph::Node socks = d.addNode();
   5.247 +    Digraph::Node shirt = d.addNode();
   5.248 +    Digraph::Node shoe = d.addNode();
   5.249 +    Digraph::Node watch = d.addNode();
   5.250 +    Digraph::Node pants = d.addNode();
   5.251 +
   5.252 +    d.addArc(socks, shoe);
   5.253 +    d.addArc(pants, shoe);
   5.254 +    d.addArc(pants, trousers);
   5.255 +    d.addArc(trousers, shoe);
   5.256 +    d.addArc(trousers, belt);
   5.257 +    d.addArc(belt, coat);
   5.258 +    d.addArc(shirt, belt);
   5.259 +    d.addArc(shirt, necktie);
   5.260 +    d.addArc(necktie, coat);
   5.261 +    
   5.262 +    check(dag(d), "This digraph is DAG.");
   5.263 +    topologicalSort(d, order);
   5.264 +    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
   5.265 +      check(order[d.source(a)] < order[d.target(a)],
   5.266 +            "Wrong topologicalSort()");
   5.267 +    }
   5.268 +  }
   5.269 +
   5.270 +  {
   5.271 +    ListGraph g;
   5.272 +    ListGraph::NodeMap<bool> map(g);
   5.273 +    
   5.274 +    ListGraph::Node n1 = g.addNode();
   5.275 +    ListGraph::Node n2 = g.addNode();
   5.276 +    ListGraph::Node n3 = g.addNode();
   5.277 +    ListGraph::Node n4 = g.addNode();
   5.278 +    ListGraph::Node n5 = g.addNode();
   5.279 +    ListGraph::Node n6 = g.addNode();
   5.280 +    ListGraph::Node n7 = g.addNode();
   5.281 +
   5.282 +    g.addEdge(n1, n3);
   5.283 +    g.addEdge(n1, n4);
   5.284 +    g.addEdge(n2, n5);
   5.285 +    g.addEdge(n3, n6);
   5.286 +    g.addEdge(n4, n6);
   5.287 +    g.addEdge(n4, n7);
   5.288 +    g.addEdge(n5, n7);
   5.289 +   
   5.290 +    check(bipartite(g), "This graph is bipartite");
   5.291 +    check(bipartitePartitions(g, map), "This graph is bipartite");
   5.292 +    
   5.293 +    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
   5.294 +          "Wrong bipartitePartitions()");
   5.295 +    check(map[n3] == map[n4] && map[n3] == map[n5],
   5.296 +          "Wrong bipartitePartitions()");
   5.297 +  }
   5.298 +
   5.299 +  return 0;
   5.300 +}