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

#include <tpl_test_acyclique.H>

Métodos públicos
	Is_Graph_Acyclique (SA &&__sa=SA())
	Is_Graph_Acyclique (SA &__sa)
bool	operator() (GT &g, size_t num_arcs)
bool	operator() (GT &g)

Descripción detallada

template<class GT, class SA = Dft_Show_Arc<GT>>
class Aleph::Is_Graph_Acyclique< GT, SA >

Determina si un grafo es o no acíclico (no contiene ciclos).

Is_Graph_Acyclique explora en profundidad en grafo g, a partir de un nodo y verifica si el grafo es acíclico; es decir, que no contenga ningún ciclo.

La clase toma dos parámetros tipo:

1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido.

La clase usa el bit is_acyclique y lo reinicia al principio del algoritmo para marcar los nodos y arcos ya visitados.

Documentación de las funciones miembro

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

bool Aleph::Is_Graph_Acyclique< GT, SA >::operator() ( GT &  g, size_t  num_arcs  )

inline

Invoca a la prueba de aciclicidad.

Si g es un grafo (no un digrafo) entonces el algoritmo compara la cantidad de arcos con la de nodos. Si el grafo tiene menos arcos que nodos, entonces se concluye que el grafo es acíclico. Consecuentemente, esta técnica no opera para multigrafos.

Parámetros

[in]	g	el grafo a probar.
	num_arcs	cantidad de arcos que tiene g. Use este valor si está empleando iteradores filtros sobre arcos pintados o interpretados según un criterio dado. De este modo, la rutina conoce la cantidad de arcos que que cumplen el criterio.

Devuelve

true si el grafo no contiene ningún ciclo; false de lo contrario.

Nota

Debido a la prueba inicial con la cantidad de arcos, esta rutina es preferible que test_for_cycle(), aún bajo el conocimiento de que el grafo es conexo, pues esta última rutina siempre realiza la exploración en profundidad, mientras que is_graph_acyclique() no.

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

bool Aleph::Is_Graph_Acyclique< GT, SA >::operator() ( GT &  g )

inline

Invoca a la prueba de aciclicidad.

Si g es un grafo (no un digrafo) entonces el algoritmo compara la cantidad de arcos con la de nodos. Si el grafo tiene menos arcos que nodos, entonces se concluye que el grafo es acíclico. Consecuentemente, esta técnica no opera para multigrafos.

Parámetros

[in]

g

el grafo a probar.

Devuelve

true si el grafo no contiene ningún ciclo; false de lo contrario.

Nota

Debido a la prueba inicial con la cantidad de arcos, esta rutina es preferible que test_for_cycle(), aún bajo el conocimiento de que el grafo es conexo, pues esta última rutina siempre realiza la exploración en profundidad, mientras que is_graph_acyclique() no.

---

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

• tpl_test_acyclique.H