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

#include <Dijkstra.H>

Clases
struct	Painted
struct	Total
	Clase totalizadora de distancias. Más...

Métodos públicos
	Dijkstra_Min_Paths (Plus &&__plus=Plus(), Distance &&dist=Distance(), SA &&__sa=SA())
	Dijkstra_Min_Paths (Plus &__plus, Distance &dist, SA &__sa)
void	compute_min_paths_tree (GT &g, typename GT::Node *start, GT &tree)
void	compute_partial_min_paths_tree (GT &g, typename GT::Node *start, typename GT::Node *end, GT &tree)
void	paint_partial_min_paths_tree (GT &g, typename GT::Node *start, typename GT::Node *end)
void	paint_min_paths_tree (GT &g, typename GT::Node *start)
Distance::Distance_Type	get_min_path (typename GT::Node *end, Path< GT > &path)
Distance::Distance_Type	find_min_path (GT &g, typename GT::Node *start, typename GT::Node *end, Path< GT > &min_path)
void	operator() (GT &g, typename GT::Node *s, GT &tree)
Distance::Distance_Type	copy_painted_min_paths_tree (GT &g, GT &tree)
Distance::Distance_Type	operator() (GT &g, typename GT::Node *s, typename GT::Node *e, Path< GT > &path)
	find_min_path()
Distance::Distance_Type	get_min_path (GT &tree, typename GT::Node *end, Path< GT > &path)

Descripción detallada

template<class GT, class Distance = Dft_Dist<GT>, class Plus = Dft_Plus<GT, Distance>, class SA = Dft_Show_Arc<GT>>
class Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >

Calculo de árbol abarcador de todos los caminos mínimos desde un nodo dado según el algoritmo de Dijkstra.

Esta clase maneja el algoritmo de Dijkstra para calcular un árbol abarcador de todos los caminos mínimos desde un nodo s de un grafo g.

El algoritmo utiliza una cola interna cuya longitud máxima es proporcional número de nodos del grafo.

El algoritmo de Dijkstra es el que exhibe mejor desempeño y es por tanto el recomendado para la mayoría de aplicaciones de caminos mínimos.

El algoritmo de Dijkstra no opera para grafos con pesos negativos.

La clase recibe los siguientes parámetros tipo:

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)

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) 

1. SA: filtro de arcos para el iterador interno

Ver también

Find_Path_Depth_First Floyd_All_Shortest_Paths Bellman_Ford_Min_Spanning_Tree

Documentación del constructor y destructor

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

Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::Dijkstra_Min_Paths ( Plus &&  __plus = Plus(), Distance &&  dist = Distance(), SA &&  __sa = SA()  )

inline

Constructor

Parámetros

[in]	dist	acceso a la distancia de arco.
[in]	cmp	comparador entre la distancias de arcos.
[in]	__plus	sumador de distancias entre los arcos.
[in]	__sa	filtro de arcos para los iteradores.

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

Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::Dijkstra_Min_Paths ( Plus &  __plus, Distance &  dist, SA &  __sa  )

inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

Documentación de las funciones miembro

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

void Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_min_paths_tree ( GT &  g, typename GT::Node *  start, GT &  tree  )

inline

Calcula el árbol abarcador de todos los caminos mínimos que parten desde el nodo start.

Parámetros

[in]	g	el grafo.
[in]	start	el nodo inicio de todos los caminos mínimos
[out]	tree	el árbol abarcador de todos los caminos mínimos que comienzan por start mapeado mediante los cookies al grafo g.

Excepciones

bad_alloc

si no hay suficiente memoria

Hace referencia a ARC_BITS, Aleph::clear_graph(), IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next(), NODE_BITS y NODE_COOKIE.

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

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

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

void Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_partial_min_paths_tree ( GT &  g, typename GT::Node *  start, typename GT::Node *  end, GT &  tree  )

inline

Calcula el árbol abarcador parcial de todos los caminos mínimos que parten desde el nodo start y que contiene al camino start-end.

compute_partial_min_paths_tree() construye el árbol abarcador de caminos mínimos que parten desde start pero el cálculo se detiene cuando se encuentra el nodo end.

Parámetros

[in]	g	el grafo.
[in]	start	el nodo inicio de todos los caminos mínimos
[in]	end
[out]	tree	el árbol abarcador de todos los caminos mínimos que comienzan por start mapeado mediante los cookies al grafo g.

Excepciones

bad_alloc

si no hay suficiente memoria

Hace referencia a ARC_BITS, Aleph::clear_graph(), IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next(), NODE_BITS y NODE_COOKIE.

Gráfico de llamadas para esta función:

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

Distance::Distance_Type Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::copy_painted_min_paths_tree ( GT &  g, GT &  tree  )

inline

Extrae el árbol de caminos mínimos (parcial o total) y lo pone en tree.

copy_painted_min_paths_tree() toma un grafo g sobre el cual están pintados los caminos mínimos (total o parcial) mediante llamadas previas a paint_min_paths_tree() o paint_partial_min_paths_tree() y extrae una copia hacia el parámetro tree.

Parámetros

[in]	g	el grafo previamente pintado donde están los caminos mínimos.
[out]	tree	el grafo donde se desea copiar el árbol abarcador

Excepciones

bad_alloc

si no hay suficiente memoria.

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

Distance::Distance_Type Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::find_min_path ( GT &  g, typename GT::Node *  start, typename GT::Node *  end, Path< GT > &  min_path  )

inline

