Referencia de la plantilla de la Clase Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >

#include <Prim.H>

Métodos públicos
	Prim_Min_Spanning_Tree (Distance &&__dist=Distance(), SA &&__sa=SA())
	Prim_Min_Spanning_Tree (Distance &__dist, SA &__sa)
void	operator() (GT &g, GT &tree)
void	operator() (GT &g, typename GT::Node *start, GT &tree)
void	operator() (GT &g)
	overload ()
void	operator() (GT &g, typename GT::Node *start)

Descripción detallada

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:

1. GT: el tipo de grafo basado en List_Graph.
2. 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.
3. 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.
4. SA: filtro de arcos

Ver también

Kruskal_Min_Spanning_Tree

Documentación del constructor y destructor

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.

Parámetros

[in,out]	__dist	acceso a la distancia de cada arco
[in,out]	__cmp	comparación entre distancias de arco
[in,out]	__sa	filtro de iterador de arcos

Documentación de las funciones miembro

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

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

inline

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

Parámetros

[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.

Excepciones

bad_alloc

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

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

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

inline

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

Parámetros

[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.

Excepciones

bad_alloc

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

---

La documentación para esta clase fue generada a partir del siguiente fichero:

• Prim.H