Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA > Class Template Reference

#include <Prim.H>

Public Member Functions
	Prim_Min_Spanning_Tree (Distance __dist=Distance(), SA __sa=SA())
void	operator() (const GT &g, GT &tree)
void	operator() (const GT &g, typename GT::Node *start, GT &tree)
void	operator() (const GT &g)
	overload ()
void	operator() (const GT &g, typename GT::Node *start)

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:

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

See also

Kruskal_Min_Spanning_Tree

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,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

Member Function Documentation

operator()() [1/2]

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.

operator()() [2/2]

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.

---

The documentation for this class was generated from the following file:

• Prim.H