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

#include <Bellman_Ford.H>

Métodos públicos
bool	operator() (GT &g, typename GT::Node *s, Path< GT > &path) const
bool	operator() (GT &g, typename GT::Node *s, GT &tree, Path< GT > &path) const
bool	operator() (GT &g, Path< GT > &cycle) const

Descripción detallada

template<class GT, class Distance, class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>
class Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Compare, Plus, SA >

Detecta si existe un ciclo negativo y eventualmente lo calcula.

Esta clase toma un digrafo y un nodo destino, ejecuta el algoritmo de Bellman-Ford y si se detecta un ciclo negativo entonces lo almacena en un camino.

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

Documentación de las funciones miembro

template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>

bool Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Compare, Plus, SA >::operator() ( GT &  g, typename GT::Node *  s, Path< GT > &  path  ) const

inline

Invoca a la detección y cálculo de ciclo negativo.

Parámetros

[in]	g	el grafo.
[in]	s	el nodo inicio.
[out]	path	el camino donde se guarda el ciclo en caso de que se detecte ciclo negativo.

Devuelve

true si existe un ciclo negativo; false de lo contrario.

Excepciones

bad_alloc

si no hay suficiente memoria.

template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>

bool Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Compare, Plus, SA >::operator() ( GT &  g, typename GT::Node *  s, GT &  tree, Path< GT > &  path  ) const

inline

Invoca a la búsqueda de todos los caminos mínimos desde un nodo dado o a la detección y cálculo de ciclo negativo.

Parámetros

[in]	g	el grafo.
[in]	s	el nodo inicio.
[out]	tree	el árbol abarcador de todos los caminos mínimo que parten desde s.
[out]	path	el camino donde se guarda el ciclo en caso de que se detecte ciclo negativo.

Devuelve

true si existe un ciclo negativo; false de lo contrario.

Excepciones

bad_alloc

si no hay suficiente memoria.

template<class GT , class Distance , class Compare = Aleph::less<typename Distance::Distance_Type>, class Plus = Aleph::plus<typename Distance::Distance_Type>, class SA = Dft_Show_Arc<GT>>

bool Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Compare, Plus, SA >::operator() ( GT &  g, Path< GT > &  cycle  ) const

inline

Verifica si en el digrafo g existe un ciclo negativo mediante el algoritmo de Bellman-Ford.

Esta operación primero calcula los componentes fuertemente conexos del digrafo.Luego, sobre cada uno de ellos (con 2 o más nodos), se ejecuta el algoritmo de Bellman-Ford en búsqueda de un ciclo negativo. Si se encuentra un ciclo negativo, entonces el proceso se detiene, el ciclo se guarda en el parámetro cycle, y se retorna true. Si, por el contrario, se recorren todos los componentes fuertemente conexos si encontrar un ciclo negativo, entonces se retorna false.

Parámetros

[in]	g	el grafo.
[out]	cycle	el camino donde se guarda el ciclo en caso de que se detecte ciclo negativo.

Devuelve

true si existe un ciclo negativo; false de lo contrario.

Excepciones

bad_alloc

si no hay suficiente memoria.

---

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

• Bellman_Ford.H