Aleph::Is_Graph_Acyclique< GT, SA > Class Template Reference

#include <tpl_test_acyclique.H>

Public Member Functions
	Is_Graph_Acyclique (SA &&__sa=SA())
	Is_Graph_Acyclique (SA &__sa)
bool	operator() (GT &g, size_t num_arcs)
bool	operator() (GT &g)

Detailed Description

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.

Member Function Documentation

operator()() [1/2]

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.

Parameters

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

Returns

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

Note

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.

operator()() [2/2]

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.

Parameters

[in]

g

el grafo a probar.

Returns

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

Note

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.

---

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

• tpl_test_acyclique.H