lemon/connectivity.h
changeset 417 6ff53afe98b5
child 419 9afe81e4c543
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/connectivity.h	Sun Nov 30 22:06:52 2008 +0100
     1.3 @@ -0,0 +1,1572 @@
     1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library.
     1.7 + *
     1.8 + * Copyright (C) 2003-2008
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#ifndef LEMON_TOPOLOGY_H
    1.23 +#define LEMON_TOPOLOGY_H
    1.24 +
    1.25 +#include <lemon/dfs.h>
    1.26 +#include <lemon/bfs.h>
    1.27 +#include <lemon/core.h>
    1.28 +#include <lemon/maps.h>
    1.29 +#include <lemon/adaptors.h>
    1.30 +
    1.31 +#include <lemon/concepts/digraph.h>
    1.32 +#include <lemon/concepts/graph.h>
    1.33 +#include <lemon/concept_check.h>
    1.34 +
    1.35 +#include <stack>
    1.36 +#include <functional>
    1.37 +
    1.38 +/// \ingroup connectivity
    1.39 +/// \file
    1.40 +/// \brief Connectivity algorithms
    1.41 +///
    1.42 +/// Connectivity algorithms
    1.43 +
    1.44 +namespace lemon {
    1.45 +
    1.46 +  /// \ingroup connectivity
    1.47 +  ///
    1.48 +  /// \brief Check whether the given undirected graph is connected.
    1.49 +  ///
    1.50 +  /// Check whether the given undirected graph is connected.
    1.51 +  /// \param graph The undirected graph.
    1.52 +  /// \return %True when there is path between any two nodes in the graph.
    1.53 +  /// \note By definition, the empty graph is connected.
    1.54 +  template <typename Graph>
    1.55 +  bool connected(const Graph& graph) {
    1.56 +    checkConcept<concepts::Graph, Graph>();
    1.57 +    typedef typename Graph::NodeIt NodeIt;
    1.58 +    if (NodeIt(graph) == INVALID) return true;
    1.59 +    Dfs<Graph> dfs(graph);
    1.60 +    dfs.run(NodeIt(graph));
    1.61 +    for (NodeIt it(graph); it != INVALID; ++it) {
    1.62 +      if (!dfs.reached(it)) {
    1.63 +        return false;
    1.64 +      }
    1.65 +    }
    1.66 +    return true;
    1.67 +  }
    1.68 +
    1.69 +  /// \ingroup connectivity
    1.70 +  ///
    1.71 +  /// \brief Count the number of connected components of an undirected graph
    1.72 +  ///
    1.73 +  /// Count the number of connected components of an undirected graph
    1.74 +  ///
    1.75 +  /// \param graph The graph. It must be undirected.
    1.76 +  /// \return The number of components
    1.77 +  /// \note By definition, the empty graph consists
    1.78 +  /// of zero connected components.
    1.79 +  template <typename Graph>
    1.80 +  int countConnectedComponents(const Graph &graph) {
    1.81 +    checkConcept<concepts::Graph, Graph>();
    1.82 +    typedef typename Graph::Node Node;
    1.83 +    typedef typename Graph::Arc Arc;
    1.84 +
    1.85 +    typedef NullMap<Node, Arc> PredMap;
    1.86 +    typedef NullMap<Node, int> DistMap;
    1.87 +
    1.88 +    int compNum = 0;
    1.89 +    typename Bfs<Graph>::
    1.90 +      template SetPredMap<PredMap>::
    1.91 +      template SetDistMap<DistMap>::
    1.92 +      Create bfs(graph);
    1.93 +
    1.94 +    PredMap predMap;
    1.95 +    bfs.predMap(predMap);
    1.96 +
    1.97 +    DistMap distMap;
    1.98 +    bfs.distMap(distMap);
    1.99 +
   1.100 +    bfs.init();
   1.101 +    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
   1.102 +      if (!bfs.reached(n)) {
   1.103 +        bfs.addSource(n);
   1.104 +        bfs.start();
   1.105 +        ++compNum;
   1.106 +      }
   1.107 +    }
   1.108 +    return compNum;
   1.109 +  }
   1.110 +
   1.111 +  /// \ingroup connectivity
   1.112 +  ///
   1.113 +  /// \brief Find the connected components of an undirected graph
   1.114 +  ///
   1.115 +  /// Find the connected components of an undirected graph.
   1.116 +  ///
   1.117 +  /// \param graph The graph. It must be undirected.
   1.118 +  /// \retval compMap A writable node map. The values will be set from 0 to
   1.119 +  /// the number of the connected components minus one. Each values of the map
   1.120 +  /// will be set exactly once, the values of a certain component will be
   1.121 +  /// set continuously.
   1.122 +  /// \return The number of components
   1.123 +  ///
   1.124 +  template <class Graph, class NodeMap>
   1.125 +  int connectedComponents(const Graph &graph, NodeMap &compMap) {
   1.126 +    checkConcept<concepts::Graph, Graph>();
   1.127 +    typedef typename Graph::Node Node;
   1.128 +    typedef typename Graph::Arc Arc;
   1.129 +    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
   1.130 +
   1.131 +    typedef NullMap<Node, Arc> PredMap;
   1.132 +    typedef NullMap<Node, int> DistMap;
   1.133 +
   1.134 +    int compNum = 0;
   1.135 +    typename Bfs<Graph>::
   1.136 +      template SetPredMap<PredMap>::
   1.137 +      template SetDistMap<DistMap>::
   1.138 +      Create bfs(graph);
   1.139 +
   1.140 +    PredMap predMap;
   1.141 +    bfs.predMap(predMap);
   1.142 +
   1.143 +    DistMap distMap;
   1.144 +    bfs.distMap(distMap);
   1.145 +
   1.146 +    bfs.init();
   1.147 +    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
   1.148 +      if(!bfs.reached(n)) {
   1.149 +        bfs.addSource(n);
   1.150 +        while (!bfs.emptyQueue()) {
   1.151 +          compMap.set(bfs.nextNode(), compNum);
   1.152 +          bfs.processNextNode();
   1.153 +        }
   1.154 +        ++compNum;
   1.155 +      }
   1.156 +    }
   1.157 +    return compNum;
   1.158 +  }
   1.159 +
   1.160 +  namespace _topology_bits {
   1.161 +
   1.162 +    template <typename Digraph, typename Iterator >
   1.163 +    struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
   1.164 +    public:
   1.165 +      typedef typename Digraph::Node Node;
   1.166 +      LeaveOrderVisitor(Iterator it) : _it(it) {}
   1.167 +
   1.168 +      void leave(const Node& node) {
   1.169 +        *(_it++) = node;
   1.170 +      }
   1.171 +
   1.172 +    private:
   1.173 +      Iterator _it;
   1.174 +    };
   1.175 +
   1.176 +    template <typename Digraph, typename Map>
   1.177 +    struct FillMapVisitor : public DfsVisitor<Digraph> {
   1.178 +    public:
   1.179 +      typedef typename Digraph::Node Node;
   1.180 +      typedef typename Map::Value Value;
   1.181 +
   1.182 +      FillMapVisitor(Map& map, Value& value)
   1.183 +        : _map(map), _value(value) {}
   1.184 +
   1.185 +      void reach(const Node& node) {
   1.186 +        _map.set(node, _value);
   1.187 +      }
   1.188 +    private:
   1.189 +      Map& _map;
   1.190 +      Value& _value;
   1.191 +    };
   1.192 +
   1.193 +    template <typename Digraph, typename ArcMap>
   1.194 +    struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
   1.195 +    public:
   1.196 +      typedef typename Digraph::Node Node;
   1.197 +      typedef typename Digraph::Arc Arc;
   1.198 +
   1.199 +      StronglyConnectedCutEdgesVisitor(const Digraph& digraph,
   1.200 +                                       ArcMap& cutMap,
   1.201 +                                       int& cutNum)
   1.202 +        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
   1.203 +          _compMap(digraph), _num(0) {
   1.204 +      }
   1.205 +
   1.206 +      void stop(const Node&) {
   1.207 +        ++_num;
   1.208 +      }
   1.209 +
   1.210 +      void reach(const Node& node) {
   1.211 +        _compMap.set(node, _num);
   1.212 +      }
   1.213 +
   1.214 +      void examine(const Arc& arc) {
   1.215 +         if (_compMap[_digraph.source(arc)] !=
   1.216 +             _compMap[_digraph.target(arc)]) {
   1.217 +           _cutMap.set(arc, true);
   1.218 +           ++_cutNum;
   1.219 +         }
   1.220 +      }
   1.221 +    private:
   1.222 +      const Digraph& _digraph;
   1.223 +      ArcMap& _cutMap;
   1.224 +      int& _cutNum;
   1.225 +
   1.226 +      typename Digraph::template NodeMap<int> _compMap;
   1.227 +      int _num;
   1.228 +    };
   1.229 +
   1.230 +  }
   1.231 +
   1.232 +
   1.233 +  /// \ingroup connectivity
   1.234 +  ///
   1.235 +  /// \brief Check whether the given directed graph is strongly connected.
   1.236 +  ///
   1.237 +  /// Check whether the given directed graph is strongly connected. The
   1.238 +  /// graph is strongly connected when any two nodes of the graph are
   1.239 +  /// connected with directed paths in both direction.
   1.240 +  /// \return %False when the graph is not strongly connected.
   1.241 +  /// \see connected
   1.242 +  ///
   1.243 +  /// \note By definition, the empty graph is strongly connected.
   1.244 +  template <typename Digraph>
   1.245 +  bool stronglyConnected(const Digraph& digraph) {
   1.246 +    checkConcept<concepts::Digraph, Digraph>();
   1.247 +
   1.248 +    typedef typename Digraph::Node Node;
   1.249 +    typedef typename Digraph::NodeIt NodeIt;
   1.250 +
   1.251 +    typename Digraph::Node source = NodeIt(digraph);
   1.252 +    if (source == INVALID) return true;
   1.253 +
   1.254 +    using namespace _topology_bits;
   1.255 +
   1.256 +    typedef DfsVisitor<Digraph> Visitor;
   1.257 +    Visitor visitor;
   1.258 +
   1.259 +    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
   1.260 +    dfs.init();
   1.261 +    dfs.addSource(source);
   1.262 +    dfs.start();
   1.263 +
   1.264 +    for (NodeIt it(digraph); it != INVALID; ++it) {
   1.265 +      if (!dfs.reached(it)) {
   1.266 +        return false;
   1.267 +      }
   1.268 +    }
   1.269 +
   1.270 +    typedef ReverseDigraph<const Digraph> RDigraph;
   1.271 +    RDigraph rdigraph(digraph);
   1.272 +
   1.273 +    typedef DfsVisitor<Digraph> RVisitor;
   1.274 +    RVisitor rvisitor;
   1.275 +
   1.276 +    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
   1.277 +    rdfs.init();
   1.278 +    rdfs.addSource(source);
   1.279 +    rdfs.start();
   1.280 +
   1.281 +    for (NodeIt it(rdigraph); it != INVALID; ++it) {
   1.282 +      if (!rdfs.reached(it)) {
   1.283 +        return false;
   1.284 +      }
   1.285 +    }
   1.286 +
   1.287 +    return true;
   1.288 +  }
   1.289 +
   1.290 +  /// \ingroup connectivity
   1.291 +  ///
   1.292 +  /// \brief Count the strongly connected components of a directed graph
   1.293 +  ///
   1.294 +  /// Count the strongly connected components of a directed graph.
   1.295 +  /// The strongly connected components are the classes of an
   1.296 +  /// equivalence relation on the nodes of the graph. Two nodes are in
   1.297 +  /// the same class if they are connected with directed paths in both
   1.298 +  /// direction.
   1.299 +  ///
   1.300 +  /// \param graph The graph.
   1.301 +  /// \return The number of components
   1.302 +  /// \note By definition, the empty graph has zero
   1.303 +  /// strongly connected components.
   1.304 +  template <typename Digraph>
   1.305 +  int countStronglyConnectedComponents(const Digraph& digraph) {
   1.306 +    checkConcept<concepts::Digraph, Digraph>();
   1.307 +
   1.308 +    using namespace _topology_bits;
   1.309 +
   1.310 +    typedef typename Digraph::Node Node;
   1.311 +    typedef typename Digraph::Arc Arc;
   1.312 +    typedef typename Digraph::NodeIt NodeIt;
   1.313 +    typedef typename Digraph::ArcIt ArcIt;
   1.314 +
   1.315 +    typedef std::vector<Node> Container;
   1.316 +    typedef typename Container::iterator Iterator;
   1.317 +
   1.318 +    Container nodes(countNodes(digraph));
   1.319 +    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
   1.320 +    Visitor visitor(nodes.begin());
   1.321 +
   1.322 +    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
   1.323 +    dfs.init();
   1.324 +    for (NodeIt it(digraph); it != INVALID; ++it) {
   1.325 +      if (!dfs.reached(it)) {
   1.326 +        dfs.addSource(it);
   1.327 +        dfs.start();
   1.328 +      }
   1.329 +    }
   1.330 +
   1.331 +    typedef typename Container::reverse_iterator RIterator;
   1.332 +    typedef ReverseDigraph<const Digraph> RDigraph;
   1.333 +
   1.334 +    RDigraph rdigraph(digraph);
   1.335 +
   1.336 +    typedef DfsVisitor<Digraph> RVisitor;
   1.337 +    RVisitor rvisitor;
   1.338 +
   1.339 +    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
   1.340 +
   1.341 +    int compNum = 0;
   1.342 +
   1.343 +    rdfs.init();
   1.344 +    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
   1.345 +      if (!rdfs.reached(*it)) {
   1.346 +        rdfs.addSource(*it);
   1.347 +        rdfs.start();
   1.348 +        ++compNum;
   1.349 +      }
   1.350 +    }
   1.351 +    return compNum;
   1.352 +  }
   1.353 +
   1.354 +  /// \ingroup connectivity
   1.355 +  ///
   1.356 +  /// \brief Find the strongly connected components of a directed graph
   1.357 +  ///
   1.358 +  /// Find the strongly connected components of a directed graph.  The
   1.359 +  /// strongly connected components are the classes of an equivalence
   1.360 +  /// relation on the nodes of the graph. Two nodes are in
   1.361 +  /// relationship when there are directed paths between them in both
   1.362 +  /// direction. In addition, the numbering of components will satisfy
   1.363 +  /// that there is no arc going from a higher numbered component to
   1.364 +  /// a lower.
   1.365 +  ///
   1.366 +  /// \param digraph The digraph.
   1.367 +  /// \retval compMap A writable node map. The values will be set from 0 to
   1.368 +  /// the number of the strongly connected components minus one. Each value
   1.369 +  /// of the map will be set exactly once, the values of a certain component
   1.370 +  /// will be set continuously.
   1.371 +  /// \return The number of components
   1.372 +  ///
   1.373 +  template <typename Digraph, typename NodeMap>
   1.374 +  int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
   1.375 +    checkConcept<concepts::Digraph, Digraph>();
   1.376 +    typedef typename Digraph::Node Node;
   1.377 +    typedef typename Digraph::NodeIt NodeIt;
   1.378 +    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
   1.379 +
   1.380 +    using namespace _topology_bits;
   1.381 +
   1.382 +    typedef std::vector<Node> Container;
   1.383 +    typedef typename Container::iterator Iterator;
   1.384 +
   1.385 +    Container nodes(countNodes(digraph));
   1.386 +    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
   1.387 +    Visitor visitor(nodes.begin());
   1.388 +
   1.389 +    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
   1.390 +    dfs.init();
   1.391 +    for (NodeIt it(digraph); it != INVALID; ++it) {
   1.392 +      if (!dfs.reached(it)) {
   1.393 +        dfs.addSource(it);
   1.394 +        dfs.start();
   1.395 +      }
   1.396 +    }
   1.397 +
   1.398 +    typedef typename Container::reverse_iterator RIterator;
   1.399 +    typedef ReverseDigraph<const Digraph> RDigraph;
   1.400 +
   1.401 +    RDigraph rdigraph(digraph);
   1.402 +
   1.403 +    int compNum = 0;
   1.404 +
   1.405 +    typedef FillMapVisitor<RDigraph, NodeMap> RVisitor;
   1.406 +    RVisitor rvisitor(compMap, compNum);
   1.407 +
   1.408 +    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
   1.409 +
   1.410 +    rdfs.init();
   1.411 +    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
   1.412 +      if (!rdfs.reached(*it)) {
   1.413 +        rdfs.addSource(*it);
   1.414 +        rdfs.start();
   1.415 +        ++compNum;
   1.416 +      }
   1.417 +    }
   1.418 +    return compNum;
   1.419 +  }
   1.420 +
   1.421 +  /// \ingroup connectivity
   1.422 +  ///
   1.423 +  /// \brief Find the cut arcs of the strongly connected components.
   1.424 +  ///
   1.425 +  /// Find the cut arcs of the strongly connected components.
   1.426 +  /// The strongly connected components are the classes of an equivalence
   1.427 +  /// relation on the nodes of the graph. Two nodes are in relationship
   1.428 +  /// when there are directed paths between them in both direction.
   1.429 +  /// The strongly connected components are separated by the cut arcs.
   1.430 +  ///
   1.431 +  /// \param graph The graph.
   1.432 +  /// \retval cutMap A writable node map. The values will be set true when the
   1.433 +  /// arc is a cut arc.
   1.434 +  ///
   1.435 +  /// \return The number of cut arcs
   1.436 +  template <typename Digraph, typename ArcMap>
   1.437 +  int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
   1.438 +    checkConcept<concepts::Digraph, Digraph>();
   1.439 +    typedef typename Digraph::Node Node;
   1.440 +    typedef typename Digraph::Arc Arc;
   1.441 +    typedef typename Digraph::NodeIt NodeIt;
   1.442 +    checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
   1.443 +
   1.444 +    using namespace _topology_bits;
   1.445 +
   1.446 +    typedef std::vector<Node> Container;
   1.447 +    typedef typename Container::iterator Iterator;
   1.448 +
   1.449 +    Container nodes(countNodes(graph));
   1.450 +    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
   1.451 +    Visitor visitor(nodes.begin());
   1.452 +
   1.453 +    DfsVisit<Digraph, Visitor> dfs(graph, visitor);
   1.454 +    dfs.init();
   1.455 +    for (NodeIt it(graph); it != INVALID; ++it) {
   1.456 +      if (!dfs.reached(it)) {
   1.457 +        dfs.addSource(it);
   1.458 +        dfs.start();
   1.459 +      }
   1.460 +    }
   1.461 +
   1.462 +    typedef typename Container::reverse_iterator RIterator;
   1.463 +    typedef ReverseDigraph<const Digraph> RDigraph;
   1.464 +
   1.465 +    RDigraph rgraph(graph);
   1.466 +
   1.467 +    int cutNum = 0;
   1.468 +
   1.469 +    typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor;
   1.470 +    RVisitor rvisitor(rgraph, cutMap, cutNum);
   1.471 +
   1.472 +    DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
   1.473 +
   1.474 +    rdfs.init();
   1.475 +    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
   1.476 +      if (!rdfs.reached(*it)) {
   1.477 +        rdfs.addSource(*it);
   1.478 +        rdfs.start();
   1.479 +      }
   1.480 +    }
   1.481 +    return cutNum;
   1.482 +  }
   1.483 +
   1.484 +  namespace _topology_bits {
   1.485 +
   1.486 +    template <typename Digraph>
   1.487 +    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
   1.488 +    public:
   1.489 +      typedef typename Digraph::Node Node;
   1.490 +      typedef typename Digraph::Arc Arc;
   1.491 +      typedef typename Digraph::Edge Edge;
   1.492 +
   1.493 +      CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
   1.494 +        : _graph(graph), _compNum(compNum),
   1.495 +          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   1.496 +
   1.497 +      void start(const Node& node) {
   1.498 +        _predMap.set(node, INVALID);
   1.499 +      }
   1.500 +
   1.501 +      void reach(const Node& node) {
   1.502 +        _numMap.set(node, _num);
   1.503 +        _retMap.set(node, _num);
   1.504 +        ++_num;
   1.505 +      }
   1.506 +
   1.507 +      void discover(const Arc& edge) {
   1.508 +        _predMap.set(_graph.target(edge), _graph.source(edge));
   1.509 +      }
   1.510 +
   1.511 +      void examine(const Arc& edge) {
   1.512 +        if (_graph.source(edge) == _graph.target(edge) &&
   1.513 +            _graph.direction(edge)) {
   1.514 +          ++_compNum;
   1.515 +          return;
   1.516 +        }
   1.517 +        if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
   1.518 +          return;
   1.519 +        }
   1.520 +        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
   1.521 +          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
   1.522 +        }
   1.523 +      }
   1.524 +
   1.525 +      void backtrack(const Arc& edge) {
   1.526 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   1.527 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   1.528 +        }
   1.529 +        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
   1.530 +          ++_compNum;
   1.531 +        }
   1.532 +      }
   1.533 +
   1.534 +    private:
   1.535 +      const Digraph& _graph;
   1.536 +      int& _compNum;
   1.537 +
   1.538 +      typename Digraph::template NodeMap<int> _numMap;
   1.539 +      typename Digraph::template NodeMap<int> _retMap;
   1.540 +      typename Digraph::template NodeMap<Node> _predMap;
   1.541 +      int _num;
   1.542 +    };
   1.543 +
   1.544 +    template <typename Digraph, typename ArcMap>
   1.545 +    class BiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
   1.546 +    public:
   1.547 +      typedef typename Digraph::Node Node;
   1.548 +      typedef typename Digraph::Arc Arc;
   1.549 +      typedef typename Digraph::Edge Edge;
   1.550 +
   1.551 +      BiNodeConnectedComponentsVisitor(const Digraph& graph,
   1.552 +                                       ArcMap& compMap, int &compNum)
   1.553 +        : _graph(graph), _compMap(compMap), _compNum(compNum),
   1.554 +          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   1.555 +
   1.556 +      void start(const Node& node) {
   1.557 +        _predMap.set(node, INVALID);
   1.558 +      }
   1.559 +
   1.560 +      void reach(const Node& node) {
   1.561 +        _numMap.set(node, _num);
   1.562 +        _retMap.set(node, _num);
   1.563 +        ++_num;
   1.564 +      }
   1.565 +
   1.566 +      void discover(const Arc& edge) {
   1.567 +        Node target = _graph.target(edge);
   1.568 +        _predMap.set(target, edge);
   1.569 +        _edgeStack.push(edge);
   1.570 +      }
   1.571 +
   1.572 +      void examine(const Arc& edge) {
   1.573 +        Node source = _graph.source(edge);
   1.574 +        Node target = _graph.target(edge);
   1.575 +        if (source == target && _graph.direction(edge)) {
   1.576 +          _compMap.set(edge, _compNum);
   1.577 +          ++_compNum;
   1.578 +          return;
   1.579 +        }
   1.580 +        if (_numMap[target] < _numMap[source]) {
   1.581 +          if (_predMap[source] != _graph.oppositeArc(edge)) {
   1.582 +            _edgeStack.push(edge);
   1.583 +          }
   1.584 +        }
   1.585 +        if (_predMap[source] != INVALID &&
   1.586 +            target == _graph.source(_predMap[source])) {
   1.587 +          return;
   1.588 +        }
   1.589 +        if (_retMap[source] > _numMap[target]) {
   1.590 +          _retMap.set(source, _numMap[target]);
   1.591 +        }
   1.592 +      }
   1.593 +
   1.594 +      void backtrack(const Arc& edge) {
   1.595 +        Node source = _graph.source(edge);
   1.596 +        Node target = _graph.target(edge);
   1.597 +        if (_retMap[source] > _retMap[target]) {
   1.598 +          _retMap.set(source, _retMap[target]);
   1.599 +        }
   1.600 +        if (_numMap[source] <= _retMap[target]) {
   1.601 +          while (_edgeStack.top() != edge) {
   1.602 +            _compMap.set(_edgeStack.top(), _compNum);
   1.603 +            _edgeStack.pop();
   1.604 +          }
   1.605 +          _compMap.set(edge, _compNum);
   1.606 +          _edgeStack.pop();
   1.607 +          ++_compNum;
   1.608 +        }
   1.609 +      }
   1.610 +
   1.611 +    private:
   1.612 +      const Digraph& _graph;
   1.613 +      ArcMap& _compMap;
   1.614 +      int& _compNum;
   1.615 +
   1.616 +      typename Digraph::template NodeMap<int> _numMap;
   1.617 +      typename Digraph::template NodeMap<int> _retMap;
   1.618 +      typename Digraph::template NodeMap<Arc> _predMap;
   1.619 +      std::stack<Edge> _edgeStack;
   1.620 +      int _num;
   1.621 +    };
   1.622 +
   1.623 +
   1.624 +    template <typename Digraph, typename NodeMap>
   1.625 +    class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Digraph> {
   1.626 +    public:
   1.627 +      typedef typename Digraph::Node Node;
   1.628 +      typedef typename Digraph::Arc Arc;
   1.629 +      typedef typename Digraph::Edge Edge;
   1.630 +
   1.631 +      BiNodeConnectedCutNodesVisitor(const Digraph& graph, NodeMap& cutMap,
   1.632 +                                     int& cutNum)
   1.633 +        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
   1.634 +          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   1.635 +
   1.636 +      void start(const Node& node) {
   1.637 +        _predMap.set(node, INVALID);
   1.638 +        rootCut = false;
   1.639 +      }
   1.640 +
   1.641 +      void reach(const Node& node) {
   1.642 +        _numMap.set(node, _num);
   1.643 +        _retMap.set(node, _num);
   1.644 +        ++_num;
   1.645 +      }
   1.646 +
   1.647 +      void discover(const Arc& edge) {
   1.648 +        _predMap.set(_graph.target(edge), _graph.source(edge));
   1.649 +      }
   1.650 +
   1.651 +      void examine(const Arc& edge) {
   1.652 +        if (_graph.source(edge) == _graph.target(edge) &&
   1.653 +            _graph.direction(edge)) {
   1.654 +          if (!_cutMap[_graph.source(edge)]) {
   1.655 +            _cutMap.set(_graph.source(edge), true);
   1.656 +            ++_cutNum;
   1.657 +          }
   1.658 +          return;
   1.659 +        }
   1.660 +        if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
   1.661 +        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
   1.662 +          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
   1.663 +        }
   1.664 +      }
   1.665 +
   1.666 +      void backtrack(const Arc& edge) {
   1.667 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   1.668 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   1.669 +        }
   1.670 +        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
   1.671 +          if (_predMap[_graph.source(edge)] != INVALID) {
   1.672 +            if (!_cutMap[_graph.source(edge)]) {
   1.673 +              _cutMap.set(_graph.source(edge), true);
   1.674 +              ++_cutNum;
   1.675 +            }
   1.676 +          } else if (rootCut) {
   1.677 +            if (!_cutMap[_graph.source(edge)]) {
   1.678 +              _cutMap.set(_graph.source(edge), true);
   1.679 +              ++_cutNum;
   1.680 +            }
   1.681 +          } else {
   1.682 +            rootCut = true;
   1.683 +          }
   1.684 +        }
   1.685 +      }
   1.686 +
   1.687 +    private:
   1.688 +      const Digraph& _graph;
   1.689 +      NodeMap& _cutMap;
   1.690 +      int& _cutNum;
   1.691 +
   1.692 +      typename Digraph::template NodeMap<int> _numMap;
   1.693 +      typename Digraph::template NodeMap<int> _retMap;
   1.694 +      typename Digraph::template NodeMap<Node> _predMap;
   1.695 +      std::stack<Edge> _edgeStack;
   1.696 +      int _num;
   1.697 +      bool rootCut;
   1.698 +    };
   1.699 +
   1.700 +  }
   1.701 +
   1.702 +  template <typename Graph>
   1.703 +  int countBiNodeConnectedComponents(const Graph& graph);
   1.704 +
   1.705 +  /// \ingroup connectivity
   1.706 +  ///
   1.707 +  /// \brief Checks the graph is bi-node-connected.
   1.708 +  ///
   1.709 +  /// This function checks that the undirected graph is bi-node-connected
   1.710 +  /// graph. The graph is bi-node-connected if any two undirected edge is
   1.711 +  /// on same circle.
   1.712 +  ///
   1.713 +  /// \param graph The graph.
   1.714 +  /// \return %True when the graph bi-node-connected.
   1.715 +  template <typename Graph>
   1.716 +  bool biNodeConnected(const Graph& graph) {
   1.717 +    return countBiNodeConnectedComponents(graph) <= 1;
   1.718 +  }
   1.719 +
   1.720 +  /// \ingroup connectivity
   1.721 +  ///
   1.722 +  /// \brief Count the biconnected components.
   1.723 +  ///
   1.724 +  /// This function finds the bi-node-connected components in an undirected
   1.725 +  /// graph. The biconnected components are the classes of an equivalence
   1.726 +  /// relation on the undirected edges. Two undirected edge is in relationship
   1.727 +  /// when they are on same circle.
   1.728 +  ///
   1.729 +  /// \param graph The graph.
   1.730 +  /// \return The number of components.
   1.731 +  template <typename Graph>
   1.732 +  int countBiNodeConnectedComponents(const Graph& graph) {
   1.733 +    checkConcept<concepts::Graph, Graph>();
   1.734 +    typedef typename Graph::NodeIt NodeIt;
   1.735 +
   1.736 +    using namespace _topology_bits;
   1.737 +
   1.738 +    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
   1.739 +
   1.740 +    int compNum = 0;
   1.741 +    Visitor visitor(graph, compNum);
   1.742 +
   1.743 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
   1.744 +    dfs.init();
   1.745 +
   1.746 +    for (NodeIt it(graph); it != INVALID; ++it) {
   1.747 +      if (!dfs.reached(it)) {
   1.748 +        dfs.addSource(it);
   1.749 +        dfs.start();
   1.750 +      }
   1.751 +    }
   1.752 +    return compNum;
   1.753 +  }
   1.754 +
   1.755 +  /// \ingroup connectivity
   1.756 +  ///
   1.757 +  /// \brief Find the bi-node-connected components.
   1.758 +  ///
   1.759 +  /// This function finds the bi-node-connected components in an undirected
   1.760 +  /// graph. The bi-node-connected components are the classes of an equivalence
   1.761 +  /// relation on the undirected edges. Two undirected edge are in relationship
   1.762 +  /// when they are on same circle.
   1.763 +  ///
   1.764 +  /// \param graph The graph.
   1.765 +  /// \retval compMap A writable uedge map. The values will be set from 0
   1.766 +  /// to the number of the biconnected components minus one. Each values
   1.767 +  /// of the map will be set exactly once, the values of a certain component
   1.768 +  /// will be set continuously.
   1.769 +  /// \return The number of components.
   1.770 +  ///
   1.771 +  template <typename Graph, typename EdgeMap>
   1.772 +  int biNodeConnectedComponents(const Graph& graph,
   1.773 +                                EdgeMap& compMap) {
   1.774 +    checkConcept<concepts::Graph, Graph>();
   1.775 +    typedef typename Graph::NodeIt NodeIt;
   1.776 +    typedef typename Graph::Edge Edge;
   1.777 +    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
   1.778 +
   1.779 +    using namespace _topology_bits;
   1.780 +
   1.781 +    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
   1.782 +
   1.783 +    int compNum = 0;
   1.784 +    Visitor visitor(graph, compMap, compNum);
   1.785 +
   1.786 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
   1.787 +    dfs.init();
   1.788 +
   1.789 +    for (NodeIt it(graph); it != INVALID; ++it) {
   1.790 +      if (!dfs.reached(it)) {
   1.791 +        dfs.addSource(it);
   1.792 +        dfs.start();
   1.793 +      }
   1.794 +    }
   1.795 +    return compNum;
   1.796 +  }
   1.797 +
   1.798 +  /// \ingroup connectivity
   1.799 +  ///
   1.800 +  /// \brief Find the bi-node-connected cut nodes.
   1.801 +  ///
   1.802 +  /// This function finds the bi-node-connected cut nodes in an undirected
   1.803 +  /// graph. The bi-node-connected components are the classes of an equivalence
   1.804 +  /// relation on the undirected edges. Two undirected edges are in
   1.805 +  /// relationship when they are on same circle. The biconnected components
   1.806 +  /// are separted by nodes which are the cut nodes of the components.
   1.807 +  ///
   1.808 +  /// \param graph The graph.
   1.809 +  /// \retval cutMap A writable edge map. The values will be set true when
   1.810 +  /// the node separate two or more components.
   1.811 +  /// \return The number of the cut nodes.
   1.812 +  template <typename Graph, typename NodeMap>
   1.813 +  int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
   1.814 +    checkConcept<concepts::Graph, Graph>();
   1.815 +    typedef typename Graph::Node Node;
   1.816 +    typedef typename Graph::NodeIt NodeIt;
   1.817 +    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
   1.818 +
   1.819 +    using namespace _topology_bits;
   1.820 +
   1.821 +    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
   1.822 +
   1.823 +    int cutNum = 0;
   1.824 +    Visitor visitor(graph, cutMap, cutNum);
   1.825 +
   1.826 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
   1.827 +    dfs.init();
   1.828 +
   1.829 +    for (NodeIt it(graph); it != INVALID; ++it) {
   1.830 +      if (!dfs.reached(it)) {
   1.831 +        dfs.addSource(it);
   1.832 +        dfs.start();
   1.833 +      }
   1.834 +    }
   1.835 +    return cutNum;
   1.836 +  }
   1.837 +
   1.838 +  namespace _topology_bits {
   1.839 +
   1.840 +    template <typename Digraph>
   1.841 +    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
   1.842 +    public:
   1.843 +      typedef typename Digraph::Node Node;
   1.844 +      typedef typename Digraph::Arc Arc;
   1.845 +      typedef typename Digraph::Edge Edge;
   1.846 +
   1.847 +      CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
   1.848 +        : _graph(graph), _compNum(compNum),
   1.849 +          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   1.850 +
   1.851 +      void start(const Node& node) {
   1.852 +        _predMap.set(node, INVALID);
   1.853 +      }
   1.854 +
   1.855 +      void reach(const Node& node) {
   1.856 +        _numMap.set(node, _num);
   1.857 +        _retMap.set(node, _num);
   1.858 +        ++_num;
   1.859 +      }
   1.860 +
   1.861 +      void leave(const Node& node) {
   1.862 +        if (_numMap[node] <= _retMap[node]) {
   1.863 +          ++_compNum;
   1.864 +        }
   1.865 +      }
   1.866 +
   1.867 +      void discover(const Arc& edge) {
   1.868 +        _predMap.set(_graph.target(edge), edge);
   1.869 +      }
   1.870 +
   1.871 +      void examine(const Arc& edge) {
   1.872 +        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
   1.873 +          return;
   1.874 +        }
   1.875 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   1.876 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   1.877 +        }
   1.878 +      }
   1.879 +
   1.880 +      void backtrack(const Arc& edge) {
   1.881 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   1.882 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   1.883 +        }
   1.884 +      }
   1.885 +
   1.886 +    private:
   1.887 +      const Digraph& _graph;
   1.888 +      int& _compNum;
   1.889 +
   1.890 +      typename Digraph::template NodeMap<int> _numMap;
   1.891 +      typename Digraph::template NodeMap<int> _retMap;
   1.892 +      typename Digraph::template NodeMap<Arc> _predMap;
   1.893 +      int _num;
   1.894 +    };
   1.895 +
   1.896 +    template <typename Digraph, typename NodeMap>
   1.897 +    class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
   1.898 +    public:
   1.899 +      typedef typename Digraph::Node Node;
   1.900 +      typedef typename Digraph::Arc Arc;
   1.901 +      typedef typename Digraph::Edge Edge;
   1.902 +
   1.903 +      BiEdgeConnectedComponentsVisitor(const Digraph& graph,
   1.904 +                                       NodeMap& compMap, int &compNum)
   1.905 +        : _graph(graph), _compMap(compMap), _compNum(compNum),
   1.906 +          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   1.907 +
   1.908 +      void start(const Node& node) {
   1.909 +        _predMap.set(node, INVALID);
   1.910 +      }
   1.911 +
   1.912 +      void reach(const Node& node) {
   1.913 +        _numMap.set(node, _num);
   1.914 +        _retMap.set(node, _num);
   1.915 +        _nodeStack.push(node);
   1.916 +        ++_num;
   1.917 +      }
   1.918 +
   1.919 +      void leave(const Node& node) {
   1.920 +        if (_numMap[node] <= _retMap[node]) {
   1.921 +          while (_nodeStack.top() != node) {
   1.922 +            _compMap.set(_nodeStack.top(), _compNum);
   1.923 +            _nodeStack.pop();
   1.924 +          }
   1.925 +          _compMap.set(node, _compNum);
   1.926 +          _nodeStack.pop();
   1.927 +          ++_compNum;
   1.928 +        }
   1.929 +      }
   1.930 +
   1.931 +      void discover(const Arc& edge) {
   1.932 +        _predMap.set(_graph.target(edge), edge);
   1.933 +      }
   1.934 +
   1.935 +      void examine(const Arc& edge) {
   1.936 +        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
   1.937 +          return;
   1.938 +        }
   1.939 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   1.940 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   1.941 +        }
   1.942 +      }
   1.943 +
   1.944 +      void backtrack(const Arc& edge) {
   1.945 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
   1.946 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
   1.947 +        }
   1.948 +      }
   1.949 +
   1.950 +    private:
   1.951 +      const Digraph& _graph;
   1.952 +      NodeMap& _compMap;
   1.953 +      int& _compNum;
   1.954 +
   1.955 +      typename Digraph::template NodeMap<int> _numMap;
   1.956 +      typename Digraph::template NodeMap<int> _retMap;
   1.957 +      typename Digraph::template NodeMap<Arc> _predMap;
   1.958 +      std::stack<Node> _nodeStack;
   1.959 +      int _num;
   1.960 +    };
   1.961 +
   1.962 +
   1.963 +    template <typename Digraph, typename ArcMap>
   1.964 +    class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
   1.965 +    public:
   1.966 +      typedef typename Digraph::Node Node;
   1.967 +      typedef typename Digraph::Arc Arc;
   1.968 +      typedef typename Digraph::Edge Edge;
   1.969 +
   1.970 +      BiEdgeConnectedCutEdgesVisitor(const Digraph& graph,
   1.971 +                                     ArcMap& cutMap, int &cutNum)
   1.972 +        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
   1.973 +          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
   1.974 +
   1.975 +      void start(const Node& node) {
   1.976 +        _predMap[node] = INVALID;
   1.977 +      }
   1.978 +
   1.979 +      void reach(const Node& node) {
   1.980 +        _numMap.set(node, _num);
   1.981 +        _retMap.set(node, _num);
   1.982 +        ++_num;
   1.983 +      }
   1.984 +
   1.985 +      void leave(const Node& node) {
   1.986 +        if (_numMap[node] <= _retMap[node]) {
   1.987 +          if (_predMap[node] != INVALID) {
   1.988 +            _cutMap.set(_predMap[node], true);
   1.989 +            ++_cutNum;
   1.990 +          }
   1.991 +        }
   1.992 +      }
   1.993 +
   1.994 +      void discover(const Arc& edge) {
   1.995 +        _predMap.set(_graph.target(edge), edge);
   1.996 +      }
   1.997 +
   1.998 +      void examine(const Arc& edge) {
   1.999 +        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
  1.1000 +          return;
  1.1001 +        }
  1.1002 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
  1.1003 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
  1.1004 +        }
  1.1005 +      }
  1.1006 +
  1.1007 +      void backtrack(const Arc& edge) {
  1.1008 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
  1.1009 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
  1.1010 +        }
  1.1011 +      }
  1.1012 +
  1.1013 +    private:
  1.1014 +      const Digraph& _graph;
  1.1015 +      ArcMap& _cutMap;
  1.1016 +      int& _cutNum;
  1.1017 +
  1.1018 +      typename Digraph::template NodeMap<int> _numMap;
  1.1019 +      typename Digraph::template NodeMap<int> _retMap;
  1.1020 +      typename Digraph::template NodeMap<Arc> _predMap;
  1.1021 +      int _num;
  1.1022 +    };
  1.1023 +  }
  1.1024 +
  1.1025 +  template <typename Graph>
  1.1026 +  int countBiEdgeConnectedComponents(const Graph& graph);
  1.1027 +
  1.1028 +  /// \ingroup connectivity
  1.1029 +  ///
  1.1030 +  /// \brief Checks that the graph is bi-edge-connected.
  1.1031 +  ///
  1.1032 +  /// This function checks that the graph is bi-edge-connected. The undirected
  1.1033 +  /// graph is bi-edge-connected when any two nodes are connected with two
  1.1034 +  /// edge-disjoint paths.
  1.1035 +  ///
  1.1036 +  /// \param graph The undirected graph.
  1.1037 +  /// \return The number of components.
  1.1038 +  template <typename Graph>
  1.1039 +  bool biEdgeConnected(const Graph& graph) {
  1.1040 +    return countBiEdgeConnectedComponents(graph) <= 1;
  1.1041 +  }
  1.1042 +
  1.1043 +  /// \ingroup connectivity
  1.1044 +  ///
  1.1045 +  /// \brief Count the bi-edge-connected components.
  1.1046 +  ///
  1.1047 +  /// This function count the bi-edge-connected components in an undirected
  1.1048 +  /// graph. The bi-edge-connected components are the classes of an equivalence
  1.1049 +  /// relation on the nodes. Two nodes are in relationship when they are
  1.1050 +  /// connected with at least two edge-disjoint paths.
  1.1051 +  ///
  1.1052 +  /// \param graph The undirected graph.
  1.1053 +  /// \return The number of components.
  1.1054 +  template <typename Graph>
  1.1055 +  int countBiEdgeConnectedComponents(const Graph& graph) {
  1.1056 +    checkConcept<concepts::Graph, Graph>();
  1.1057 +    typedef typename Graph::NodeIt NodeIt;
  1.1058 +
  1.1059 +    using namespace _topology_bits;
  1.1060 +
  1.1061 +    typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
  1.1062 +
  1.1063 +    int compNum = 0;
  1.1064 +    Visitor visitor(graph, compNum);
  1.1065 +
  1.1066 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
  1.1067 +    dfs.init();
  1.1068 +
  1.1069 +    for (NodeIt it(graph); it != INVALID; ++it) {
  1.1070 +      if (!dfs.reached(it)) {
  1.1071 +        dfs.addSource(it);
  1.1072 +        dfs.start();
  1.1073 +      }
  1.1074 +    }
  1.1075 +    return compNum;
  1.1076 +  }
  1.1077 +
  1.1078 +  /// \ingroup connectivity
  1.1079 +  ///
  1.1080 +  /// \brief Find the bi-edge-connected components.
  1.1081 +  ///
  1.1082 +  /// This function finds the bi-edge-connected components in an undirected
  1.1083 +  /// graph. The bi-edge-connected components are the classes of an equivalence
  1.1084 +  /// relation on the nodes. Two nodes are in relationship when they are
  1.1085 +  /// connected at least two edge-disjoint paths.
  1.1086 +  ///
  1.1087 +  /// \param graph The graph.
  1.1088 +  /// \retval compMap A writable node map. The values will be set from 0 to
  1.1089 +  /// the number of the biconnected components minus one. Each values
  1.1090 +  /// of the map will be set exactly once, the values of a certain component
  1.1091 +  /// will be set continuously.
  1.1092 +  /// \return The number of components.
  1.1093 +  ///
  1.1094 +  template <typename Graph, typename NodeMap>
  1.1095 +  int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
  1.1096 +    checkConcept<concepts::Graph, Graph>();
  1.1097 +    typedef typename Graph::NodeIt NodeIt;
  1.1098 +    typedef typename Graph::Node Node;
  1.1099 +    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
  1.1100 +
  1.1101 +    using namespace _topology_bits;
  1.1102 +
  1.1103 +    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
  1.1104 +
  1.1105 +    int compNum = 0;
  1.1106 +    Visitor visitor(graph, compMap, compNum);
  1.1107 +
  1.1108 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
  1.1109 +    dfs.init();
  1.1110 +
  1.1111 +    for (NodeIt it(graph); it != INVALID; ++it) {
  1.1112 +      if (!dfs.reached(it)) {
  1.1113 +        dfs.addSource(it);
  1.1114 +        dfs.start();
  1.1115 +      }
  1.1116 +    }
  1.1117 +    return compNum;
  1.1118 +  }
  1.1119 +
  1.1120 +  /// \ingroup connectivity
  1.1121 +  ///
  1.1122 +  /// \brief Find the bi-edge-connected cut edges.
  1.1123 +  ///
  1.1124 +  /// This function finds the bi-edge-connected components in an undirected
  1.1125 +  /// graph. The bi-edge-connected components are the classes of an equivalence
  1.1126 +  /// relation on the nodes. Two nodes are in relationship when they are
  1.1127 +  /// connected with at least two edge-disjoint paths. The bi-edge-connected
  1.1128 +  /// components are separted by edges which are the cut edges of the
  1.1129 +  /// components.
  1.1130 +  ///
  1.1131 +  /// \param graph The graph.
  1.1132 +  /// \retval cutMap A writable node map. The values will be set true when the
  1.1133 +  /// edge is a cut edge.
  1.1134 +  /// \return The number of cut edges.
  1.1135 +  template <typename Graph, typename EdgeMap>
  1.1136 +  int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
  1.1137 +    checkConcept<concepts::Graph, Graph>();
  1.1138 +    typedef typename Graph::NodeIt NodeIt;
  1.1139 +    typedef typename Graph::Edge Edge;
  1.1140 +    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
  1.1141 +
  1.1142 +    using namespace _topology_bits;
  1.1143 +
  1.1144 +    typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
  1.1145 +
  1.1146 +    int cutNum = 0;
  1.1147 +    Visitor visitor(graph, cutMap, cutNum);
  1.1148 +
  1.1149 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
  1.1150 +    dfs.init();
  1.1151 +
  1.1152 +    for (NodeIt it(graph); it != INVALID; ++it) {
  1.1153 +      if (!dfs.reached(it)) {
  1.1154 +        dfs.addSource(it);
  1.1155 +        dfs.start();
  1.1156 +      }
  1.1157 +    }
  1.1158 +    return cutNum;
  1.1159 +  }
  1.1160 +
  1.1161 +
  1.1162 +  namespace _topology_bits {
  1.1163 +
  1.1164 +    template <typename Digraph, typename IntNodeMap>
  1.1165 +    class TopologicalSortVisitor : public DfsVisitor<Digraph> {
  1.1166 +    public:
  1.1167 +      typedef typename Digraph::Node Node;
  1.1168 +      typedef typename Digraph::Arc edge;
  1.1169 +
  1.1170 +      TopologicalSortVisitor(IntNodeMap& order, int num)
  1.1171 +        : _order(order), _num(num) {}
  1.1172 +
  1.1173 +      void leave(const Node& node) {
  1.1174 +        _order.set(node, --_num);
  1.1175 +      }
  1.1176 +
  1.1177 +    private:
  1.1178 +      IntNodeMap& _order;
  1.1179 +      int _num;
  1.1180 +    };
  1.1181 +
  1.1182 +  }
  1.1183 +
  1.1184 +  /// \ingroup connectivity
  1.1185 +  ///
  1.1186 +  /// \brief Sort the nodes of a DAG into topolgical order.
  1.1187 +  ///
  1.1188 +  /// Sort the nodes of a DAG into topolgical order.
  1.1189 +  ///
  1.1190 +  /// \param graph The graph. It must be directed and acyclic.
  1.1191 +  /// \retval order A writable node map. The values will be set from 0 to
  1.1192 +  /// the number of the nodes in the graph minus one. Each values of the map
  1.1193 +  /// will be set exactly once, the values  will be set descending order.
  1.1194 +  ///
  1.1195 +  /// \see checkedTopologicalSort
  1.1196 +  /// \see dag
  1.1197 +  template <typename Digraph, typename NodeMap>
  1.1198 +  void topologicalSort(const Digraph& graph, NodeMap& order) {
  1.1199 +    using namespace _topology_bits;
  1.1200 +
  1.1201 +    checkConcept<concepts::Digraph, Digraph>();
  1.1202 +    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
  1.1203 +
  1.1204 +    typedef typename Digraph::Node Node;
  1.1205 +    typedef typename Digraph::NodeIt NodeIt;
  1.1206 +    typedef typename Digraph::Arc Arc;
  1.1207 +
  1.1208 +    TopologicalSortVisitor<Digraph, NodeMap>
  1.1209 +      visitor(order, countNodes(graph));
  1.1210 +
  1.1211 +    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
  1.1212 +      dfs(graph, visitor);
  1.1213 +
  1.1214 +    dfs.init();
  1.1215 +    for (NodeIt it(graph); it != INVALID; ++it) {
  1.1216 +      if (!dfs.reached(it)) {
  1.1217 +        dfs.addSource(it);
  1.1218 +        dfs.start();
  1.1219 +      }
  1.1220 +    }
  1.1221 +  }
  1.1222 +
  1.1223 +  /// \ingroup connectivity
  1.1224 +  ///
  1.1225 +  /// \brief Sort the nodes of a DAG into topolgical order.
  1.1226 +  ///
  1.1227 +  /// Sort the nodes of a DAG into topolgical order. It also checks
  1.1228 +  /// that the given graph is DAG.
  1.1229 +  ///
  1.1230 +  /// \param graph The graph. It must be directed and acyclic.
  1.1231 +  /// \retval order A readable - writable node map. The values will be set
  1.1232 +  /// from 0 to the number of the nodes in the graph minus one. Each values
  1.1233 +  /// of the map will be set exactly once, the values will be set descending
  1.1234 +  /// order.
  1.1235 +  /// \return %False when the graph is not DAG.
  1.1236 +  ///
  1.1237 +  /// \see topologicalSort
  1.1238 +  /// \see dag
  1.1239 +  template <typename Digraph, typename NodeMap>
  1.1240 +  bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) {
  1.1241 +    using namespace _topology_bits;
  1.1242 +
  1.1243 +    checkConcept<concepts::Digraph, Digraph>();
  1.1244 +    checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
  1.1245 +      NodeMap>();
  1.1246 +
  1.1247 +    typedef typename Digraph::Node Node;
  1.1248 +    typedef typename Digraph::NodeIt NodeIt;
  1.1249 +    typedef typename Digraph::Arc Arc;
  1.1250 +
  1.1251 +    order = constMap<Node, int, -1>();
  1.1252 +
  1.1253 +    TopologicalSortVisitor<Digraph, NodeMap>
  1.1254 +      visitor(order, countNodes(graph));
  1.1255 +
  1.1256 +    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
  1.1257 +      dfs(graph, visitor);
  1.1258 +
  1.1259 +    dfs.init();
  1.1260 +    for (NodeIt it(graph); it != INVALID; ++it) {
  1.1261 +      if (!dfs.reached(it)) {
  1.1262 +        dfs.addSource(it);
  1.1263 +        while (!dfs.emptyQueue()) {
  1.1264 +           Arc edge = dfs.nextArc();
  1.1265 +           Node target = graph.target(edge);
  1.1266 +           if (dfs.reached(target) && order[target] == -1) {
  1.1267 +             return false;
  1.1268 +           }
  1.1269 +           dfs.processNextArc();
  1.1270 +         }
  1.1271 +      }
  1.1272 +    }
  1.1273 +    return true;
  1.1274 +  }
  1.1275 +
  1.1276 +  /// \ingroup connectivity
  1.1277 +  ///
  1.1278 +  /// \brief Check that the given directed graph is a DAG.
  1.1279 +  ///
  1.1280 +  /// Check that the given directed graph is a DAG. The DAG is
  1.1281 +  /// an Directed Acyclic Digraph.
  1.1282 +  /// \return %False when the graph is not DAG.
  1.1283 +  /// \see acyclic
  1.1284 +  template <typename Digraph>
  1.1285 +  bool dag(const Digraph& graph) {
  1.1286 +
  1.1287 +    checkConcept<concepts::Digraph, Digraph>();
  1.1288 +
  1.1289 +    typedef typename Digraph::Node Node;
  1.1290 +    typedef typename Digraph::NodeIt NodeIt;
  1.1291 +    typedef typename Digraph::Arc Arc;
  1.1292 +
  1.1293 +    typedef typename Digraph::template NodeMap<bool> ProcessedMap;
  1.1294 +
  1.1295 +    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
  1.1296 +      Create dfs(graph);
  1.1297 +
  1.1298 +    ProcessedMap processed(graph);
  1.1299 +    dfs.processedMap(processed);
  1.1300 +
  1.1301 +    dfs.init();
  1.1302 +    for (NodeIt it(graph); it != INVALID; ++it) {
  1.1303 +      if (!dfs.reached(it)) {
  1.1304 +        dfs.addSource(it);
  1.1305 +        while (!dfs.emptyQueue()) {
  1.1306 +          Arc edge = dfs.nextArc();
  1.1307 +          Node target = graph.target(edge);
  1.1308 +          if (dfs.reached(target) && !processed[target]) {
  1.1309 +            return false;
  1.1310 +          }
  1.1311 +          dfs.processNextArc();
  1.1312 +        }
  1.1313 +      }
  1.1314 +    }
  1.1315 +    return true;
  1.1316 +  }
  1.1317 +
  1.1318 +  /// \ingroup connectivity
  1.1319 +  ///
  1.1320 +  /// \brief Check that the given undirected graph is acyclic.
  1.1321 +  ///
  1.1322 +  /// Check that the given undirected graph acyclic.
  1.1323 +  /// \param graph The undirected graph.
  1.1324 +  /// \return %True when there is no circle in the graph.
  1.1325 +  /// \see dag
  1.1326 +  template <typename Graph>
  1.1327 +  bool acyclic(const Graph& graph) {
  1.1328 +    checkConcept<concepts::Graph, Graph>();
  1.1329 +    typedef typename Graph::Node Node;
  1.1330 +    typedef typename Graph::NodeIt NodeIt;
  1.1331 +    typedef typename Graph::Arc Arc;
  1.1332 +    Dfs<Graph> dfs(graph);
  1.1333 +    dfs.init();
  1.1334 +    for (NodeIt it(graph); it != INVALID; ++it) {
  1.1335 +      if (!dfs.reached(it)) {
  1.1336 +        dfs.addSource(it);
  1.1337 +        while (!dfs.emptyQueue()) {
  1.1338 +          Arc edge = dfs.nextArc();
  1.1339 +          Node source = graph.source(edge);
  1.1340 +          Node target = graph.target(edge);
  1.1341 +          if (dfs.reached(target) &&
  1.1342 +              dfs.predArc(source) != graph.oppositeArc(edge)) {
  1.1343 +            return false;
  1.1344 +          }
  1.1345 +          dfs.processNextArc();
  1.1346 +        }
  1.1347 +      }
  1.1348 +    }
  1.1349 +    return true;
  1.1350 +  }
  1.1351 +
  1.1352 +  /// \ingroup connectivity
  1.1353 +  ///
  1.1354 +  /// \brief Check that the given undirected graph is tree.
  1.1355 +  ///
  1.1356 +  /// Check that the given undirected graph is tree.
  1.1357 +  /// \param graph The undirected graph.
  1.1358 +  /// \return %True when the graph is acyclic and connected.
  1.1359 +  template <typename Graph>
  1.1360 +  bool tree(const Graph& graph) {
  1.1361 +    checkConcept<concepts::Graph, Graph>();
  1.1362 +    typedef typename Graph::Node Node;
  1.1363 +    typedef typename Graph::NodeIt NodeIt;
  1.1364 +    typedef typename Graph::Arc Arc;
  1.1365 +    Dfs<Graph> dfs(graph);
  1.1366 +    dfs.init();
  1.1367 +    dfs.addSource(NodeIt(graph));
  1.1368 +    while (!dfs.emptyQueue()) {
  1.1369 +      Arc edge = dfs.nextArc();
  1.1370 +      Node source = graph.source(edge);
  1.1371 +      Node target = graph.target(edge);
  1.1372 +      if (dfs.reached(target) &&
  1.1373 +          dfs.predArc(source) != graph.oppositeArc(edge)) {
  1.1374 +        return false;
  1.1375 +      }
  1.1376 +      dfs.processNextArc();
  1.1377 +    }
  1.1378 +    for (NodeIt it(graph); it != INVALID; ++it) {
  1.1379 +      if (!dfs.reached(it)) {
  1.1380 +        return false;
  1.1381 +      }
  1.1382 +    }
  1.1383 +    return true;
  1.1384 +  }
  1.1385 +
  1.1386 +  namespace _topology_bits {
  1.1387 +
  1.1388 +    template <typename Digraph>
  1.1389 +    class BipartiteVisitor : public BfsVisitor<Digraph> {
  1.1390 +    public:
  1.1391 +      typedef typename Digraph::Arc Arc;
  1.1392 +      typedef typename Digraph::Node Node;
  1.1393 +
  1.1394 +      BipartiteVisitor(const Digraph& graph, bool& bipartite)
  1.1395 +        : _graph(graph), _part(graph), _bipartite(bipartite) {}
  1.1396 +
  1.1397 +      void start(const Node& node) {
  1.1398 +        _part[node] = true;
  1.1399 +      }
  1.1400 +      void discover(const Arc& edge) {
  1.1401 +        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
  1.1402 +      }
  1.1403 +      void examine(const Arc& edge) {
  1.1404 +        _bipartite = _bipartite &&
  1.1405 +          _part[_graph.target(edge)] != _part[_graph.source(edge)];
  1.1406 +      }
  1.1407 +
  1.1408 +    private:
  1.1409 +
  1.1410 +      const Digraph& _graph;
  1.1411 +      typename Digraph::template NodeMap<bool> _part;
  1.1412 +      bool& _bipartite;
  1.1413 +    };
  1.1414 +
  1.1415 +    template <typename Digraph, typename PartMap>
  1.1416 +    class BipartitePartitionsVisitor : public BfsVisitor<Digraph> {
  1.1417 +    public:
  1.1418 +      typedef typename Digraph::Arc Arc;
  1.1419 +      typedef typename Digraph::Node Node;
  1.1420 +
  1.1421 +      BipartitePartitionsVisitor(const Digraph& graph,
  1.1422 +                                 PartMap& part, bool& bipartite)
  1.1423 +        : _graph(graph), _part(part), _bipartite(bipartite) {}
  1.1424 +
  1.1425 +      void start(const Node& node) {
  1.1426 +        _part.set(node, true);
  1.1427 +      }
  1.1428 +      void discover(const Arc& edge) {
  1.1429 +        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
  1.1430 +      }
  1.1431 +      void examine(const Arc& edge) {
  1.1432 +        _bipartite = _bipartite &&
  1.1433 +          _part[_graph.target(edge)] != _part[_graph.source(edge)];
  1.1434 +      }
  1.1435 +
  1.1436 +    private:
  1.1437 +
  1.1438 +      const Digraph& _graph;
  1.1439 +      PartMap& _part;
  1.1440 +      bool& _bipartite;
  1.1441 +    };
  1.1442 +  }
  1.1443 +
  1.1444 +  /// \ingroup connectivity
  1.1445 +  ///
  1.1446 +  /// \brief Check if the given undirected graph is bipartite or not
  1.1447 +  ///
  1.1448 +  /// The function checks if the given undirected \c graph graph is bipartite
  1.1449 +  /// or not. The \ref Bfs algorithm is used to calculate the result.
  1.1450 +  /// \param graph The undirected graph.
  1.1451 +  /// \return %True if \c graph is bipartite, %false otherwise.
  1.1452 +  /// \sa bipartitePartitions
  1.1453 +  template<typename Graph>
  1.1454 +  inline bool bipartite(const Graph &graph){
  1.1455 +    using namespace _topology_bits;
  1.1456 +
  1.1457 +    checkConcept<concepts::Graph, Graph>();
  1.1458 +
  1.1459 +    typedef typename Graph::NodeIt NodeIt;
  1.1460 +    typedef typename Graph::ArcIt ArcIt;
  1.1461 +
  1.1462 +    bool bipartite = true;
  1.1463 +
  1.1464 +    BipartiteVisitor<Graph>
  1.1465 +      visitor(graph, bipartite);
  1.1466 +    BfsVisit<Graph, BipartiteVisitor<Graph> >
  1.1467 +      bfs(graph, visitor);
  1.1468 +    bfs.init();
  1.1469 +    for(NodeIt it(graph); it != INVALID; ++it) {
  1.1470 +      if(!bfs.reached(it)){
  1.1471 +        bfs.addSource(it);
  1.1472 +        while (!bfs.emptyQueue()) {
  1.1473 +          bfs.processNextNode();
  1.1474 +          if (!bipartite) return false;
  1.1475 +        }
  1.1476 +      }
  1.1477 +    }
  1.1478 +    return true;
  1.1479 +  }
  1.1480 +
  1.1481 +  /// \ingroup connectivity
  1.1482 +  ///
  1.1483 +  /// \brief Check if the given undirected graph is bipartite or not
  1.1484 +  ///
  1.1485 +  /// The function checks if the given undirected graph is bipartite
  1.1486 +  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
  1.1487 +  /// During the execution, the \c partMap will be set as the two
  1.1488 +  /// partitions of the graph.
  1.1489 +  /// \param graph The undirected graph.
  1.1490 +  /// \retval partMap A writable bool map of nodes. It will be set as the
  1.1491 +  /// two partitions of the graph.
  1.1492 +  /// \return %True if \c graph is bipartite, %false otherwise.
  1.1493 +  template<typename Graph, typename NodeMap>
  1.1494 +  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
  1.1495 +    using namespace _topology_bits;
  1.1496 +
  1.1497 +    checkConcept<concepts::Graph, Graph>();
  1.1498 +
  1.1499 +    typedef typename Graph::Node Node;
  1.1500 +    typedef typename Graph::NodeIt NodeIt;
  1.1501 +    typedef typename Graph::ArcIt ArcIt;
  1.1502 +
  1.1503 +    bool bipartite = true;
  1.1504 +
  1.1505 +    BipartitePartitionsVisitor<Graph, NodeMap>
  1.1506 +      visitor(graph, partMap, bipartite);
  1.1507 +    BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >
  1.1508 +      bfs(graph, visitor);
  1.1509 +    bfs.init();
  1.1510 +    for(NodeIt it(graph); it != INVALID; ++it) {
  1.1511 +      if(!bfs.reached(it)){
  1.1512 +        bfs.addSource(it);
  1.1513 +        while (!bfs.emptyQueue()) {
  1.1514 +          bfs.processNextNode();
  1.1515 +          if (!bipartite) return false;
  1.1516 +        }
  1.1517 +      }
  1.1518 +    }
  1.1519 +    return true;
  1.1520 +  }
  1.1521 +
  1.1522 +  /// \brief Returns true when there are not loop edges in the graph.
  1.1523 +  ///
  1.1524 +  /// Returns true when there are not loop edges in the graph.
  1.1525 +  template <typename Digraph>
  1.1526 +  bool loopFree(const Digraph& graph) {
  1.1527 +    for (typename Digraph::ArcIt it(graph); it != INVALID; ++it) {
  1.1528 +      if (graph.source(it) == graph.target(it)) return false;
  1.1529 +    }
  1.1530 +    return true;
  1.1531 +  }
  1.1532 +
  1.1533 +  /// \brief Returns true when there are not parallel edges in the graph.
  1.1534 +  ///
  1.1535 +  /// Returns true when there are not parallel edges in the graph.
  1.1536 +  template <typename Digraph>
  1.1537 +  bool parallelFree(const Digraph& graph) {
  1.1538 +    typename Digraph::template NodeMap<bool> reached(graph, false);
  1.1539 +    for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
  1.1540 +      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
  1.1541 +        if (reached[graph.target(e)]) return false;
  1.1542 +        reached.set(graph.target(e), true);
  1.1543 +      }
  1.1544 +      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
  1.1545 +        reached.set(graph.target(e), false);
  1.1546 +      }
  1.1547 +    }
  1.1548 +    return true;
  1.1549 +  }
  1.1550 +
  1.1551 +  /// \brief Returns true when there are not loop edges and parallel
  1.1552 +  /// edges in the graph.
  1.1553 +  ///
  1.1554 +  /// Returns true when there are not loop edges and parallel edges in
  1.1555 +  /// the graph.
  1.1556 +  template <typename Digraph>
  1.1557 +  bool simpleDigraph(const Digraph& graph) {
  1.1558 +    typename Digraph::template NodeMap<bool> reached(graph, false);
  1.1559 +    for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
  1.1560 +      reached.set(n, true);
  1.1561 +      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
  1.1562 +        if (reached[graph.target(e)]) return false;
  1.1563 +        reached.set(graph.target(e), true);
  1.1564 +      }
  1.1565 +      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
  1.1566 +        reached.set(graph.target(e), false);
  1.1567 +      }
  1.1568 +      reached.set(n, false);
  1.1569 +    }
  1.1570 +    return true;
  1.1571 +  }
  1.1572 +
  1.1573 +} //namespace lemon
  1.1574 +
  1.1575 +#endif //LEMON_TOPOLOGY_H