Min_Cost_Matching.H File Reference

Minimum-cost matching in general undirected graphs. More...

#include <cstddef>
#include <limits>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <Blossom_Weighted.H>

Include dependency graph for Min_Cost_Matching.H:

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

Go to the source code of this file.

Classes
struct	Aleph::Min_Cost_Matching_Result< Cost_Type >
	Result of minimum-cost matching. More...
struct	Aleph::Min_Cost_Perfect_Matching_Result< Cost_Type >
	Result of minimum-cost perfect matching. More...
class	Aleph::min_cost_matching_detail::Negated_Cost_Accessor< Cost_Accessor >
class	Aleph::Compute_Minimum_Cost_General_Matching< GT, Cost, SA >
	Functor wrapper for minimum-cost general matching. More...
class	Aleph::Compute_Minimum_Cost_Perfect_General_Matching< GT, Cost, SA >
	Functor wrapper for minimum-cost perfect general matching. More...

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

Functions
template<typename T >
long long	Aleph::min_cost_matching_detail::to_ll_checked (T value)
template<class GT , class Cost = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>
Min_Cost_Matching_Result< long long >	Aleph::compute_minimum_cost_general_matching (const GT &g, DynDlist< typename GT::Arc * > &matching, Cost cost=Cost(), SA sa=SA(), const bool max_cardinality=false)
	Compute minimum-cost matching in a general undirected graph.
template<class GT , class Cost = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>
Min_Cost_Matching_Result< long long >	Aleph::blossom_minimum_cost_matching (const GT &g, DynDlist< typename GT::Arc * > &matching, Cost cost=Cost(), SA sa=SA(), const bool max_cardinality=false)
	Alias for compute_minimum_cost_general_matching().
template<class GT , class Cost = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>
Min_Cost_Perfect_Matching_Result< long long >	Aleph::compute_minimum_cost_perfect_general_matching (const GT &g, DynDlist< typename GT::Arc * > &matching, Cost cost=Cost(), SA sa=SA())
	Compute minimum-cost perfect matching in a general undirected graph.
template<class GT , class Cost = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>
Min_Cost_Perfect_Matching_Result< long long >	Aleph::blossom_minimum_cost_perfect_matching (const GT &g, DynDlist< typename GT::Arc * > &matching, Cost cost=Cost(), SA sa=SA())
	Alias for compute_minimum_cost_perfect_general_matching().

Detailed Description

Minimum-cost matching in general undirected graphs.

This header exposes a dedicated API for minimum-cost matching on non-bipartite graphs over Aleph graph backends.

Problem solved

Given an undirected graph \(G=(V,E)\) where each edge \(e \in E\) has a cost \(c(e)\), find a matching \(M\) that minimizes \(\sum_{e \in M} c(e)\).

Optional mode max_cardinality = true changes the objective to: 1) maximize matching cardinality, and 2) among those, minimize total cost.

It also provides a dedicated perfect-matching variant that reports feasibility and, when feasible, the minimum perfect-matching cost.

Highlights

• Works on List_Graph, List_SGraph, and Array_Graph
• Supports Aleph arc filters
• Uses integral costs (converted to long long with checks)
• Dedicated API names for minimum-cost intent

Complexity

• Time: \(O(V^3)\)
• Space: \(O(V + E)\)

See also

Blossom.H For maximum-cardinality matching in general graphs

Blossom_Weighted.H For maximum-weight matching

Definition in file Min_Cost_Matching.H.