Encapsulates the complete state of the weighted matching algorithm. More...

#include <blossom_weighted_mwmatching.H>

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

Classes
struct	DeltaStep
	A candidate step for dual variable modification. More...

Public Types
using	EdgeT = Edge< WeightType >

using	BlossomT = Blossom< WeightType >

using	NonTrivialBlossomT = NonTrivialBlossom< WeightType >

Public Member Functions
	MatchingContext (const Array< EdgeT > &edges_in)
	Initialize context from an edge array.

	MatchingContext (const MatchingContext &)=delete

MatchingContext &	operator= (const MatchingContext &)=delete

WeightType	edge_slack (const EdgeT &edge) const
	Calculate edge slack.

void	lset_reset ()
	Reset least-slack edge tracking.

void	lset_add_vertex_edge (VertexId y, const EdgeT *edge, WeightType slack)
	Add edge "e" from an S-vertex to unlabeled vertex or T-vertex "y".

std::pair< const EdgeT *, WeightType >	lset_get_best_vertex_edge ()
	Return the index and slack of the least-slack edge between any S-vertex and unlabeled vertex.

void	lset_add_blossom_edge (BlossomT blossom, const EdgeT edge, WeightType slack)
	Add edge "e" between the specified S-blossom and another S-blossom.

void	lset_merge_blossoms (NonTrivialBlossomT *blossom)
	Update least-slack edge tracking after merging sub-blossoms into a new S-blossom.

std::pair< const EdgeT *, WeightType >	lset_get_best_blossom_edge ()
	Return the index and slack of the least-slack edge between any pair of top-level S-blossoms.

AlternatingPath	trace_alternating_paths (VertexId x, VertexId y)
	Trace back through the alternating trees from vertices "x" and "y".

void	make_blossom (const AlternatingPath &path)
	Create a new blossom from an alternating cycle.

void	erase_nontrivial_blossom (NonTrivialBlossomT *blossom)
	Erase the specified non-trivial blossom.

void	expand_t_blossom (NonTrivialBlossomT *blossom)
	Expand the specified T-blossom.

void	expand_unlabeled_blossom (NonTrivialBlossomT *blossom)
	Expand the specified unlabeled blossom.

void	augment_blossom_rec (NonTrivialBlossomT blossom, BlossomT entry, DynListStack< std::pair< NonTrivialBlossomT , BlossomT > > &rec_stack)
	Augment along an alternating path through the specified blossom, from sub-blossom "entry" to the base vertex of the blossom.

void	augment_blossom (NonTrivialBlossomT blossom, BlossomT entry)
	Augment along an alternating path through the specified blossom, from sub-blossom "entry" to the base vertex of the blossom.

void	augment_matching (const AlternatingPath &path)
	Augment the matching through the specified augmenting path.

void	assign_label_s (VertexId x)
	Assign label S to the unlabeled blossom that contains vertex "x".

void	assign_label_t (VertexId x, VertexId y)
	Assign label T to the unlabeled blossom that contains vertex "y".

bool	add_s_to_s_edge (VertexId x, VertexId y)
	Add the edge between S-vertices "x" and "y".

bool	substage_scan ()
	Scan queued S-vertices to expand the alternating trees.

DeltaStep	substage_calc_dual_delta ()
	Calculate a delta step in the dual LPP problem.

void	substage_apply_delta_step (WeightType delta)
	Apply a delta step to the dual LPP variables.

void	reset_stage ()
	Reset data which are only valid during a stage.

bool	run_stage ()
	Run one stage of the matching algorithm.

void	run ()
	Run the matching algorithm.

Static Public Member Functions
static void	lset_new_blossom (BlossomT *blossom)
	Start tracking edges for a new S-blossom.

Public Attributes
const Problem_Data< WeightType >	graph
	Internal graph representation.

Array< VertexId >	vertex_mate
	The current mate of each vertex, or NO_VERTEX.

Array< BlossomT >	trivial_blossom
	All trivial (single vertex) blossoms.

DynDlist< NonTrivialBlossomT >	nontrivial_blossom
	Currently active non-trivial blossoms.

Array< BlossomT * >	vertex_top_blossom
	Maps each vertex to its highest-level containing blossom.

Array< WeightType >	vertex_dual
	Dual variable \(y_i\)for each vertex.

Array< const EdgeT * >	vertex_best_edge

DynListQueue< VertexId >	queue

Array< bool >	vertex_marker

Array< VertexId >	marked_vertex

Static Public Attributes
static constexpr WeightType	weight_factor
	Integer scaling factor for weight calculations.

Detailed Description

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

Encapsulates the complete state of the weighted matching algorithm.

Includes dual variables, blossom hierarchy, and the current matching state.

