Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA > Class Template Reference

Spanning tree calculation of all shortest paths from a given node according to Dijkstra's algorithm. More...

#include <Dijkstra.H>

Classes
struct	Total
	Clase totalizadora de distancias. More...

Public Member Functions
	Dijkstra_Min_Paths (Distance dist=Distance(), SA __sa=SA()) noexcept(std::is_nothrow_move_assignable< SA >::value)
GT::Node *	compute_min_paths_tree (const GT &g, typename GT::Node *start, GT &tree)
void	compute_partial_min_paths_tree (const GT &g, typename GT::Node *start, typename GT::Node *end, GT &tree)
bool	paint_partial_min_paths_tree (const GT &g, typename GT::Node *start, typename GT::Node *end)
void	paint_min_paths_tree (const 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 (const GT &g, typename GT::Node *start, typename GT::Node *end, Path< GT > &min_path)
void	operator() (const GT &g, typename GT::Node *s, GT &tree)
Distance::Distance_Type	copy_painted_min_paths_tree (const GT &g, GT &tree)
Distance::Distance_Type	operator() (const GT &g, typename GT::Node *s, typename GT::Node *e, Path< GT > &path)
	find_min_path()
Distance::Distance_Type	get_min_path (const GT &tree, typename GT::Node *end, Path< GT > &path)

Detailed Description

template<class GT, class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
class Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA >

Spanning tree calculation of all shortest paths from a given node according to Dijkstra's algorithm.

This class handles Dijkstra's algorithm to compute a tree containing of all shortest paths from a node s of a graph g.

The algorithm uses an internal queue whose length is proportional to the number of nodes in the graph.

Dijkstra's algorithm does not work for graphs with negative weights.

The class receives the following template parameters:

1. GT: graph type.
2. Distance <GT>: class reading the weight. It should export the following attributes:
   1. typedef Distance<GT>::Distance_Type: Data type. It represents a weight on an arc
   2. Distance <GT> Distance_Type :: operator () (typename GT :: Arc * a): that returns the value of the peso in the bow
3. SA: Arcs filter for internal iterator

See also

Find_Path_Depth_First Floyd_All_Shortest_Paths Bellman_Ford_Min_Spanning_Tree

Constructor & Destructor Documentation

Dijkstra_Min_Paths()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA >::Dijkstra_Min_Paths ( Distance  dist = Distance(), SA  __sa = SA()  )

inlinenoexcept

Constructor

Parameters

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

Member Function Documentation

compute_min_paths_tree()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

GT::Node* Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA >::compute_min_paths_tree ( const 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.

Parameters

[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.

Exceptions

bad_alloc

si no hay suficiente memoria

Here is the call graph for this function:

Here is the caller graph for this function:

compute_partial_min_paths_tree()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA >::compute_partial_min_paths_tree ( const 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.

Parameters

[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.

Exceptions

bad_alloc

si no hay suficiente memoria

Here is the call graph for this function:

copy_painted_min_paths_tree()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance::Distance_Type Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA >::copy_painted_min_paths_tree ( const 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.

Parameters

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

Exceptions

bad_alloc

si no hay suficiente memoria.

find_min_path()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance::Distance_Type Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA >::find_min_path ( const 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.

Parameters

[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.

Returns

el coste total del camino desde start hasta end.

Exceptions

bad_alloc

si no hay suficiente memoria

See also

get_min_parth

Here is the call graph for this function:

Here is the caller graph for this function:

get_min_path() [1/2]

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance::Distance_Type Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, 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.

Parameters

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

Exceptions

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

Here is the caller graph for this function:

get_min_path() [2/2]

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance::Distance_Type Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA >::get_min_path ( const 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.

Parameters

[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.

Exceptions

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

Here is the call graph for this function:

operator()()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA >::operator() ( const 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.

Parameters

[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.

Exceptions

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.

Here is the call graph for this function:

paint_min_paths_tree()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

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

inline

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

Parameters

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

Exceptions

bad_alloc

si no hay suficiente memoria.

paint_partial_min_paths_tree()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

bool Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA >::paint_partial_min_paths_tree ( const 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.

Parameters

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

Exceptions

bad_alloc

si no hay suficiente memoria.

Here is the caller graph for this function:

---

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

• Dijkstra.H