Aleph::blossom_weighted_detail::mwmatching::impl Namespace Reference

Classes
struct	AlternatingPath
	Represents a sequence of edges along an alternating path. More...
struct	Blossom
	Represents a blossom in the algorithm. More...
class	MatchingContext
	Encapsulates the complete state of the weighted matching algorithm. More...
class	MatchingVerifier
	Helper class to verify that an optimal solution has been found. More...
struct	NonTrivialBlossom
	Represents a non-trivial blossom (an odd cycle of sub-blossoms). More...
struct	Problem_Data
	Representation of the input graph for the internal solver. More...

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

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

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

Enumeration Type Documentation

BlossomLabel

enum Aleph::blossom_weighted_detail::mwmatching::impl::BlossomLabel

Top-level blossoms may be labeled "S" or "T" or unlabeled.

Enumerator
LABEL_NONE
LABEL_S
LABEL_T

Definition at line 128 of file blossom_weighted_mwmatching.H.

Function Documentation

check_input_graph()

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.

The graph may not have self-edges or multiple edges between the same pair of vertices. Edge weights must be within a valid range.

This function takes time O(m * log(m)).

Parameters

edges

Array of weighted edges defining the graph.

Exceptions

std::invalid_argument

If the input graph is not valid.

Definition at line 154 of file blossom_weighted_mwmatching.H.

References ah_invalid_argument_if, Aleph::all_unique(), Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::in_place_sort(), and Aleph::Array< T >::reserve().

Referenced by Aleph::blossom_weighted_detail::mwmatching::maximum_weight_matching().

flip_vertex_pair()

VertexPair Aleph::blossom_weighted_detail::mwmatching::impl::flip_vertex_pair ( const VertexPair &  vt )

inline

Return a pair of vertices in flipped order.

Definition at line 136 of file blossom_weighted_mwmatching.H.

Referenced by Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::expand_t_blossom().

for_vertices_in_blossom()

template<typename WeightType , typename Func >

void Aleph::blossom_weighted_detail::mwmatching::impl::for_vertices_in_blossom ( const Blossom< WeightType > *  blossom, Func  func  )

inline

Iterate over all base vertices contained within a blossom.

Definition at line 447 of file blossom_weighted_mwmatching.H.

References Aleph::Array< T >::append(), Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::base_vertex, Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::get_last(), Aleph::Array< T >::is_empty(), Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::nontrivial(), Aleph::Array< T >::remove_last(), and Aleph::blossom_weighted_detail::mwmatching::impl::NonTrivialBlossom< WeightType >::subblossoms.

Referenced by Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::assign_label_s(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >::check_blossom(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::expand_t_blossom(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::expand_unlabeled_blossom(), and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::make_blossom().

Variable Documentation

NO_VERTEX

constexpr VertexId Aleph::blossom_weighted_detail::mwmatching::impl::NO_VERTEX = std::numeric_limits<VertexId>::max()

constexpr

Value used to mark an invalid or undefined vertex.

Definition at line 124 of file blossom_weighted_mwmatching.H.

Referenced by Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::MatchingContext(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::assign_label_s(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::assign_label_t(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::augment_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::run_stage(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::trace_alternating_paths(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >::verify_vertex_duals(), and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >::verify_vertex_mate().