Definition at line 498 of file blossom_weighted_mwmatching.H.

Member Typedef Documentation

◆ BlossomT

template<typename WeightType >

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

Definition at line 502 of file blossom_weighted_mwmatching.H.

◆ EdgeT

template<typename WeightType >

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

Definition at line 501 of file blossom_weighted_mwmatching.H.

◆ NonTrivialBlossomT

template<typename WeightType >

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

Definition at line 503 of file blossom_weighted_mwmatching.H.

Constructor & Destructor Documentation

◆ MatchingContext() [1/2]

template<typename WeightType >

Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::MatchingContext ( const Array< EdgeT > & edges_in )

inlineexplicit

Initialize context from an edge array.

Definition at line 556 of file blossom_weighted_mwmatching.H.

◆ MatchingContext() [2/2]

template<typename WeightType >

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

delete

Member Function Documentation

◆ add_s_to_s_edge()

template<typename WeightType >

bool Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::add_s_to_s_edge	(	VertexId	x,
		VertexId	y
	)

inline

Add the edge between S-vertices "x" and "y".

If the edge connects blossoms that are part of the same alternating tree, this function creates a new S-blossom and returns false.

If the edge connects two different alternating trees, an augmenting path has been discovered. In this case the matching is augmented.

Returns: True if the matching was augmented; otherwise false.

