Min_Mean_Cycle.H File Reference

Minimum mean cycle in directed graphs (Karp algorithm). More...

#include <ah-graph-concepts.H>
#include <cmath>
#include <cstddef>
#include <limits>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <shortest_path_common.H>
#include <htlist.H>
#include <tpl_array.H>
#include <tpl_dynMapTree.H>

Include dependency graph for Min_Mean_Cycle.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Min_Mean_Cycle_Result< GT, Cost_Type >
	Result of minimum mean cycle computation. More...
struct	Aleph::Min_Mean_Cycle_Value_Result
	Lightweight minimum-mean-cycle value result. More...
struct	Aleph::min_mean_cycle_detail::Incoming_Arc< GT, Cost_Type >
class	Aleph::Karp_Minimum_Mean_Cycle< GT, Distance, SA >
	Functor wrapper for Karp minimum mean cycle. More...
class	Aleph::Karp_Minimum_Mean_Cycle_Value< GT, Distance, SA >
	Functor wrapper for value-only minimum mean cycle. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::min_mean_cycle_detail

Functions
template<AlephGraph GT, ArcDistance< GT > Distance, ArcFilter< GT > SA>
void	Aleph::min_mean_cycle_detail::validate_weights (const GT &g, Distance distance, SA sa)
template<typename Cost_Type >
void	Aleph::min_mean_cycle_detail::validate_finite_accumulator (const Cost_Type &value, const char *context)
template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
Min_Mean_Cycle_Result< GT, typename Distance::Distance_Type >	Aleph::karp_minimum_mean_cycle (const GT &g, Distance distance=Distance(), SA sa=SA())
	Compute minimum mean cycle by Karp's algorithm.
template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
Min_Mean_Cycle_Value_Result	Aleph::karp_minimum_mean_cycle_value (const GT &g, Distance distance=Distance(), SA sa=SA())
	Compute only the minimum mean value (without witness walk).
template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
Min_Mean_Cycle_Value_Result	Aleph::minimum_mean_cycle_value (const GT &g, Distance distance=Distance(), SA sa=SA())
	Alias for karp_minimum_mean_cycle_value().
template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
Min_Mean_Cycle_Result< GT, typename Distance::Distance_Type >	Aleph::minimum_mean_cycle (const GT &g, Distance distance=Distance(), SA sa=SA())
	Alias for karp_minimum_mean_cycle().

Detailed Description

Minimum mean cycle in directed graphs (Karp algorithm).

This header provides a dedicated API to compute the minimum cycle mean in a directed weighted graph using Karp's dynamic programming algorithm.

Problem solved

Given a directed graph \(G=(V,E)\)with arc costs \(w(e)\), find the cycle \(C\)minimizing the average weight:

\[ \mu^* = \min_C \frac{w(C)}{|C|} \]

Highlights

• Works with Aleph directed graph backends (List_Digraph, Array_Graph, ...)
• Supports arc filters (SA) and custom distance accessors
• Accepts negative and positive weights (only finite arithmetic costs)
• Returns minimum mean and a cycle witness when available
• Includes value-only API when only the optimal mean is required

Complexity

• Time: \(O(VE)\)
• Space: \(O(V^2)\)

Author

Leandro Rabindranath León

Definition in file Min_Mean_Cycle.H.