lemon/hao_orlin.h
changeset 561 6e0525ec5355
parent 440 88ed40ad0d4f
child 581 aa1804409f29
equal deleted inserted replaced
3:7af2f7b0dd96 4:6b37b4153c1b
    55   /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
    55   /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
    56   /// purpose of such algorithm is testing network reliability. For an
    56   /// purpose of such algorithm is testing network reliability. For an
    57   /// undirected graph you can run just the first phase of the
    57   /// undirected graph you can run just the first phase of the
    58   /// algorithm or you can use the algorithm of Nagamochi and Ibaraki
    58   /// algorithm or you can use the algorithm of Nagamochi and Ibaraki
    59   /// which solves the undirected problem in
    59   /// which solves the undirected problem in
    60   /// \f$ O(nm + n^2 \log(n)) \f$ time: it is implemented in the
    60   /// \f$ O(nm + n^2 \log n) \f$ time: it is implemented in the
    61   /// NagamochiIbaraki algorithm class.
    61   /// NagamochiIbaraki algorithm class.
    62   ///
    62   ///
    63   /// \param _Digraph is the graph type of the algorithm.
    63   /// \param GR The digraph class the algorithm runs on.
    64   /// \param _CapacityMap is an edge map of capacities which should
    64   /// \param CAP An arc map of capacities which can be any numreric type.
    65   /// be any numreric type. The default type is _Digraph::ArcMap<int>.
    65   /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    66   /// \param _Tolerance is the handler of the inexact computation. The
    66   /// \param TOL Tolerance class for handling inexact computations. The
    67   /// default type for this is Tolerance<CapacityMap::Value>.
    67   /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>".
    68 #ifdef DOXYGEN
    68 #ifdef DOXYGEN
    69   template <typename _Digraph, typename _CapacityMap, typename _Tolerance>
    69   template <typename GR, typename CAP, typename TOL>
    70 #else
    70 #else
    71   template <typename _Digraph,
    71   template <typename GR,
    72             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
    72             typename CAP = typename GR::template ArcMap<int>,
    73             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
    73             typename TOL = Tolerance<typename CAP::Value> >
    74 #endif
    74 #endif
    75   class HaoOrlin {
    75   class HaoOrlin {
    76   private:
    76   private:
    77 
    77 
    78     typedef _Digraph Digraph;
    78     typedef GR Digraph;
    79     typedef _CapacityMap CapacityMap;
    79     typedef CAP CapacityMap;
    80     typedef _Tolerance Tolerance;
    80     typedef TOL Tolerance;
    81 
    81 
    82     typedef typename CapacityMap::Value Value;
    82     typedef typename CapacityMap::Value Value;
    83 
    83 
    84     TEMPLATE_GRAPH_TYPEDEFS(Digraph);
    84     TEMPLATE_GRAPH_TYPEDEFS(Digraph);
    85 
    85 
   815 
   815 
   816   public:
   816   public:
   817 
   817 
   818     /// \name Execution control
   818     /// \name Execution control
   819     /// The simplest way to execute the algorithm is to use
   819     /// The simplest way to execute the algorithm is to use
   820     /// one of the member functions called \c run(...).
   820     /// one of the member functions called \ref run().
   821     /// \n
   821     /// \n
   822     /// If you need more control on the execution,
   822     /// If you need more control on the execution,
   823     /// first you must call \ref init(), then the \ref calculateIn() or
   823     /// first you must call \ref init(), then the \ref calculateIn() or
   824     /// \ref calculateOut() functions.
   824     /// \ref calculateOut() functions.
   825 
   825