Namespaces
namespace	impl

Classes
struct	Edge
	Type representing a weighted edge. More...

Typedefs
using	VertexId = unsigned int
	Type representing the unique ID of a vertex.

using	VertexPair = std::pair< VertexId, VertexId >
	Type representing a pair of vertices.

Functions
template<typename WeightType >
Array< VertexPair >	maximum_weight_matching (const Array< Edge< WeightType > > &edges)
	Compute a maximum-weighted matching in a general undirected graph.

template<typename WeightType >
Array< Edge< WeightType > >	adjust_weights_for_maximum_cardinality_matching (const Array< Edge< WeightType > > &edges_in)
	Adjust edge weights to prioritize maximum cardinality matching.

Typedef Documentation

◆ VertexId

using Aleph::blossom_weighted_detail::mwmatching::VertexId = typedef unsigned int

Type representing the unique ID of a vertex.

Vertices must be indexed by consecutive non-negative integers starting from 0.

Definition at line 75 of file blossom_weighted_mwmatching.H.

◆ VertexPair

using Aleph::blossom_weighted_detail::mwmatching::VertexPair = typedef std::pair<VertexId, VertexId>

Type representing a pair of vertices.

Used to represent edges and matched pairs.

Definition at line 81 of file blossom_weighted_mwmatching.H.

Function Documentation

◆ adjust_weights_for_maximum_cardinality_matching()

template<typename WeightType >

Array< Edge< WeightType > > Aleph::blossom_weighted_detail::mwmatching::adjust_weights_for_maximum_cardinality_matching ( const Array< Edge< WeightType > > & edges_in )

Adjust edge weights to prioritize maximum cardinality matching.

This function modifies the weights of the input edges such that any maximum weight matching in the modified graph is also a maximum cardinality matching in the original graph. Among matchings of maximum cardinality, it will find one with maximum weight.

This is useful when the goal is to find the "best" maximum matching.

Template Parameters

WeightType Type used for edge weights.

Parameters

[in] edges_in Original weighted edges.

Returns: A new array of edges with adjusted weights.

Exceptions

std::invalid_argument If adjustment would cause numeric overflow.

Definition at line 2174 of file blossom_weighted_mwmatching.H.

References ah_invalid_argument_if, Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::get_first(), Aleph::Array< T >::is_empty(), and m.

Referenced by Aleph::compute_maximum_weight_general_matching().

◆ maximum_weight_matching()

template<typename WeightType >

Array< VertexPair > Aleph::blossom_weighted_detail::mwmatching::maximum_weight_matching ( const Array< Edge< WeightType > > & edges )

Compute a maximum-weighted matching in a general undirected graph.

This function implements the main Edmonds Blossom algorithm for weighted matching. It finds a set of edges such that no two edges share a vertex and the sum of weights is maximized.

The input graph must be provided as an array of weighted edges.

Vertices must be indexed 0 to \(n-1\).
Self-loops are not allowed.
Negative weight edges are ignored.

Template Parameters

WeightType Type used for edge weights (integral or floating-point).

Parameters

[in] edges Array of weighted edges.

Returns: Array of matched vertex pairs.

Exceptions

std::invalid_argument If the input graph is invalid (e.g. duplicate edges, self-loops).

Complexity

Time: \(O(n^3)\) where \(n\) is the number of vertices.
Space: \(O(n + m)\) where \(m\) is the number of edges.

Definition at line 2132 of file blossom_weighted_mwmatching.H.

References Aleph::Array< T >::append(), Aleph::blossom_weighted_detail::mwmatching::impl::check_input_graph(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::reserve(), and verify().

Referenced by Aleph::compute_maximum_weight_general_matching().

Namespaces

Classes