r819:f964a00b9068
Fri, 16 Oct 2009 09:50:18
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -40,65 +40,65 @@ |
| 40 | 40 |
/// \tparam LEN The type of the length map. |
| 41 | 41 |
/// It must conform to the \ref concepts::Rea_data "Rea_data" concept. |
| 42 | 42 |
#ifdef DOXYGEN |
| 43 | 43 |
template <typename GR, typename LEN> |
| 44 | 44 |
#else |
| 45 | 45 |
template <typename GR, typename LEN, |
| 46 | 46 |
bool integer = std::numeric_limits<typename LEN::Value>::is_integer> |
| 47 | 47 |
#endif |
| 48 | 48 |
struct HartmannOrlinDefaultTraits |
| 49 | 49 |
{
|
| 50 | 50 |
/// The type of the digraph |
| 51 | 51 |
typedef GR Digraph; |
| 52 | 52 |
/// The type of the length map |
| 53 | 53 |
typedef LEN LengthMap; |
| 54 | 54 |
/// The type of the arc lengths |
| 55 | 55 |
typedef typename LengthMap::Value Value; |
| 56 | 56 |
|
| 57 | 57 |
/// \brief The large value type used for internal computations |
| 58 | 58 |
/// |
| 59 | 59 |
/// The large value type used for internal computations. |
| 60 | 60 |
/// It is \c long \c long if the \c Value type is integer, |
| 61 | 61 |
/// otherwise it is \c double. |
| 62 | 62 |
/// \c Value must be convertible to \c LargeValue. |
| 63 | 63 |
typedef double LargeValue; |
| 64 | 64 |
|
| 65 | 65 |
/// The tolerance type used for internal computations |
| 66 | 66 |
typedef lemon::Tolerance<LargeValue> Tolerance; |
| 67 | 67 |
|
| 68 | 68 |
/// \brief The path type of the found cycles |
| 69 | 69 |
/// |
| 70 | 70 |
/// The path type of the found cycles. |
| 71 | 71 |
/// It must conform to the \ref lemon::concepts::Path "Path" concept |
| 72 |
/// and it must have an \c |
|
| 72 |
/// and it must have an \c addFront() function. |
|
| 73 | 73 |
typedef lemon::Path<Digraph> Path; |
| 74 | 74 |
}; |
| 75 | 75 |
|
| 76 | 76 |
// Default traits class for integer value types |
| 77 | 77 |
template <typename GR, typename LEN> |
| 78 | 78 |
struct HartmannOrlinDefaultTraits<GR, LEN, true> |
| 79 | 79 |
{
|
| 80 | 80 |
typedef GR Digraph; |
| 81 | 81 |
typedef LEN LengthMap; |
| 82 | 82 |
typedef typename LengthMap::Value Value; |
| 83 | 83 |
#ifdef LEMON_HAVE_LONG_LONG |
| 84 | 84 |
typedef long long LargeValue; |
| 85 | 85 |
#else |
| 86 | 86 |
typedef long LargeValue; |
| 87 | 87 |
#endif |
| 88 | 88 |
typedef lemon::Tolerance<LargeValue> Tolerance; |
| 89 | 89 |
typedef lemon::Path<Digraph> Path; |
| 90 | 90 |
}; |
| 91 | 91 |
|
| 92 | 92 |
|
| 93 | 93 |
/// \addtogroup min_mean_cycle |
| 94 | 94 |
/// @{
|
| 95 | 95 |
|
| 96 | 96 |
/// \brief Implementation of the Hartmann-Orlin algorithm for finding |
| 97 | 97 |
/// a minimum mean cycle. |
| 98 | 98 |
/// |
| 99 | 99 |
/// This class implements the Hartmann-Orlin algorithm for finding |
| 100 | 100 |
/// a directed cycle of minimum mean length (cost) in a digraph |
| 101 | 101 |
/// \ref amo93networkflows, \ref dasdan98minmeancycle. |
| 102 | 102 |
/// It is an improved version of \ref Karp "Karp"'s original algorithm, |
| 103 | 103 |
/// it applies an efficient early termination scheme. |
| 104 | 104 |
/// It runs in time O(ne) and uses space O(n<sup>2</sup>+e). |
| ... | ... |
@@ -40,65 +40,65 @@ |
| 40 | 40 |
/// \tparam LEN The type of the length map. |
| 41 | 41 |
/// It must conform to the \ref concepts::ReadMap "ReadMap" concept. |
| 42 | 42 |
#ifdef DOXYGEN |
| 43 | 43 |
template <typename GR, typename LEN> |
| 44 | 44 |
#else |
| 45 | 45 |
template <typename GR, typename LEN, |
| 46 | 46 |
bool integer = std::numeric_limits<typename LEN::Value>::is_integer> |
| 47 | 47 |
#endif |
| 48 | 48 |
struct KarpDefaultTraits |
| 49 | 49 |
{
|
| 50 | 50 |
/// The type of the digraph |
| 51 | 51 |
typedef GR Digraph; |
| 52 | 52 |
/// The type of the length map |
| 53 | 53 |
typedef LEN LengthMap; |
| 54 | 54 |
/// The type of the arc lengths |
| 55 | 55 |
typedef typename LengthMap::Value Value; |
| 56 | 56 |
|
| 57 | 57 |
/// \brief The large value type used for internal computations |
| 58 | 58 |
/// |
| 59 | 59 |
/// The large value type used for internal computations. |
| 60 | 60 |
/// It is \c long \c long if the \c Value type is integer, |
| 61 | 61 |
/// otherwise it is \c double. |
| 62 | 62 |
/// \c Value must be convertible to \c LargeValue. |
| 63 | 63 |
typedef double LargeValue; |
| 64 | 64 |
|
| 65 | 65 |
/// The tolerance type used for internal computations |
| 66 | 66 |
typedef lemon::Tolerance<LargeValue> Tolerance; |
| 67 | 67 |
|
| 68 | 68 |
/// \brief The path type of the found cycles |
| 69 | 69 |
/// |
| 70 | 70 |
/// The path type of the found cycles. |
| 71 | 71 |
/// It must conform to the \ref lemon::concepts::Path "Path" concept |
| 72 |
/// and it must have an \c |
|
| 72 |
/// and it must have an \c addFront() function. |
|
| 73 | 73 |
typedef lemon::Path<Digraph> Path; |
| 74 | 74 |
}; |
| 75 | 75 |
|
| 76 | 76 |
// Default traits class for integer value types |
| 77 | 77 |
template <typename GR, typename LEN> |
| 78 | 78 |
struct KarpDefaultTraits<GR, LEN, true> |
| 79 | 79 |
{
|
| 80 | 80 |
typedef GR Digraph; |
| 81 | 81 |
typedef LEN LengthMap; |
| 82 | 82 |
typedef typename LengthMap::Value Value; |
| 83 | 83 |
#ifdef LEMON_HAVE_LONG_LONG |
| 84 | 84 |
typedef long long LargeValue; |
| 85 | 85 |
#else |
| 86 | 86 |
typedef long LargeValue; |
| 87 | 87 |
#endif |
| 88 | 88 |
typedef lemon::Tolerance<LargeValue> Tolerance; |
| 89 | 89 |
typedef lemon::Path<Digraph> Path; |
| 90 | 90 |
}; |
| 91 | 91 |
|
| 92 | 92 |
|
| 93 | 93 |
/// \addtogroup min_mean_cycle |
| 94 | 94 |
/// @{
|
| 95 | 95 |
|
| 96 | 96 |
/// \brief Implementation of Karp's algorithm for finding a minimum |
| 97 | 97 |
/// mean cycle. |
| 98 | 98 |
/// |
| 99 | 99 |
/// This class implements Karp's algorithm for finding a directed |
| 100 | 100 |
/// cycle of minimum mean length (cost) in a digraph |
| 101 | 101 |
/// \ref amo93networkflows, \ref dasdan98minmeancycle. |
| 102 | 102 |
/// It runs in time O(ne) and uses space O(n<sup>2</sup>+e). |
| 103 | 103 |
/// |
| 104 | 104 |
/// \tparam GR The type of the digraph the algorithm runs on. |
0 comments (0 inline)