Aleph-w: Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType > Struct Template Reference

Aleph-w 3.0

A C++ Library for Data Structures and Algorithms

Loading...

Searching...

No Matches

Represents a blossom in the algorithm. More...

#include <blossom_weighted_mwmatching.H>

Inheritance diagram for Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >:

Public Member Functions
	Blossom ()

	Blossom (VertexId base_vertex)

NonTrivialBlossom< WeightType > *	nontrivial ()
	Safe downcast to NonTrivialBlossom.

const NonTrivialBlossom< WeightType > *	nontrivial () const
	Safe downcast to NonTrivialBlossom (const version).

Public Attributes
NonTrivialBlossom< WeightType > *	parent
	Parent in the blossom hierarchy, or null if top-level.

VertexId	base_vertex
	Index of the base vertex (the unmatched vertex in the blossom).

BlossomLabel	label
	Label S or T if this is part of the current alternating forest.

bool	is_nontrivial_blossom
	Flag to distinguish between Blossom and NonTrivialBlossom.

VertexPair	tree_edge
	Tree edge attaching this blossom to its parent in the alternating forest.

const Edge< WeightType > *	best_edge
	Best edge for dual variable calculation (least slack).

Protected Member Functions
	Blossom (const VertexId base_vertex, const bool is_nontrivial_blossom)

Detailed Description

template<typename WeightType>
struct Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >

Represents a blossom in the algorithm.

A blossom is either a single vertex (trivial) or an odd-length alternating cycle of sub-blossoms.

Template Parameters

WeightType Numeric type for weights.

Definition at line 315 of file blossom_weighted_mwmatching.H.

Constructor & Destructor Documentation

◆ Blossom() [1/3]

template<typename WeightType >

Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::Blossom	(	const VertexId	base_vertex,
		const bool	is_nontrivial_blossom
	)

inlineprotected

Definition at line 337 of file blossom_weighted_mwmatching.H.

◆ Blossom() [2/3]

template<typename WeightType >

Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::Blossom ( )

inline

Definition at line 347 of file blossom_weighted_mwmatching.H.

◆ Blossom() [3/3]

template<typename WeightType >

Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::Blossom ( VertexId base_vertex )

inlineexplicit

Definition at line 352 of file blossom_weighted_mwmatching.H.

Member Function Documentation

◆ nontrivial() [1/2]

template<typename WeightType >

NonTrivialBlossom< WeightType > * Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::nontrivial ( )

inline

Safe downcast to NonTrivialBlossom.

Definition at line 357 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::is_nontrivial_blossom.

Referenced by Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::assign_label_t(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::augment_blossom_rec(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::augment_matching(), Aleph::blossom_weighted_detail::mwmatching::impl::for_vertices_in_blossom(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_add_blossom_edge(), and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_new_blossom().

◆ nontrivial() [2/2]

template<typename WeightType >

const NonTrivialBlossom< WeightType > * Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::nontrivial ( ) const

inline

Safe downcast to NonTrivialBlossom (const version).

Definition at line 365 of file blossom_weighted_mwmatching.H.

References Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::is_nontrivial_blossom.

Member Data Documentation

◆ base_vertex

template<typename WeightType >

VertexId Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::base_vertex

Index of the base vertex (the unmatched vertex in the blossom).

Definition at line 321 of file blossom_weighted_mwmatching.H.

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

◆ best_edge

template<typename WeightType >

const Edge<WeightType>* Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::best_edge

Best edge for dual variable calculation (least slack).

Definition at line 333 of file blossom_weighted_mwmatching.H.

Referenced by Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_add_blossom_edge(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_merge_blossoms(), and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::lset_new_blossom().

◆ is_nontrivial_blossom

template<typename WeightType >

bool Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::is_nontrivial_blossom

Flag to distinguish between Blossom and NonTrivialBlossom.

Definition at line 327 of file blossom_weighted_mwmatching.H.

Referenced by Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::nontrivial(), and Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::nontrivial().

◆ label

template<typename WeightType >

BlossomLabel Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::label

Label S or T if this is part of the current alternating forest.

Definition at line 324 of file blossom_weighted_mwmatching.H.

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

◆ parent

template<typename WeightType >

NonTrivialBlossom<WeightType>* Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::parent

Parent in the blossom hierarchy, or null if top-level.

Definition at line 318 of file blossom_weighted_mwmatching.H.

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

◆ tree_edge

template<typename WeightType >

VertexPair Aleph::blossom_weighted_detail::mwmatching::impl::Blossom< WeightType >::tree_edge

Tree edge attaching this blossom to its parent in the alternating forest.

Definition at line 330 of file blossom_weighted_mwmatching.H.

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

The documentation for this struct was generated from the following file:

blossom_weighted_mwmatching.H