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

#include <Floyd.H>

Métodos públicos
Node *	select_node (long i)
int	index_node (Node *p)
	Floyd_All_Shortest_Paths (GT &__g, SA &&__sa=SA())
	Floyd_All_Shortest_Paths (GT &__g, const SA &__sa)
string	entry (const Distance_Type &e)
bool	operator() (DynMatrix< Distance_Type > &dist, DynMatrix< long > &path)
void	get_min_path (const long src_idx, const long tgt_idx, Path< GT > &path)
void	get_min_path (typename GT::Node *src, typename GT::Node *tgt, Path< GT > &path) const

Métodos públicos estáticos
static void	print (DynMatrix< Distance_Type > &dist)

Descripción detallada

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

Calcula las matriz de costes de los caminos mínimos entre todos pares de nodos de un grafo g y la matriz de caminos mínimos según el algoritmo de Floy-Warshall.

Esta clase utiliza el algoritmo de Floy-Warshall para calcular dos matrices de tipo Ady_Mat que se especifican del siguiente modo:

1. dist: matriz de costes mínimos entre todos los pares de nodos. Cada entrada dist(i,j) almacena el coste total mínimo para ir del nodo con índice i hacia el nodo con índice j.
   Recuérdese que un índice de nodo en la matriz dist puede calcularse mediante dist(node), donde node es un puntero a nodo en una representación con listas enlzadas derivada del tipo de grafo
2. path: matriz de caminos mínimos. Cada entrada path(i,j) almacena el nodo k que permitió al algoritmo de Floyd-Warshall encontrar el mínimo valor de dist(i,j). De este modo, inspecciones sucesivas a dist(k,j) permiten encontrar y construir el camino hacia el nodo j.
   La función find_min_path(g,i,j,path) realiza la función anterior.

El algoritmo de Floyd-Warshall maneja pesos negativos, pero no opera correctamente si el grafo contiene ciclos negativos. Úsese el algoritmo de Bellman-Ford q_bellman_ford_min_spanning_tree() si se sospecha su presencia.

El algoritmo utiliza dos matrices internas adicionales.

El procedimiento es parametrizado con las siguientes especificaciones:

1. GT: el tipo de grafo
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
4. Plus<GT>: clase que realiza la suma de distancias con el siguiente prototipo:
   • typename Distance<GT>::Distance_Type operator()(const typename Distance<GT>::Distance_Type & op1, const typename Distance<GT>::Distance_Type & op2) const
5. SA: filtro de arcos.

Ver también

dijkstra_min_spanning_tree() dijkstra_min_path() find_path_depth_first() find_min_path() bellman_ford_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Documentación de las funciones miembro

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

int Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::index_node ( Node *  p )

inline

Retorna el ìndice dentro de una matriz de adyacencia que tendría el nodo p

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

bool Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::operator() ( DynMatrix< Distance_Type > &  dist, DynMatrix< long > &  path  )

inline

Invoca al cálculo de las matrices de costes mínimos y sus caminos entre todos los pares de nodos.

@param[in] g el grafo al cual se desea calcular el árbol
abarcador mínimo.
@param[in] dist matriz donde se almacenan los costes mínimos.
@param[out] path matriz de índices de caminos mínimos que
permite su recuperación.
@throw bad_alloc si no hay suficiente memoria para construir
las matrices internas

Hace referencia a Aleph::DynMatrix< T >::allocate(), Aleph::IndexArc< GT, Tree, SA >::search() y Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::select_node().

Gráfico de llamadas para esta función:

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

Node* Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::select_node ( long  i )

inline

Retorna el nodo correspondiente al índice i en una matriz de adyacencia para el algoritmo de Floyd-Warshall

Referenciado por Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::operator()().

Gráfico de llamadas a esta función:

---

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

• Floyd.H