Computes the minimum spanning tree of a graph using Kruskal's algorithm. More...

#include <Kruskal.H>

Classes
struct	Init_Node
	Helper struct for initializing node counters during DFS. More...

struct	Paint_Filt
	Filter for arcs painted by Kruskal's algorithm. More...

Public Member Functions
	Kruskal_Min_Spanning_Tree (Distance __dist=Distance(), SA __sa=SA())
	Constructor.

	Kruskal_Min_Spanning_Tree (Distance &__dist, SA __sa=SA())
	Constructor with reference to external distance accessor.

bool	is_painted () const noexcept
	Returns true if the spanning tree has been painted on the graph.

void	paint_min_spanning_tree (const GT &g)
	Paints the minimum spanning tree arcs on the graph.

void	paint_min_spanning_tree (const GT &g, GT &tree)
	Paints the MST on g and copies it to a separate tree graph.

void	operator() (const GT &g, GT &tree)
	Computes the minimum spanning tree using Kruskal's algorithm.

void	operator() (const GT &g)
	Paints the minimum spanning tree on the graph using Kruskal's algorithm.

Static Private Member Functions
static bool	arc_is_in_tree (Fixed_Relation &tree, long i, long j) noexcept

Private Attributes
Distance	dist_val

Distance &	dist

SA	sa

bool	painted

Detailed Description

template<AlephGraph GT, class Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
class Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >

Computes the minimum spanning tree of a graph using Kruskal's algorithm.

Kruskal's algorithm is recommended for sparse graphs. It works by sorting all arcs by weight and greedily adding arcs that don't form a cycle.

The procedure is parameterized with the following specifications:

GT: The graph type based on List_Graph.
Distance<GT>: The arc weight accessor class that must export the following attributes:
1. typedef Distance<GT>::Distance_Type: The data type that represents an arc weight.
2. Distance<GT>::Distance_Type operator()(typename GT::Arc *a): Returns the weight value of arc a.
3. Distance<GT>::Max_Distance: Static constant representing the maximum distance value that an algorithm would consider as infinity.
4. typename Distance<GT>::Zero_Distance: Static constant corresponding to the neutral element of addition. Traditionally, in the vast majority of cases, this is zero.
SA: Arc filter for arc iterators.

Time complexity: O(E log E) where E is the number of arcs. Space complexity: O(V) for the Union-Find structure.

See also: Prim_Min_Spanning_Tree

Definition at line 91 of file Kruskal.H.

Constructor & Destructor Documentation

◆ Kruskal_Min_Spanning_Tree() [1/2]

template<AlephGraph GT, class Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::Kruskal_Min_Spanning_Tree	(	Distance	__dist = `Distance()`,
		SA	__sa = `SA()`
	)

inline

Constructor.

Parameters

__dist	Distance accessor for arc weights.
__sa	Arc filter for arc iterators.

Definition at line 123 of file Kruskal.H.

◆ Kruskal_Min_Spanning_Tree() [2/2]

template<AlephGraph GT, class Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::Kruskal_Min_Spanning_Tree	(	Distance &	__dist,
		SA	__sa = `SA()`
	)

inline

Constructor with reference to external distance accessor.

Definition at line 130 of file Kruskal.H.

Member Function Documentation

◆ arc_is_in_tree()

template<AlephGraph GT, class Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

static bool Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::arc_is_in_tree	(	Fixed_Relation &	tree,
		long	i,
		long	j
	)

inlinestaticprivatenoexcept

Definition at line 112 of file Kruskal.H.

Referenced by Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree().

◆ is_painted()

template<AlephGraph GT, class Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

bool Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::is_painted ( ) const

inlinenoexcept

Returns true if the spanning tree has been painted on the graph.

Definition at line 137 of file Kruskal.H.

References Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::painted.

◆ operator()() [1/2]

template<AlephGraph GT, class Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::operator() ( const GT & g )

inline

Paints the minimum spanning tree on the graph using Kruskal's algorithm.

After the algorithm completes, the arcs of g that belong to the spanning tree are marked with the Spanning_Tree bit.

Parameters

[in] g The graph for which to compute the minimum spanning tree.

Exceptions

bad_alloc	If there is not enough memory.
domain_error	If g is a digraph.

Definition at line 258 of file Kruskal.H.

References Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree().

◆ operator()() [2/2]

template<AlephGraph GT, class Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::operator()	(	const GT &	g,
		GT &	tree
	)

inline

Computes the minimum spanning tree using Kruskal's algorithm.

Parameters

[in]	g	The graph for which to compute the minimum spanning tree.
[out]	tree	The graph where the resulting minimum spanning tree will be stored. This graph is cleared before the algorithm starts.

Exceptions

bad_alloc	If there is not enough memory to construct the tree. In this case, the value of tree is indeterminate and not clean.
domain_error	If g is a digraph.

Definition at line 243 of file Kruskal.H.

References Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree().

◆ paint_min_spanning_tree() [1/2]

template<AlephGraph GT, class Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree ( const GT & g )

inline

Paints the minimum spanning tree arcs on the graph.

After calling this method, the arcs belonging to the MST are marked with the Spanning_Tree bit. Use is_painted() to check if the tree has been painted.

Note: The const_cast on g is safe because sort_arcs only changes the physical ordering of arcs, not the logical graph structure.

Parameters

[in] g The graph for which to compute the minimum spanning tree.

Exceptions

domain_error If g is a digraph.

Definition at line 168 of file Kruskal.H.

References ah_domain_error_if, Aleph::and, ARC_BITS, Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::arc_is_in_tree(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::dist, Fixed_Relation::get_num_blocks(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), GraphCommon< GT, Node, Arc >::is_digraph(), Fixed_Relation::join(), NODE_COUNTER, Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::painted, GraphCommon< GT, Node, Arc >::reset_bit_arcs(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::sa, Aleph::Spanning_Tree, and V.

Referenced by Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::operator()(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::operator()(), and Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree().

◆ paint_min_spanning_tree() [2/2]

template<AlephGraph GT, class Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree	(	const GT &	g,
		GT &	tree
	)

inline

Paints the MST on g and copies it to a separate tree graph.

First paints the spanning tree arcs on g, then creates a copy of the MST in the tree parameter.

Parameters

[in]	g	The graph for which to compute the minimum spanning tree.
[out]	tree	The graph where the resulting minimum spanning tree will be stored. This graph is cleared before the algorithm starts.

Exceptions