 |
Aleph-w
1.5a.2
Biblioteca general de algoritmos y estructuras de datos
|
|
|
Aleph-w
1.5a.2
Biblioteca general de algoritmos y estructuras de datos
|
|
#include <Tarjan.H>
Métodos públicos | |
| Tarjan_Connected_Components (SA &&__sa=SA()) | |
| Tarjan_Connected_Components (SA &__sa) | |
| void | connected_components (GT &g, DynList< GT > &blk_list, DynList< typename GT::Arc * > &arc_list) |
| void | connected_components (GT &g, DynList< DynList< typename GT::Node * >> &blks) |
| void | connected_components (GT &g, DynList< size_t > &blks) |
| void | operator() (GT &g, DynList< GT > &blk_list, DynList< typename GT::Arc * > &arc_list) |
| void | operator() (GT &g, DynList< DynList< typename GT::Node * >> &blks) |
| void | operator() (GT &g, DynDlist< GT > &blk_list, DynDlist< typename GT::Arc * > &arc_list) |
| void | operator() (GT &g, DynDlist< DynDlist< typename GT::Node * >> &blks) |
| bool | has_cycle (GT &g) |
| Retorna true si el digrafo g contiene al menos un ciclo. | |
| bool | is_dag (GT &g) |
| Retorna true si el grafo dirigido es acíclico. | |
| bool | compute_cycle (GT &g, Path< GT > &path) |
| bool | test_connectivity (GT &g) |
Operaciones sobre componentes fuertemente conexos de un digrafo empleando el algoritmo de Tarjan para el cálculo de los componentes fuertemente conexos de un grafo.
La clase emplea dos parámetros tipo:
|
inline |
Calcula los componentes fuertemente conexos de un digrafo.
connected_components() toma un digrafo g, "supuestamente débilmente conexo", calcula sus subgrafos o componentes inconexos y los almacena en una lista dinámica blk_list de subdigrafos mapeados, tanto en los nodos como en los arcos. El énfasis en el supuesto carácter conexo del grafo se debe a que si el grafo no fuese conexo, entonces la lista resultante contendría un solo elemento correspondiente al digrafo copia mapeado de g. Si este fuese el caso, entonces es preferible hacerlo con la función copy_graph().
La función se basa en el algoritmo de Tarjan.
La función se vale del bit build_subtree para marcar nodos y arcos visitados.
El algoritmo internamente descubre los componentes mediante búsquedas en profundidad.
| [in] | g | el grafo sobre el cual se desea calcular sus bloques. |
| [out] | blk_list | lista de subgrafos mapeados a g con los subgrafos o componentes inconexos de g. |
| [out] | arc_list | lista de arcos que conectan a los bloques. |
| bad_alloc | si no hay memoria para construir algún bloque o insertar en la lista. |
Hace referencia a Aleph::DynList< T >::append(), IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next() y NODE_COUNTER.
Referenciado por Aleph::Tarjan_Connected_Components< GT, SA >::operator()().
Gráfico de llamadas para esta función: Gráfico de llamadas a esta función:
|
inline |
Calcula los componentes fuertemente conexos de un digrafo.
Esta versión sobrecargada connected_components() toma un digrafo g, "supuestamente débilmente conexo", calcula sus subgrafos o componentes inconexos y los almacena en una lista dinámica list de listas de nodos.
Cada lista contiene los nodos que pertenecen al componente fuertemente conexo.
Úsese esta función si no es necesario obtener copias mapeadas de los componentes fuertemente conexos.
La función se basa en el algoritmo de Tarjan.
La función se vale del bit build_subtree para marcar nodos y arcos visitados.
El algoritmo internamente descubre los componentes mediante búsquedas en profundidad.
Puesto que se ahorra el mapeo, esta rutina es más rápida y menos onerosa en memoria que la versión anterior. La desventaja quizá es que no calcula los posibles arcos que podrían interconectar un bloque en un solo sentido.
| [in] | g | el grafo sobre el cual se desea calcular sus bloques. |
| [out] | blks | lista de listas de nodos. Cada lista contiene los nodos que conforman un componente conexo. |
| bad_alloc | si no hay memoria para insertar en la lista. |
Hace referencia a IS_NODE_VISITED.
|
inline |
Calcula los componentes fuertemente conexos de un digrafo.
Esta versión sobrecargada connected_components() toma un digrafo g, "supuestamente débilmente conexo" y cuenta sus subgrafos o componentes inconexos junto con sus tamaños.
La función se basa en el algoritmo de Tarjan.
La función se vale del bit build_subtree para marcar nodos y arcos visitados.
El algoritmo internamente descubre los componentes mediante búsquedas en profundidad.
| [in] | g | el grafo sobre el cual se desea calcular sus bloques. |
| [out] | blks | lista de enteros positivos. Cada lista contiene el tamaño de un componente conexo distinto. |
| bad_alloc | si no hay memoria para insertar en la lista. |
Hace referencia a IS_NODE_VISITED.
|
inline |
Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.
Hace referencia a Aleph::Tarjan_Connected_Components< GT, SA >::connected_components().
Gráfico de llamadas para esta función:
|
inline |
Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.
Hace referencia a Aleph::Tarjan_Connected_Components< GT, SA >::connected_components().
Gráfico de llamadas para esta función:
|
inline |
Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.
Hace referencia a Aleph::DynDlist< T >::append() y Aleph::Tarjan_Connected_Components< GT, SA >::connected_components().
Gráfico de llamadas para esta función:
|
inline |
Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.
Hace referencia a Aleph::DynDlist< T >::append(), Aleph::Tarjan_Connected_Components< GT, SA >::connected_components(), Aleph::HTList::is_empty() y Aleph::DynList< T >::remove_first().
Gráfico de llamadas para esta función:
