Calcula el árbol abarcador mínimo de un grafo según el algoritmo de Prim. 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)
	Invoca al cálculo del árbol abarcador mínimo por el algoritmo de Prim.

void	operator() (const GT &g, typename GT::Node *start, GT &tree)
	Invoca al cálculo del árbol abarcador mínimo por el algoritmo de Prim.

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<class GT, class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>
class Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >

Calcula el árbol abarcador mínimo de un grafo según el algoritmo de Prim.

Esta clase emplea el algoritmo de Prim para calcular el árbol abarcador mínimo de un grafo y almacenarlo en otro grafo.

El árbol abarcador mínimo tree completamente mapeado con el grafo.

El algoritmo utiliza una cola interna cuya longitud máxima es proporcional número de nodos del grafo.

El algoritmo de Prim es el recomendado para grafos densos.

El procedimiento es parametrizado con las siguientes especificaciones:

GT: el tipo de grafo basado en List_Graph.
Distance<GT>: La clase de lectura del peso del arco que debe exportar los siguientes atributos:
1. typedef Distance<GT>::Distance_Type: el tipo de dato que representa un peso en un arco.
2. Distance<GT>::Distance_Type operator()(typename GT::Arc *a): que retorna el valor del peso en el arco a.
3. Distance<GT>::Max_Distance: constante estática correspondiente al valor de distancia máximo que un algoritmo consideraría como valor infinito.
4. typename Distance<GT>::Zero_Distance: constante estática correspondiente al elemento neutro de la suma. Tradicionalmente, en la inmensa mayoría de casos, este será el cero.
Compare<GT>: clase que realiza la comparación entre dos pesos y cuyo prototipo es:
- bool operator () (const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const . Por omisión, esta clase implanta el operador relacional menor que.
SA: filtro de arcos

See also: Kruskal_Min_Spanning_Tree

Definition at line 213 of file Prim.H.

Member Typedef Documentation

◆ Acc_Heap

template<class GT , class Distance = Dft_Dist<GT>, class 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 215 of file Prim.H.

◆ Acc_Simple_Heap

template<class GT , class Distance = Dft_Dist<GT>, class 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 217 of file Prim.H.

◆ Heap

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

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

private

Definition at line 219 of file Prim.H.

◆ Simple_Heap

template<class GT , class Distance = Dft_Dist<GT>, class 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 221 of file Prim.H.

Constructor & Destructor Documentation

◆ Prim_Min_Spanning_Tree()

template<class GT , class Distance = Dft_Dist<GT>, class 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	acceso a la distancia de cada arco
[in]	__sa	filtro de iterador de arcos

Definition at line 232 of file Prim.H.

Member Function Documentation

◆ min_spanning_tree()

template<class GT , class Distance = Dft_Dist<GT>, class 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 297 of file Prim.H.

References ah_domain_error_if, ARC_BITS, 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::maps(), 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<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

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

inline

overload ()

Definition at line 404 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<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

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

inline

Invoca al cálculo del árbol abarcador mínimo por el algoritmo de Prim.

Parameters

[in]	g	el grafo al cual se desea calcular el árbol abarcador mínimo.
[out]	tree	el grafo donde se desea guardar el árbol abarcador mínimo resultado. Este grafo es limpiado antes del comienzo del algoritmo.

Exceptions

bad_alloc si no hay suficiente memoria para construir tree. En este caso el valor de tree es indeterminado y no está limpio.

Definition at line 380 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<class GT , class Distance = Dft_Dist<GT>, class 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 409 of file Prim.H.

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

◆ operator()() [4/4]

template<class GT , class Distance = Dft_Dist<GT>, class 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

Invoca al cálculo del árbol abarcador mínimo por el algoritmo de Prim.

Parameters

[in]	g	el grafo al cual se desea calcular el árbol abarcador mínimo.
[in]	start	nodo desde el cual se inicia elalgoritmo.
[out]	tree	el grafo donde se desea guardar el árbol abarcador mínimo resultado. Este grafo es limpiado antes del comienzo del algoritmo.

Exceptions

bad_alloc si no hay suficiente memoria para construir tree. En este caso el valor de tree es indeterminado y no está limpio.

Definition at line 398 of file Prim.H.

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