Calcula el camino mínimo entre el nodo start y end por pintado del grafo.

Esta es la versión de menor consumo de memoria y probablemente también la más rápida. Note que cada llamada calcula el árbol parcial de caminos mínimos desde start.

Use get_min_path() si ya calculó el árbol abarcador y desea simplemente obtener el camino mínimo.

Parámetros

[in]	g	el grafo.
[in]	start	el nodo inicio del camino.
[in]	end	el nodo final del camino.
[in]	min_path	el camino mínimo.

Devuelve

el coste total del camino desde start hasta end.

Excepciones

bad_alloc

si no hay suficiente memoria

Ver también

get_min_parth

Hace referencia a Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::get_min_path() y Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::paint_partial_min_paths_tree().

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

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

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

Distance::Distance_Type Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::get_min_path ( typename GT::Node *  end, Path< GT > &  path  )

inline

Extrae un camino mínimo con destino en end sobre un grafo previamente pintado.

get_min_path() toma un grafo g sobre el cual están pintados los caminos mínimos (total o parcial) mediante llamadas previas a paint_min_paths_tree() o paint_partial_min_paths_tree() y extrae el camino mínimo hacia end guardándolo en path.

El resultado es indeterminado si end no está contenido dentro del grafo; es decir, se llamó previamente a paint_partial_min_paths_tree() con un nodo destino distinto a end y el resultado no contiene a end.

Una llamada previa a paint_min_paths_tree() o paint_partial_min_paths_tree() almacena el grafo y nodo origen.

Parámetros

[in]	end	nodo destino del camino.
[out]	path	camino donde se guardará el mínimo.

Excepciones

bad_alloc	sino hay suficiente memoria.
domain_error	si el grafo no ha sido previamente pintado mediante paint_min_paths_tree() o paint_partial_min_paths_tree().

Referenciado por Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::find_min_path().

Gráfico de llamadas a esta función:

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

Distance::Distance_Type Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::get_min_path ( GT &  tree, typename GT::Node *  end, Path< GT > &  path  )

inline

Extrae un camino mínimo con destino en end sobre un árbol de caminos mínimos previamente calculado.

get_min_path() toma un árbol tree, previamente construido mediante compute_min_paths_tree() o compute_partial_min_paths_tree() y extrae el camino mínimo hacia end guardándolo en path.

El resultado es indeterminado si end no está contenido dentro del árbol; es decir, se llamó previamente a compute_partial_min_paths_tree() con un nodo destino distinto a end y el resultado no contiene a end.

Parámetros

[in]	tree	árbol de caminos mínimos el cual debe haber sido previamente calculado mediante compute_min_paths_tree() o compute_partial_min_paths_tree().
[in]	end	nodo destino del camino.
[out]	path	camino donde se guardará el mínimo.

Excepciones

bad_alloc	sino hay suficiente memoria.
domain_error	si el grafo no ha sido previamente pintado mediante paint_min_paths_tree() o paint_partial_min_paths_tree().

Hace referencia a Aleph::Path< GT >::append(), Aleph::Path< GT >::clear_path(), Aleph::Path< GT >::Iterator::get_current_node(), Aleph::Path< GT >::init() y Aleph::DynDlist< T >::Iterator::next().

Gráfico de llamadas para esta función:

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

void Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::operator() ( GT &  g, typename GT::Node *  s, GT &  tree  )

inline

Calcula el árbol abarcador de todos los caminos mínimos desde un nodo dado según el algoritmo de Dijkstra.

El árbol abarcador tree de todos los caminos mínimos resultante start_node está completamente mapeado con g. Por tanto, una búsqueda de camino en profundidad, mediante Find_Path_Depth_First, sobre tree encontrará y construirá cualquier camino mínimo desde start_node hasta un nodo cualquiera.

Parámetros

[in]	g	el grafo al cual se desea calcular el árbol abarcador mínimo.
[in]	s	nodo inicio de los caminos mínimos.
[out]	tree	el grafo donde se desea guardar el árbol abarcador resultado de todos los caminos mínimos que parten desde el nodo start_node. Este grafo es limpiado antes del comienzo del algoritmo.

Excepciones

bad_alloc

si no hay suficiente memoria para construir tree; bien sea porque falla tree o por la cola interna. En este caso el valor de tree es indeterminado y no está limpio.

Hace referencia a Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::compute_min_paths_tree().

Gráfico de llamadas para esta función:

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

void Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::paint_min_paths_tree ( GT &  g, typename GT::Node *  start  )

inline

Pinta sobre el grafo g el árbol de todos caminos mínimos que comienzan desde start.

Parámetros

[in]	g	el grafo.
[in]	start	el nodo inicio del camino mínimo.

Excepciones

bad_alloc

si no hay suficiente memoria.

Hace referencia a ARC_BITS, IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next() y NODE_BITS.

Gráfico de llamadas para esta función:

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

void Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::paint_partial_min_paths_tree ( GT &  g, typename GT::Node *  start, typename GT::Node *  end  )

inline

Pinta sobre el grafo g el árbol parcial de caminos mínimos que comienzan desde start y se detiene cuando se encuentra el nodo end.

Parámetros

[in]	g	el grafo.
[in]	start	el nodo inicio del camino mínimo.
[in]	end	el nodo final del camino mínimo.

Excepciones

bad_alloc

si no hay suficiente memoria.

Hace referencia a ARC_BITS, IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next() y NODE_BITS.

Referenciado por Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::find_min_path().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

---

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

• Dijkstra.H