RhodeCode

    using namespace _connectivity_bits;

    typedef DfsVisitor<Digraph> Visitor;

    Visitor visitor;

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

    dfs.init();

    dfs.addSource(source);

    dfs.start();

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

      if (!dfs.reached(it)) {

        return false;

      }

    }

    typedef ReverseDigraph<const Digraph> RDigraph;

    typedef typename RDigraph::NodeIt RNodeIt;

    RDigraph rdigraph(digraph);

    typedef DfsVisitor<Digraph> RVisitor;

    RVisitor rvisitor;

    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) {

      if (!dfs.reached(it)) {

        dfs.addSource(it);

        dfs.start();

      }

    }

    typedef typename Container::reverse_iterator RIterator;

    typedef ReverseDigraph<const Digraph> RDigraph;

    RDigraph rdigraph(digraph);

    typedef DfsVisitor<Digraph> RVisitor;

    RVisitor rvisitor;

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

    int compNum = 0;

    rdfs.init();

    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {

      if (!rdfs.reached(*it)) {

        rdfs.addSource(*it);

        rdfs.start();

        ++compNum;

  }

  /// \ingroup connectivity

  ///

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

  ///

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

  ///

  /// \param graph The graph. It must be directed and acyclic.

  /// \retval order A 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.

  ///

  /// \see checkedTopologicalSort

  /// \see dag

  template <typename Digraph, typename NodeMap>

  void topologicalSort(const Digraph& graph, NodeMap& order) {

    using namespace _connectivity_bits;

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

    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    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);

    }

    TopologicalSortVisitor<Digraph, NodeMap>

      visitor(order, countNodes(digraph));

    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >

      dfs(digraph, visitor);

    dfs.init();

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

      if (!dfs.reached(it)) {

        dfs.addSource(it);

        while (!dfs.emptyQueue()) {

           Arc arc = dfs.nextArc();

           Node target = digraph.target(arc);

           if (dfs.reached(target) && order[target] == -1) {

             return false;

           }

           dfs.processNextArc();

         }

      }

    }

    return true;

  }

  /// \ingroup connectivity

      while (arc != INVALID) {

        odd = _graph.target(arc);

        arc = (*_ear)[odd];

        even = _graph.target(arc);

        _matching->set(odd, arc);

        arc = (*_matching)[even];

        _matching->set(even, _graph.oppositeArc((*_matching)[odd]));

      }

      for (typename TreeSet::ItemIt it(*_tree_set, tree);

           it != INVALID; ++it) {

        if ((*_status)[it] == ODD) {

          _status->set(it, MATCHED);

        } else {

          int blossom = _blossom_set->find(it);

          for (typename BlossomSet::ItemIt jt(*_blossom_set, blossom);

               jt != INVALID; ++jt) {

            _status->set(jt, MATCHED);

          }

          _blossom_set->eraseClass(blossom);

        }

      }

      _tree_set->eraseClass(tree);

    }

  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);

      }

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

        if ((*_matching)[n] == INVALID) {

          for (OutArcIt a(_graph, n); a != INVALID ; ++a) {

            Node v = _graph.target(a);

            if ((*_matching)[v] == INVALID && v != n) {

              _matching->set(n, a);

              _status->set(n, MATCHED);

              _matching->set(v, _graph.oppositeArc(a));

              _status->set(v, MATCHED);

              break;

            }

          }

        }

      }

    }

    /// \brief Initialize the matching from a map containing.

    ///

    /// Initialize the matching from a \c bool valued \c Edge map. This

    /// map must have the property that there are no two incident edges

    /// with true value, ie. it contains a matching.

    /// \return %True if the map contains a matching.

    template <typename MatchingMap>

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_SUURBALLE_H

#define LEMON_SUURBALLE_H

///\ingroup shortest_path

///\file

///\brief An algorithm for finding arc-disjoint paths between two

/// nodes having minimum total length.

#include <vector>

#include <lemon/bin_heap.h>

#include <lemon/path.h>

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:

    /// \brief Special implementation of the Dijkstra algorithm

    /// for finding shortest paths in the residual network.

    ///

    /// \ref ResidualDijkstra is a special implementation of the

    /// \ref Dijkstra algorithm for finding shortest paths in the

    /// residual network of the digraph with respect to the reduced arc

    /// lengths and modifying the node potentials according to the

    /// distance of the nodes.

    class ResidualDijkstra

    {

      typedef typename Digraph::template NodeMap<int> HeapCrossRef;

      typedef BinHeap<Length, HeapCrossRef> Heap;

    private:

      // The digraph the algorithm runs on

      const Digraph &_graph;

      // The main maps

      const FlowMap &_flow;

      const LengthMap &_length;

      PotentialMap &_potential;