RhodeCode

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// The default type is \ref ListDigraph.

  /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies

  /// the lengths of the arcs. The default map type is

  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template <typename GR=ListDigraph,

            typename LEN=typename GR::template ArcMap<int>,

            typename TR=BellmanFordDefaultTraits<GR,LEN> >

  /// \ref BellmanFord "Bellman-Ford" algorithm.

  /// It does not have own \ref run() method, it uses the

  /// functions and features of the plain \ref BellmanFord.

  ///

  /// This class should only be used through the \ref bellmanFord()

  /// function, which makes it easier to use the algorithm.

  template<class TR>

  class BellmanFordWizard : public TR {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

  ///There is also a \ref bfs() "function-type interface" for the BFS

  ///algorithm, which is convenient in the simplier cases and it can be

  ///used easier.

  ///

  ///\tparam GR The type of the digraph the algorithm runs on.

  ///The default type is \ref ListDigraph.

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

#else

  template <typename GR=ListDigraph,

            typename TR=BfsDefaultTraits<GR> >

  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.

  /// It does not have own \ref run(Node) "run()" method, it uses the

  /// functions and features of the plain \ref Bfs.

  ///

  /// This class should only be used through the \ref bfs() function,

  /// which makes it easier to use the algorithm.

  template<class TR>

  class BfsWizard : public TR

  {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

  /// The value of GR is not used directly by \ref BfsVisit,

  /// it is only passed to \ref BfsVisitDefaultTraits.

  /// \tparam VS The Visitor type that is used by the algorithm.

  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which

  /// does not observe the BFS events. If you want to observe the BFS

  /// events, you should implement your own visitor class.

#ifdef DOXYGEN

  template <typename GR, typename VS, typename TR>

#else

  template <typename GR = ListDigraph,

            typename VS = BfsVisitor<GR>,

            typename TR = BfsVisitDefaultTraits<GR> >

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

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

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// \tparam C The number type used for costs and potentials in the

  ///

  /// \warning Both number types must be signed and all input data must

  /// be integer.

  /// \warning This algorithm does not support negative costs for such

  /// arcs that have infinite upper bound.

#ifdef DOXYGEN

     \tparam LM The type of the lower bound map. The default

     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

     \tparam UM The type of the upper bound (capacity) map.

     The default map type is \c LM.

     \tparam SM The type of the supply map. The default map type is

     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".

  */

#ifdef DOXYGEN

template< typename GR,

          typename LM,

          typename UM,

          typename SM,

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

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

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// \tparam C The number type used for costs and potentials in the

  ///

  /// \warning Both number types must be signed and all input data must

  /// be integer.

  /// \warning This algorithm does not support negative costs for such

  /// arcs that have infinite upper bound.

  ///

    /// The type of the arc costs

    typedef typename TR::Cost Cost;

    /// \brief The large cost type

    ///

    /// The large cost type used for internal computations.

    /// otherwise it is \c double.

    typedef typename TR::LargeCost LargeCost;

    /// The \ref CostScalingDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  ///There is also a \ref dfs() "function-type interface" for the DFS

  ///algorithm, which is convenient in the simplier cases and it can be

  ///used easier.

  ///

  ///\tparam GR The type of the digraph the algorithm runs on.

  ///The default type is \ref ListDigraph.

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

#else

  template <typename GR=ListDigraph,

            typename TR=DfsDefaultTraits<GR> >

  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.

  /// It does not have own \ref run(Node) "run()" method, it uses the

  /// functions and features of the plain \ref Dfs.

  ///

  /// This class should only be used through the \ref dfs() function,

  /// which makes it easier to use the algorithm.

  template<class TR>

  class DfsWizard : public TR

  {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

  /// The value of GR is not used directly by \ref DfsVisit,

  /// it is only passed to \ref DfsVisitDefaultTraits.

  /// \tparam VS The Visitor type that is used by the algorithm.

  /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which

  /// does not observe the DFS events. If you want to observe the DFS

  /// events, you should implement your own visitor class.

#ifdef DOXYGEN

  template <typename GR, typename VS, typename TR>

#else

  template <typename GR = ListDigraph,

            typename VS = DfsVisitor<GR>,

            typename TR = DfsVisitDefaultTraits<GR> >

  ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies

  ///the lengths of the arcs.

  ///It is read once for each arc, so the map may involve in

  ///relatively time consuming process to compute the arc lengths if

  ///it is necessary. The default map type is \ref

  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template <typename GR=ListDigraph,

            typename LEN=typename GR::template ArcMap<int>,

            typename TR=DijkstraDefaultTraits<GR,LEN> >

  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.

  /// It does not have own \ref run(Node) "run()" method, it uses the

  /// functions and features of the plain \ref Dijkstra.

  ///

  /// This class should only be used through the \ref dijkstra() function,

  /// which makes it easier to use the algorithm.

  template<class TR>

  class DijkstraWizard : public TR

  {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

  /// it applies an efficient early termination scheme.

  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam LEN The type of the length map. The default

  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

             typename LEN = typename GR::template ArcMap<int>,

             typename TR = HartmannOrlinDefaultTraits<GR, LEN> >

    /// The type of the arc lengths

    typedef typename TR::Value Value;

    /// \brief The large value type

    ///

    /// The large value type used for internal computations.

    /// otherwise it is \c double.

    typedef typename TR::LargeValue LargeValue;

    /// The tolerance type

    typedef typename TR::Tolerance Tolerance;

  /// minimum mean cycle problem, though the best known theoretical

  /// bound on its running time is exponential.

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam LEN The type of the length map. The default

  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

             typename LEN = typename GR::template ArcMap<int>,

             typename TR = HowardDefaultTraits<GR, LEN> >

    /// The type of the arc lengths

    typedef typename TR::Value Value;

    /// \brief The large value type

    ///

    /// The large value type used for internal computations.

    /// otherwise it is \c double.

    typedef typename TR::LargeValue LargeValue;

    /// The tolerance type

    typedef typename TR::Tolerance Tolerance;

  /// \ref amo93networkflows, \ref dasdan98minmeancycle.

  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam LEN The type of the length map. The default

  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template < typename GR,

             typename LEN = typename GR::template ArcMap<int>,

             typename TR = KarpDefaultTraits<GR, LEN> >

    /// The type of the arc lengths

    typedef typename TR::Value Value;

    /// \brief The large value type

    ///

    /// The large value type used for internal computations.

    /// otherwise it is \c double.

    typedef typename TR::LargeValue LargeValue;

    /// The tolerance type

    typedef typename TR::Tolerance Tolerance;

  /// \param GR The digraph type the algorithm runs on.

  /// \param CM A read-only arc map storing the costs of the

  /// arcs. It is read once for each arc, so the map may involve in

  /// relatively time consuming process to compute the arc costs if

  /// it is necessary. The default map type is \ref

  /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".

  /// "MinCostArborescenceDefaultTraits<GR, CM>".

#ifndef DOXYGEN

  template <typename GR,

            typename CM = typename GR::template ArcMap<int>,

            typename TR =

              MinCostArborescenceDefaultTraits<GR, CM> >

#else

#endif

  class MinCostArborescence {

  public:

    /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" 

    /// of the algorithm. 

  /// \warning This implementation cannot handle infinite or very large

  /// capacities (e.g. the maximum value of \c CAP::Value).

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam CAP The type of the capacity map. The default map

  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename CAP, typename TR>

#else

  template <typename GR,

            typename CAP = typename GR::template ArcMap<int>,

            typename TR = PreflowDefaultTraits<GR, CAP> >