RhodeCode

    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);

    rdfs.init();

    rdfs.addSource(source);

    rdfs.start();

    for (RNodeIt it(rdigraph); it != INVALID; ++it) {

      if (!rdfs.reached(it)) {

        return false;

      }

    }

    return true;

  }

  /// \ingroup connectivity

  ///

  /// \brief Count the strongly connected components of a directed graph

  ///

  /// Count the strongly connected components of a directed graph.

  /// The strongly connected components are the classes of an

  /// equivalence relation on the nodes of the graph. Two nodes are in

  /// the same class if they are connected with directed paths in both

  /// direction.

  ///

  /// \return The number of components

  /// \note By definition, the empty graph has zero

  /// strongly connected components.

  template <typename Digraph>

  int countStronglyConnectedComponents(const Digraph& digraph) {

    checkConcept<concepts::Digraph, Digraph>();

    using namespace _connectivity_bits;

    typedef typename Digraph::Node Node;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::ArcIt ArcIt;

    typedef std::vector<Node> Container;

    typedef typename Container::iterator Iterator;

    Container nodes(countNodes(digraph));

    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;

    Visitor visitor(nodes.begin());

    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);

    dfs.init();

    for (NodeIt it(digraph); it != INVALID; ++it) {

    typedef typename Digraph::Arc Arc;

    TopologicalSortVisitor<Digraph, NodeMap>

      visitor(order, countNodes(graph));

    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >

      dfs(graph, visitor);

    dfs.init();

    for (NodeIt it(graph); it != INVALID; ++it) {

      if (!dfs.reached(it)) {

        dfs.addSource(it);

        dfs.start();

      }

    }

  }

  /// \ingroup connectivity

  ///

  /// \brief Sort the nodes of a DAG into topolgical order.

  ///

  /// Sort the nodes of a DAG into topolgical order. It also checks

  /// that the given graph is DAG.

  ///

  /// \retval order A readable - writable node map. The values will be set

  /// from 0 to the number of the nodes in the graph minus one. Each values

  /// of the map will be set exactly once, the values will be set descending

  /// order.

  /// \return %False when the graph is not DAG.

  ///

  /// \see topologicalSort

  /// \see dag

  template <typename Digraph, typename NodeMap>

  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {

    using namespace _connectivity_bits;

    checkConcept<concepts::Digraph, Digraph>();

    checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,

      NodeMap>();

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    for (NodeIt it(digraph); it != INVALID; ++it) {

      order.set(it, -1);

    }

    }

  public:

    /// \brief Constructor

    ///

    /// Constructor.

    MaxMatching(const Graph& graph)

      : _graph(graph), _matching(0), _status(0), _ear(0),

        _blossom_set_index(0), _blossom_set(0), _blossom_rep(0),

        _tree_set_index(0), _tree_set(0) {}

    ~MaxMatching() {

      destroyStructures();

    }

    /// \name Execution control

    /// The simplest way to execute the algorithm is to use the

    /// \c run() member function.

    /// \n

    /// If you need better control on the execution, you must call

    /// \ref init(), \ref greedyInit() or \ref matchingInit()

    /// functions first, then you can start the algorithm with the \ref

    ///@{

    /// \brief Sets the actual matching to the empty matching.

    ///

    /// Sets the actual matching to the empty matching.

    ///

    void init() {

      createStructures();

      for(NodeIt n(_graph); n != INVALID; ++n) {

        _matching->set(n, INVALID);

        _status->set(n, UNMATCHED);

      }

    }

    ///\brief Finds an initial matching in a greedy way

    ///

    ///It finds an initial matching in a greedy way.

    void greedyInit() {

      createStructures();

      for (NodeIt n(_graph); n != INVALID; ++n) {

        _matching->set(n, INVALID);

        _status->set(n, UNMATCHED);

      }

namespace lemon {

  /// \addtogroup shortest_path

  /// @{

  /// \brief Algorithm for finding arc-disjoint paths between two nodes

  /// having minimum total length.

  ///

  /// \ref lemon::Suurballe "Suurballe" implements an algorithm for

  /// finding arc-disjoint paths having minimum total length (cost)

  /// from a given source node to a given target node in a digraph.

  ///

  /// In fact, this implementation is the specialization of the

  /// \ref CapacityScaling "successive shortest path" algorithm.

  ///

  /// \tparam Digraph The digraph type the algorithm runs on.

  /// The default value is \c ListDigraph.

  /// \tparam LengthMap The type of the length (cost) map.

  /// The default value is <tt>Digraph::ArcMap<int></tt>.

  ///

  /// \warning Length values should be \e non-negative \e integers.

  ///

  /// \note For finding node-disjoint paths this algorithm can be used

#ifdef DOXYGEN

  template <typename Digraph, typename LengthMap>

#else

  template < typename Digraph = ListDigraph,

             typename LengthMap = typename Digraph::template ArcMap<int> >

#endif

  class Suurballe

  {

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    typedef typename LengthMap::Value Length;

    typedef ConstMap<Arc, int> ConstArcMap;

    typedef typename Digraph::template NodeMap<Arc> PredMap;

  public:

    /// The type of the flow map.

    typedef typename Digraph::template ArcMap<int> FlowMap;

    /// The type of the potential map.

    typedef typename Digraph::template NodeMap<Length> PotentialMap;

    /// The type of the path structures.

    typedef SimplePath<Digraph> Path;

  private: