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

#include <Kruskal.H>

Classes
struct	Paint_Filt
	Filtro de arcos pintados por el algoritmo de Kruskal. More...

Public Member Functions
	Kruskal_Min_Spanning_Tree (Distance &&__dist=Distance(), SA __sa=SA()) noexcept(std::is_nothrow_move_assignable< Distance >::value and std::is_nothrow_move_assignable< SA >::value)
	Kruskal_Min_Spanning_Tree (Distance &__dist, SA __sa=SA()) noexcept(std::is_nothrow_copy_assignable< Distance >::value and std::is_nothrow_copy_assignable< SA >::value)
void	paint_min_spanning_tree (const GT &g)
void	paint_min_spanning_tree (const GT &g, GT &tree)
void	operator() (const GT &g, GT &tree)
void	operator() (const GT &g)

Detailed Description

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

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

El algoritmo de Kruskal es el recomendado para grafos esparcidos.

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) 

   . Por omisión, esta clase implanta el operador relacional menor que.
4. SA: filtro de arcos.

See also

Prim_Min_Spanning_Tree

Constructor & Destructor Documentation

Kruskal_Min_Spanning_Tree()

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

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

inlinenoexcept

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::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::operator() ( const GT &  g, GT &  tree  )

inline

Invoca el cálculo del árbol abarcador según Kruskal.

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::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::operator() ( const GT &  g )

inline

Pinta en el grafo el árbol abarcador según Kruskal.

Al terminar el algoritmo, los arcos de g que pertenecen al árbol abarcador están pintados con el bit Kruskal.

Parameters

[in]

g

el grafo al cual se desea calcular el árbol abarcador mínimo.

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:

• Kruskal.H