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 |