Helper class to verify that an optimal solution has been found. More...

#include <blossom_weighted_mwmatching.H>

Collaboration diagram for Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >:

Public Member Functions
	MatchingVerifier (const MatchingContext< WeightType > &ctx)

bool	verify ()
	Verify that the optimum solution has been found.

Private Types
using	EdgeT = Edge< WeightType >

using	BlossomT = Blossom< WeightType >

using	NonTrivialBlossomT = NonTrivialBlossom< WeightType >

Private Member Functions
std::size_t	edge_index (const EdgeT *edge)
	Convert edge pointer to its index in the array "edges".

bool	verify_vertex_mate ()
	Check that the array "vertex_mate" is consistent.

bool	verify_vertex_duals ()
	Check that vertex dual variables are non-negative, and all unmatched vertices have zero dual.

bool	verify_blossom_duals ()
	Check that blossom dual variables are non-negative.

bool	check_blossom (const NonTrivialBlossomT *blossom)
	Helper function for verifying the solution.

bool	verify_blossoms_and_calc_edge_duals ()
	Check that all blossoms are full.

bool	verify_edge_slack ()
	Check that all edges have non-negative slack, and check that all matched edges have zero slack.

Static Private Member Functions
static bool	checked_add (WeightType &result, WeightType a, WeightType b)

Private Attributes
const MatchingContext< WeightType > &	ctx
	Reference to the MatchingContext instance.

const Problem_Data< WeightType > &	graph
	Reference to the input graph.

Array< WeightType >	edge_duals
	For each edge, the sum of duals of its incident vertices and duals of all blossoms that contain the edge.

Detailed Description

template<typename WeightType>
class Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >

Helper class to verify that an optimal solution has been found.

Definition at line 1768 of file blossom_weighted_mwmatching.H.

Member Typedef Documentation

◆ BlossomT

template<typename WeightType >

using Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >::BlossomT = Blossom<WeightType>

private

Definition at line 1799 of file blossom_weighted_mwmatching.H.

◆ EdgeT

template<typename WeightType >

using Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >::EdgeT = Edge<WeightType>

private

Definition at line 1798 of file blossom_weighted_mwmatching.H.

◆ NonTrivialBlossomT

template<typename WeightType >

using Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >::NonTrivialBlossomT = NonTrivialBlossom<WeightType>

private

Definition at line 1800 of file blossom_weighted_mwmatching.H.

Constructor & Destructor Documentation

◆ MatchingVerifier()

template<typename WeightType >

Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >::MatchingVerifier ( const MatchingContext< WeightType > & ctx )

inline

Definition at line 1771 of file blossom_weighted_mwmatching.H.

References Aleph::Array< T >::append(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >::ctx, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >::edge_duals, and Aleph::Array< T >::reserve().

Member Function Documentation

◆ check_blossom()

template<typename WeightType >

bool Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >::check_blossom ( const NonTrivialBlossomT * blossom )

inlineprivate

Helper function for verifying the solution.

Descend down the blossom tree to find edges that are contained in blossoms.

On the way down, keep track of the sum of dual variables of containing blossoms. Add blossom duals to edges that are contained inside blossoms.

On the way up, keep track of the total number of matched edges in subblossoms. Check that all blossoms with non-zero dual variables are "full".

Returns: True if successful; false if a blossom with non-zero dual is not full; false if blossom dual calculations cause numeric overflow.

Definition at line 1885 of file blossom_weighted_mwmatching.H.

Referenced by Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >::verify_blossoms_and_calc_edge_duals().

◆ checked_add()

template<typename WeightType >

static bool Aleph::blossom_weighted_detail::mwmatching::impl::MatchingVerifier< WeightType >::checked_add	(	WeightType &	result,
		WeightType	a,
		WeightType	b
	)