Referencia de la plantilla de la Clase Aleph::Search_Cycle< GT >

#include <Bellman_Ford.H>

Métodos públicos
bool	operator() (GT &g, DynArray< typename GT::Node * > &pred, DynArray< typename GT::Arc * > &arcs, Path< GT > &cycle) const

Descripción detallada

template<class GT>
class Aleph::Search_Cycle< GT >

Busca un ciclo negativo según los resultados parciales de algoritmo de Bellman-Ford.

Durante la ejecución del algoritmo de Bellman-Ford para el cálculo de un árbol abarcador de todos los caminos mínimo, se emplean dos arreglos, uno de nodos y otros de arcos.

La clase Search_Cycle examina los arreglos empleados por el algoritmo de Bellman-Ford y determina si el grafo contiene o no.

Eventualmente la clase puede emplearse, independientemente del algoritmo de Bellman-Ford, sobre los arreglos (a condición de que sean válidos) para detectar si existe o no un ciclo y calcularlo.

Ver también

bellman_ford_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Documentación de las funciones miembro

template<class GT >

bool Aleph::Search_Cycle< GT >::operator() ( GT &  g, DynArray< typename GT::Node * > &  pred, DynArray< typename GT::Arc * > &  arcs, Path< GT > &  cycle  ) const

inline

Invoca al cálculo del ciclo sobre un grafo.

Parámetros

[in]	g	el grafo sobre el cual se calcula un árbol abarcador de todos los caminos mínimos.
[in]	pred	arreglo de nodos padre del árbol abarcador.
[in]	arcs	arreglo de arcos que conforman el árbol abarcador.
[out]	cycle	un ciclo negativo contenido en g. El valor de cycle sólo tiene sentido si el grafo en efecto contiene un ciclo.

Devuelve

true si el grafo contiene un ciclo negativo; false de lo contrario.

Excepciones

bad_alloc

si no hay suficiente memoria para construir las estructuras alternas de cálculo.

Nota

Los arreglos pred y arcs deben corresponderse a los generados por cualquiera de las rutinas de caminos mínimos basadas en el algoritmo de Bellman-Ford.

---

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

• Bellman_Ford.H