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

#include <Prim.H>

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

void	operator() (const GT &g, GT &tree)
	Invokes the computation of the minimum spanning tree using Prim's algorithm.

void	operator() (const GT &g, typename GT::Node *start, GT &tree)
	Invokes the computation of the minimum spanning tree using Prim's algorithm.

void	operator() (const GT &g)
	overload ()

void	operator() (const GT &g, typename GT::Node *start)

Private Types
typedef Prim_Heap_Info< GT, Distance >	Acc_Heap

typedef Simple_Prim_Heap< GT, Distance >	Acc_Simple_Heap

typedef ArcHeap< GT, Distance, Acc_Heap >	Heap

typedef ArcHeap< GT, Distance, Acc_Simple_Heap >	Simple_Heap

Private Member Functions
void	paint_min_spanning_tree (const GT &g, typename GT::Node *first)

void	min_spanning_tree (const GT &g, typename GT::Node *first, GT &tree)

Private Attributes
Distance	dist

SA	sa

Detailed Description

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

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

This class uses Prim's algorithm to compute the minimum spanning tree of a graph and stores it in another graph.

The resulting minimum spanning tree is fully mapped to the graph.

The algorithm uses an internal queue whose maximum length is proportional to the number of nodes of the graph.

Prim's algorithm is recommended for dense graphs.

The procedure is parameterized with the following specifications:

GT: the graph type, based on List_Graph.
Distance<GT>: the class that reads an arc's weight, which must export the following members:
1. typedef Distance<GT>::Distance_Type: the data type that represents an arc's 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 corresponding to the maximum distance value an algorithm would consider as infinite.
4. typename Distance<GT>::Zero_Distance: static constant corresponding to the neutral element of the sum. Traditionally, in the vast majority of cases, this will be zero.
Compare<GT>: class that compares two weights and whose prototype is:
- bool operator () (const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const . By default, this class implements the less-than relational operator.
SA: arc filter

See also: Kruskal_Min_Spanning_Tree

Definition at line 214 of file Prim.H.

Member Typedef Documentation

◆ Acc_Heap

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

typedef Prim_Heap_Info<GT, Distance> Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::Acc_Heap

private

Definition at line 216 of file Prim.H.

◆ Acc_Simple_Heap

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

typedef Simple_Prim_Heap<GT, Distance> Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::Acc_Simple_Heap

private

Definition at line 218 of file Prim.H.

◆ Heap

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

typedef ArcHeap<GT, Distance, Acc_Heap> Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::Heap

private

Definition at line 220 of file Prim.H.

◆ Simple_Heap

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

typedef ArcHeap<GT, Distance, Acc_Simple_Heap> Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::Simple_Heap

private

Definition at line 222 of file Prim.H.

Constructor & Destructor Documentation

◆ Prim_Min_Spanning_Tree()

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

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

inline

Constructor.

Parameters

[in]	__dist	access to each arc's distance
[in]	__sa	arc iterator filter

Definition at line 233 of file Prim.H.

Member Function Documentation

◆ min_spanning_tree()

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

void Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::min_spanning_tree	(	const GT &	g,
		typename GT::Node *	first,
		GT &	tree
	)

inlineprivate

Definition at line 298 of file Prim.H.

References ah_domain_error_if, Aleph::and, ARC_BITS, Aleph::blossom_maximum_cardinality_matching(), Aleph::clear_graph(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::dist, GTArcCommon< ArcInfo >::get_info(), ArcHeap< GT, Distance, Access_Heap_Node >::get_min_arc(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::init, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), IS_ARC_VISITED, GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::GenBinHeap< NodeType, Key, Compare >::is_empty(), IS_NODE_VISITED, GraphCommon< GT, Node, Arc >::map_arcs(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_BITS, ArcHeap< GT, Distance, Access_Heap_Node >::put_arc(), GraphCommon< GT, Node, Arc >::reset_arcs(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::sa, Aleph::Spanning_Tree, and TREENODE.

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

◆ operator()() [1/4]

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

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

inline

overload ()

Definition at line 405 of file Prim.H.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node(), and Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree().

◆ operator()() [2/4]

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

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

inline

Invokes the computation of the minimum spanning tree using Prim's algorithm.

Parameters

[in]	g	the graph whose minimum spanning tree is to be computed.
[out]	tree	the graph where the resulting minimum spanning tree is to be stored. This graph is cleared before the algorithm starts.

Exceptions

bad_alloc if there is not enough memory to build tree. In this case tree's value is indeterminate and it is not clean.

Definition at line 381 of file Prim.H.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node(), and Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::min_spanning_tree().

◆ operator()() [3/4]

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

void Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::operator()	(	const GT &	g,
		typename GT::Node *	start
	)

inline

Definition at line 410 of file Prim.H.

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

◆ operator()() [4/4]

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

void Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::operator()	(	const GT &	g,
		typename GT::Node *	start,
		GT &	tree
	)

inline

Invokes the computation of the minimum spanning tree using Prim's algorithm.

Parameters

[in]	g	the graph whose minimum spanning tree is to be computed.
[in]	start	the node from which the algorithm starts.
[out]	tree	the graph where the resulting minimum spanning tree is to be stored. This graph is cleared before the algorithm starts.

Exceptions

bad_alloc if there is not enough memory to build tree. In this case tree's value is indeterminate and it is not clean.

Definition at line 399 of file Prim.H.

References Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::min_spanning_tree().