KI_MST Namespace Reference

Minimum spanning forest by Filter-Kruskal. More...

Functions
template<typename EDGE, typename LESS, typename ENDPOINTS, typename EMIT>
size_t	FilterKruskal (std::span< EDGE > aEdges, KI_UNION_FIND &aForest, LESS aLess, ENDPOINTS aEndpoints, EMIT aEmit)
	Build a minimum spanning forest over aEdges.

Variables
static constexpr size_t	KRUSKAL_THRESHOLD = 1024
	< Sort and scan a range of this size or smaller instead of splitting it again.

Detailed Description

Minimum spanning forest by Filter-Kruskal.

Plain Kruskal sorts every edge, although most edges of a dense graph close a cycle and are discarded as soon as the scan reaches them. Filter-Kruskal does not sort those. It splits the edges at a pivot, recurses into the lighter half, then discards each edge of the heavier half whose endpoints the lighter half already joined. The cycle property keeps the result the same as plain Kruskal.

Osipov, V., Sanders, P., & Singler, J. (2009). The Filter-Kruskal minimum spanning tree algorithm. Proceedings of the Meeting on Algorithm Engineering & Experiments (ALENEX), 52-61. SIAM.

Function Documentation

FilterKruskal()

template<typename EDGE, typename LESS, typename ENDPOINTS, typename EMIT>

size_t KI_MST::FilterKruskal	(	std::span< EDGE >	aEdges,
		KI_UNION_FIND &	aForest,
		LESS	aLess,
		ENDPOINTS	aEndpoints,
		EMIT	aEmit )

Build a minimum spanning forest over aEdges.

Parameters

aEdges	is the candidate edge set. This function reorders it.
aForest	is the union-find state. A caller can unite known-connected pairs first, because this function discards the edges those pairs imply.
aLess	must be a strict total order on edges and not on their weights alone. A tie that the order leaves open makes the chosen tree depend on the platform.
aEndpoints	maps an edge to its two vertex indices, both below aForest.Size().
aEmit	receives each selected edge in order of increasing weight.

Returns

the number of edges emitted.

Definition at line 63 of file filter_kruskal.h.

References KI_UNION_FIND::ComponentCount(), end, filter, KRUSKAL_THRESHOLD, LESS, and KI_UNION_FIND::Unite().

Referenced by BOOST_AUTO_TEST_CASE(), and RN_NET::kruskalMST().

Variable Documentation

KRUSKAL_THRESHOLD

size_t KI_MST::KRUSKAL_THRESHOLD = 1024

staticconstexpr

< Sort and scan a range of this size or smaller instead of splitting it again.

Definition at line 47 of file filter_kruskal.h.

Referenced by FilterKruskal().