blossom_weighted_mwmatching.H File Reference

Internal weighted matching core used by Blossom_Weighted.H. More...

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <limits>
#include <tuple>
#include <utility>
#include <ah-errors.H>
#include <ahFunctional.H>
#include <ahSort.H>
#include <tpl_array.H>
#include <tpl_agraph.H>
#include <tpl_dynDlist.H>
#include <tpl_dynListQueue.H>
#include <tpl_dynListStack.H>

Include dependency graph for blossom_weighted_mwmatching.H:

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

Go to the source code of this file.

Classes
struct	Aleph::blossom_weighted_detail::mwmatching::Edge< WeightType >
	Type representing a weighted edge. More...
struct	Aleph::blossom_weighted_detail::mwmatching::impl::Problem_Data< WeightType >
	Representation of the input graph for the internal solver. More...
struct	Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >
	Represents a blossom in the algorithm. More...
struct	Aleph::blossom_weighted_detail::mwmatching::impl::NonTrivialBlossom< WeightType >
	Represents a non-trivial blossom (an odd cycle of sub-blossoms). More...
struct	Aleph::blossom_weighted_detail::mwmatching::impl::NonTrivialBlossom< WeightType >::SubBlossom
struct	Aleph::blossom_weighted_detail::mwmatching::impl::AlternatingPath
	Represents a sequence of edges along an alternating path. More...
class	Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >
	Encapsulates the complete state of the weighted matching algorithm. More...
struct	Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::DeltaStep
	A candidate step for dual variable modification. More...
class	Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >
	Helper class to verify that an optimal solution has been found. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::blossom_weighted_detail
namespace	Aleph::blossom_weighted_detail::mwmatching
namespace	Aleph::blossom_weighted_detail::mwmatching::impl

Typedefs
using	Aleph::blossom_weighted_detail::mwmatching::VertexId = unsigned int
	Type representing the unique ID of a vertex.
using	Aleph::blossom_weighted_detail::mwmatching::VertexPair = std::pair< VertexId, VertexId >
	Type representing a pair of vertices.

Enumerations
enum	Aleph::blossom_weighted_detail::mwmatching::impl::BlossomLabel { Aleph::blossom_weighted_detail::mwmatching::impl::LABEL_NONE = 0 , Aleph::blossom_weighted_detail::mwmatching::impl::LABEL_S = 1 , Aleph::blossom_weighted_detail::mwmatching::impl::LABEL_T = 2 }
	Top-level blossoms may be labeled "S" or "T" or unlabeled. More...

Functions
VertexPair	Aleph::blossom_weighted_detail::mwmatching::impl::flip_vertex_pair (const VertexPair &vt)
	Return a pair of vertices in flipped order.
template<typename WeightType >
void	Aleph::blossom_weighted_detail::mwmatching::impl::check_input_graph (const Array< Edge< WeightType > > &edges)
	Check that the input is a valid graph.
template<typename WeightType , typename Func >
void	Aleph::blossom_weighted_detail::mwmatching::impl::for_vertices_in_blossom (const Blossom< WeightType > *blossom, Func func)
	Iterate over all base vertices contained within a blossom.
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.
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.

Variables
constexpr VertexId	Aleph::blossom_weighted_detail::mwmatching::impl::NO_VERTEX = std::numeric_limits<VertexId>::max()
	Value used to mark an invalid or undefined vertex.

Detailed Description

Internal weighted matching core used by Blossom_Weighted.H.

This file contains an adapted version of the MIT-licensed reference implementation by Joris van Rantwijk (repository: https://git.jorisvr.nl/joris/maximum-weight-matching).

Adaptations for Aleph include:

• Namespace nesting under Aleph internals.
• Error reporting via Aleph ah-errors macros.
• Header/style integration.

Definition in file blossom_weighted_mwmatching.H.