Aleph-w  1.5a.2
Biblioteca general de algoritmos y estructuras de datos
 Todo Clases Archivos Funciones Variables 'typedefs' Enumeraciones Amigas Grupos Páginas
Clases | Métodos públicos | Lista de todos los miembros
Referencia de la plantilla de la Clase Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >
Grafos.

#include <Kruskal.H>

Clases

struct  Paint_Filt
 Filtro de arcos pintados por el algoritmo de Kruskal. Más...
 

Métodos públicos

 Kruskal_Min_Spanning_Tree (Distance &&__dist=Distance(), SA &&__sa=SA())
 
 Kruskal_Min_Spanning_Tree (Distance &__dist, SA &__sa)
 
void paint_min_spanning_tree (GT &g)
 
void paint_min_spanning_tree (GT &g, GT &tree)
 
void operator() (GT &g, GT &tree)
 
void operator() (GT &g)
 

Descripción detallada

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.
Ver también
Prim_Min_Spanning_Tree

Documentación del constructor y destructor

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() 
)
inline

Constructor.

Parámetros
[in,out]__distacceso a la distancia de cada arco
[in,out]__cmpcomparación entre distancias de arco
[in,out]__safiltro 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::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::operator() ( GT &  g,
GT &  tree 
)
inline

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

Parámetros
[in]gel grafo al cual se desea calcular el árbol abarcador mínimo.
[out]treeel grafo donde se desea guardar el árbol abarcador mínimo resultado. Este grafo es limpiado antes del comienzo del algoritmo.
Excepciones
bad_allocsi 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::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::operator() ( 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.

Parámetros
[in]gel grafo al cual se desea calcular el árbol abarcador mínimo.
Excepciones
bad_allocsi 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:
Leandro Rabindranath León