Definition at line 1431 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::augment_matching(), Aleph::blossom_maximum_cardinality_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::AlternatingPath::edges, Aleph::DynDlist< T >::get_first(), Aleph::DynDlist< T >::get_last(), Aleph::blossom_weighted_detail::mwmatching::impl::LABEL_S, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::make_blossom(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::trace_alternating_paths(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_top_blossom, and y.

Referenced by Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::run_stage(), and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::substage_scan().

◆ assign_label_s()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::assign_label_s ( VertexId x )

inline

Assign label S to the unlabeled blossom that contains vertex "x".

If vertex "x" is matched, it becomes attached to the alternating tree via its matched edge. If vertex "x" is unmatched, it becomes the root of an alternating tree.

All vertices in the newly labeled blossom are added to the scan queue.

Precondition: "x" is an unlabeled vertex, either unmatched or matched to a T-vertex via a tight edge.

Definition at line 1342 of file blossom_weighted_mwmatching.H.

Referenced by Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::assign_label_t(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::expand_t_blossom(), and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::run_stage().

◆ assign_label_t()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::assign_label_t	(	VertexId	x,
		VertexId	y
	)

inline

Assign label T to the unlabeled blossom that contains vertex "y".

Attach it to the alternating tree via edge (x, y). Then immediately assign label S to the mate of vertex "y".

Note that this function may expand blossoms that contain vertex "y".

Precondition: "x" is an S-vertex.; "y" is an unlabeled, matched vertex.; There is a tight edge between vertices "x" and "y".

Definition at line 1391 of file blossom_weighted_mwmatching.H.

Referenced by Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::run_stage(), and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::substage_scan().

◆ augment_blossom()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::augment_blossom	(	NonTrivialBlossomT *	blossom,
		BlossomT *	entry
	)

inline

Augment along an alternating path through the specified blossom, from sub-blossom "entry" to the base vertex of the blossom.

Recursively handle sub-blossoms as needed.

This function takes time O(n).

Definition at line 1249 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::augment_blossom_rec(), Aleph::blossom_maximum_cardinality_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::parent, and Aleph::DynListStack< T >::put().

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

◆ augment_blossom_rec()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::augment_blossom_rec	(	NonTrivialBlossomT *	blossom,
		BlossomT *	entry,
		DynListStack< std::pair< NonTrivialBlossomT , BlossomT > > &	rec_stack
	)

inline

Augment along an alternating path through the specified blossom, from sub-blossom "entry" to the base vertex of the blossom.

Modify the blossom to reflect that sub-blossom "entry" contains the base vertex after augmenting.

Definition at line 1170 of file blossom_weighted_mwmatching.H.

References Aleph::and, Aleph::DynDlist< T >::append(), Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::base_vertex, Aleph::blossom_maximum_cardinality_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::NonTrivialBlossom< WeightType >::find_subblossom_pos(), k, Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::nontrivial(), Aleph::Array< T >::reserve(), Aleph::blossom_weighted_detail::mwmatching::impl::NonTrivialBlossom< WeightType >::subblossoms, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::trivial_blossom, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_mate, and y.

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

◆ augment_matching()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::augment_matching ( const AlternatingPath & path )

inline

Augment the matching through the specified augmenting path.

This function takes time O(n).

Definition at line 1287 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::augment_blossom(), StlAlephIterator< SetName >::begin(), Aleph::blossom_maximum_cardinality_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::AlternatingPath::edges, StlAlephIterator< SetName >::end(), Aleph::DynDlist< T >::get_first(), Aleph::DynDlist< T >::get_last(), Aleph::blossom_weighted_detail::mwmatching::impl::NO_VERTEX, Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::nontrivial(), Aleph::DynDlist< T >::size(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::trivial_blossom, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_mate, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_top_blossom, and y.

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

◆ edge_slack()

template<typename WeightType >

WeightType Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::edge_slack ( const EdgeT & edge ) const

inline

Calculate edge slack.

Definition at line 605 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_dual, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_top_blossom, Aleph::blossom_weighted_detail::mwmatching::Edge< WeightType >::vt, Aleph::blossom_weighted_detail::mwmatching::Edge< WeightType >::weight, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::weight_factor, and y.

Referenced by Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_add_blossom_edge(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_add_vertex_edge(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_get_best_blossom_edge(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_get_best_vertex_edge(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_merge_blossoms(), and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::substage_scan().

◆ erase_nontrivial_blossom()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::erase_nontrivial_blossom ( NonTrivialBlossomT * blossom )

inline

Erase the specified non-trivial blossom.

Definition at line 1040 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::nontrivial_blossom.

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

◆ expand_t_blossom()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::expand_t_blossom ( NonTrivialBlossomT * blossom )

inline

Expand the specified T-blossom.

This function takes time O(n).

Definition at line 1056 of file blossom_weighted_mwmatching.H.

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

◆ expand_unlabeled_blossom()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::expand_unlabeled_blossom ( NonTrivialBlossomT * blossom )

inline

Expand the specified unlabeled blossom.

This function takes time O(n).

Definition at line 1138 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::erase_nontrivial_blossom(), Aleph::blossom_weighted_detail::mwmatching::impl::for_vertices_in_blossom(), Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::label, Aleph::blossom_weighted_detail::mwmatching::impl::LABEL_NONE, Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::parent, Aleph::blossom_weighted_detail::mwmatching::impl::NonTrivialBlossom< WeightType >::subblossoms, and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_top_blossom.

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

◆ lset_add_blossom_edge()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_add_blossom_edge	(	BlossomT *	blossom,
		const EdgeT *	edge,
		WeightType	slack
	)

inline

Add edge "e" between the specified S-blossom and another S-blossom.

This function takes time O(1) per call. This function is called O(m) times per stage.

Definition at line 724 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::best_edge, Aleph::blossom_maximum_cardinality_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::edge_slack(), and Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::nontrivial().

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

◆ lset_add_vertex_edge()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_add_vertex_edge	(	VertexId	y,
		const EdgeT *	edge,
		WeightType	slack
	)

inline

Add edge "e" from an S-vertex to unlabeled vertex or T-vertex "y".

This function takes time O(1) per call. This function is called O(m) times per stage.

Definition at line 670 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::edge_slack(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_best_edge, and y.

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

◆ lset_get_best_blossom_edge()

template<typename WeightType >

std::pair< const EdgeT *, WeightType > Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_get_best_blossom_edge ( )

inline

Return the index and slack of the least-slack edge between any pair of top-level S-blossoms.

This function takes time O(n) per call. This function takes total time O(n**2) per stage.

Returns: Pair (edge, slack) if there is a least-slack edge, or (nullptr, 0) if there is no suitable edge.

Definition at line 843 of file blossom_weighted_mwmatching.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::edge_slack(), Aleph::blossom_weighted_detail::mwmatching::impl::LABEL_S, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::nontrivial_blossom, and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::trivial_blossom.

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

◆ lset_get_best_vertex_edge()

template<typename WeightType >

std::pair< const EdgeT *, WeightType > Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_get_best_vertex_edge ( )

inline

Return the index and slack of the least-slack edge between any S-vertex and unlabeled vertex.

This function takes time O(n) per call. This function takes total time O(n**2) per stage.

Returns: Pair (edge, slack) if there is a least-slack edge, or (nullptr, 0) if there is no suitable edge.

Definition at line 687 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::edge_slack(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::graph, Aleph::blossom_weighted_detail::mwmatching::impl::LABEL_NONE, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_best_edge, and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_top_blossom.

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

◆ lset_merge_blossoms()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_merge_blossoms ( NonTrivialBlossomT * blossom )

inline

Update least-slack edge tracking after merging sub-blossoms into a new S-blossom.

This function takes total time O(n**2) per stage.

Definition at line 742 of file blossom_weighted_mwmatching.H.

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

◆ lset_new_blossom()

template<typename WeightType >

static void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_new_blossom ( BlossomT * blossom )

inlinestatic

Start tracking edges for a new S-blossom.

Definition at line 711 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_maximum_cardinality_matching().

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

◆ lset_reset()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_reset ( )

inline

Reset least-slack edge tracking.

This function takes time O(n + m).

Definition at line 649 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::graph, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::nontrivial_blossom, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::trivial_blossom, and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_best_edge.

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

◆ make_blossom()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::make_blossom ( const AlternatingPath & path )

inline

Create a new blossom from an alternating cycle.

Assign label S to the new blossom. Relabel all T-sub-blossoms as S and add their vertices to the queue.

This function takes total time O(n**2) per stage.

Definition at line 983 of file blossom_weighted_mwmatching.H.

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

◆ operator=()

template<typename WeightType >

MatchingContext & Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::operator= ( const MatchingContext< WeightType > & )

delete

◆ reset_stage()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::reset_stage ( )

inline

Reset data which are only valid during a stage.

Mark all blossoms as unlabeled, clear the queue, reset least-slack edge tracking.

Definition at line 1644 of file blossom_weighted_mwmatching.H.

References Aleph::DynListQueue< T >::clear(), Aleph::blossom_weighted_detail::mwmatching::impl::LABEL_NONE, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_reset(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::nontrivial_blossom, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::queue, and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::trivial_blossom.

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

◆ run()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::run ( )

inline

Run the matching algorithm.

Definition at line 1750 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::run_stage().

◆ run_stage()

template<typename WeightType >

bool Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::run_stage ( )

inline

Run one stage of the matching algorithm.

The stage searches a maximum-weight augmenting path. If this path is found, it is used to augment the matching, thereby increasing the number of matched edges by 1. If no such path is found, the matching must already be optimal.

This function takes time O(n**2).

Returns: True if the matching was successfully augmented; false if no further improvement is possible.

Definition at line 1672 of file blossom_weighted_mwmatching.H.

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

◆ substage_apply_delta_step()

template<typename WeightType >

void Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::substage_apply_delta_step ( WeightType delta )

inline

Apply a delta step to the dual LPP variables.

Definition at line 1604 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::graph, Aleph::blossom_weighted_detail::mwmatching::impl::LABEL_S, Aleph::blossom_weighted_detail::mwmatching::impl::LABEL_T, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::nontrivial_blossom, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_dual, and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_top_blossom.

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

◆ substage_calc_dual_delta()

template<typename WeightType >

DeltaStep Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::substage_calc_dual_delta ( )

inline

Calculate a delta step in the dual LPP problem.

This function returns the minimum of the 4 types of delta values, and the type of delta which obtain the minimum, and the edge or blossom that produces the minimum delta, if applicable.

This function takes time O(n).

Precondition: There is at least one S-vertex.

Returns: Tuple (delta_type, delta_value, delta_edge, delta_blossom)

Definition at line 1556 of file blossom_weighted_mwmatching.H.

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

◆ substage_scan()

template<typename WeightType >

bool Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::substage_scan ( )

inline

Scan queued S-vertices to expand the alternating trees.

The scan proceeds until either an augmenting path is found, or the queue of S-vertices becomes empty. If an augmenting path is found, it is used to augment the matching.

New blossoms may be created during the scan.

Returns: True if the matching was augmented; otherwise false.

Definition at line 1465 of file blossom_weighted_mwmatching.H.

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

◆ trace_alternating_paths()

template<typename WeightType >

AlternatingPath Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::trace_alternating_paths	(	VertexId	x,
		VertexId	y
	)

inline

Trace back through the alternating trees from vertices "x" and "y".

If both vertices are part of the same alternating tree, this function discovers a new blossom. In this case it returns an alternating path through the blossom that starts and ends in the same sub-blossom.

If the vertices are part of different alternating trees, this function discovers an augmenting path. In this case it returns an alternating path that starts and ends in an unmatched vertex.

This function takes time O(k) to discover a blossom, where "k" is the number of sub-blossoms, or time O(n) to discover an augmenting path.

Definition at line 889 of file blossom_weighted_mwmatching.H.

References Aleph::Array< T >::append(), Aleph::DynDlist< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::AlternatingPath::edges, Aleph::Array< T >::empty(), Aleph::DynDlist< T >::get_first(), Aleph::DynDlist< T >::get_last(), Aleph::DynDlist< T >::insert(), k, Aleph::blossom_weighted_detail::mwmatching::impl::LABEL_S, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::marked_vertex, Aleph::blossom_weighted_detail::mwmatching::impl::NO_VERTEX, Aleph::DynDlist< T >::remove_first(), Aleph::DynDlist< T >::remove_last(), Aleph::DynDlist< T >::size(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_marker, Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::vertex_top_blossom, and y.