#include <tpl_cut_nodes.H>

Métodos públicos
void	cut_nodes (typename GT::Node start, DynDlist< typename GT::Node > &list)

	Compute_Cut_Nodes (GT &g, SA &&__sa=SA())

	Compute_Cut_Nodes (GT &g, SA &__sa)

void	operator() (DynDlist< typename GT::Node * > &list)

void	operator() (typename GT::Node start, DynDlist< typename GT::Node > &list)

long	paint_subgraphs ()

void	map_subgraph (GT &sg, const long &color)

void	map_cut_graph (GT &cut_graph, DynDlist< typename GT::Arc * > &cross_arc_list)

void	compute_blocks (DynDlist< GT > &block_list, GT &cut_graph, DynDlist< typename GT::Arc * > &cross_arc_list)

Descripción detallada

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

Cálculo de los puntos de corte de un grafo.

La clase Compute_Cut_Nodes se encarga de calcular todolo relacionado a los nodes de corte de un grafo conexo. Para ello efectúa un recorrido en profundidad a partir de un nodo dado y añade a una lista dinámica cada nodo de corte que contenga el grafo.

La lista dinámica es provista por el usuario.

Un nodo de corte se define como un nodo tal que al suprimirlo (juntos con sus arcos) el grafo deviene inconexo.

El algoritmo utiliza el bit Depth_First para marcar los nodos y arcos que han sido visitados. También, para construir copias mapeadas de componentes conexos en torno a un punto de corte, de emplea el bit Build_Subtree.

Esta clase también provee métodos para "pintar" los diversos bloques que separarían los puntos de corte, así como para obtener copias mapeadas de los componentes conexos en torno a los puntos de corte, el grafo de corte y los arcos de cruce.

Se asume que g es conexo y no se realiza ninguna verificación al respecto.

Los parámetros tipo de la clase son:

GT: el grafo.
SA: el filtro de arcos para los iteradores de arcos.

Nota: Si se requiere calcular el grafo de corte, mediante el método map_cut_graph(), entonces la clase filtro de arcos debe sobrecargar el operador () (GT&, GT::Arc*).

Esta clase exporta varias operaciones con dependencia secuencial:

cut_nodes(): la cual calcula los nodos de corte y los introcuce en una lista. El operador () sobre la clase es sinónimo de este método.
paint_subgraphs(): "pinta" los distintos componentes del grafo en torno a los puntos de corte previamente calculados. La rutina retorna la cantidad de colores, uno por cada componente, que tenga el grafo. Los colores son colocados en los contadores asociados por cada nodo.
map_subgraph(): obtiene una copia mapeada de un componente conexo asociado a un color dado.
map_cut_graph(); obtiene una copia mapeada del "grafo de corte"; o sea, aquel sólo conformado por los nodos de corte del grafo. Este método también calcula los arcos de cruce (los que conectan a un punto de corte con un bloque conexo).

En caso de que se desea ejecutar todo a la vez, se provee el método compute_blocks(), el cual calcula los puntos de corte, pinta los componentes y calcula las copias mapeadas de los componentes conexos así como los arcos de cruce.

Documentación del constructor y destructor

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

Aleph::Compute_Cut_Nodes< GT, SA >::Compute_Cut_Nodes	(	GT &	g,
		SA &&	__sa = `SA()`
	)

inline

Constructor de calculador de nodos de corte.

Parámetros

[in]	g	el grafo al cual se desea calcular los puntos de corte.
[in]	__sa	el filtro de arcos para los oiteradores sobre arcos.

Documentación de las funciones miembro

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

void Aleph::Compute_Cut_Nodes< GT, SA >::compute_blocks	(	DynDlist< GT > &	block_list,
		GT &	cut_graph,
		DynDlist< typename GT::Arc * > &	cross_arc_list
	)

inline

Construye grafos mapeados en torno a los puntos de corte de un grafo.

Esta rutina toma una lista de puntos de corte previamente calculada y construye en una sola pasada sobre los nodos copias mapeadas de los componentes conexos en torno a los puntos de corte así como el grafo de corte. Luego, se realiza una pasada sobre los arcos en la cual se determinan los arcos de cruce.

Si se requieren calcular todos los grafos mapeados y el grafo de corte, entonces el uso de esta rutina es mucho más eficiente que llamadas separadas a map_subgraph() y map_cut_graph().

Parámetros

[out]	block_list	lista de grafos donde se guardarán las copias mapeadas de los componentes conexos
[out]	cut_graph	el grafo mapeado de corte
[out]	lista	de arcos de cruce.

Excepciones

bad_alloc	si no hay suficiente memoria.
logic_error	si los nodos de corte no han sido previamente calculados.

Hace referencia a Aleph::DynArray< T >::access(), Aleph::DynDlist< T >::append(), IS_NODE_VISITED, Aleph::Compute_Cut_Nodes< GT, SA >::map_cut_graph(), Aleph::Compute_Cut_Nodes< GT, SA >::paint_subgraphs() y Aleph::DynArray< T >::reserve().

Gráfico de llamadas para esta función:

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

void Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes	(	typename GT::Node *	start,
		DynDlist< typename GT::Node * > &	list
	)

inline

Calcula los puntos de corte.

Parámetros

[in]	start	nodo inicio desde donde se desea iniciar el cálculo.
[out]	list	lista dinámica donde se guardan punteros a nodos de corte del grafo.

Excepciones

bad_alloc si no hay memoria para insertar en la lista dinámica o si no hay memoria para los datos de cálculo interno del algoritmo.

La lista debe ser provista por el usario y se vacía al inicio del cálculo.

Hace referencia a Aleph::DynDlist< T >::append(), ARC_BITS, Aleph::DynDlist< T >::empty(), IS_ARC_VISITED, IS_NODE_VISITED y NODE_BITS.

Gráfico de llamadas para esta función:

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

void Aleph::Compute_Cut_Nodes< GT, SA >::map_cut_graph	(	GT &	cut_graph,
		DynDlist< typename GT::Arc * > &	cross_arc_list
	)

inline

Calcula el grafo mapeado de corte de un grafo.

El grafo de corte de corte de un grafo es aquel sólo compuesto por los nodos de corte.

También se calculan los arcos de cruce; es decir, aquellos que conectan a puntos de corte con componentes conexos.

La idea de este algoritmo es que usado en combinación con map_subgraph() se puedan obtener desde la copias mapeadas el grafo original.

Parámetros

[out]	cut_graph	el grafo de corte
[out]	cross_arc_list	la lista de arcos de cruce; es decir, los arcos que van desde un nodo de corte hacia un componente conoxo. Estos arcos no pertenecen al grafo de corte.

Excepciones

logic_error si el grafo no ha sido previamente pintado.

Hace referencia a Aleph::DynDlist< T >::append(), Aleph::clear_graph() y Aleph::Filter_Iterator< Container, It, Show_Item >::next().

Referenciado por Aleph::Compute_Cut_Nodes< GT, SA >::compute_blocks().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

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

void Aleph::Compute_Cut_Nodes< GT, SA >::map_subgraph	(	GT &	sg,
		const long &	color
	)

inline

Obtiene una copia mapeada del componente de color.

map_subgraph() extrae del grafo el componente con color color y construye una grafo mapeado en sg.

Parámetros

[out]	sg	el grafo donde se desea obtener la copia mapeada.
[in]	el	color que se desea extraer.

Excepciones

logic_error	si el grafo no está pintado.
domain_error	si no hay ningún componente con el color dado.

Hace referencia a Aleph::clear_graph().

Gráfico de llamadas para esta función:

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

void Aleph::Compute_Cut_Nodes< GT, SA >::operator() ( DynDlist< typename GT::Node * > & list )

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.

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

void Aleph::Compute_Cut_Nodes< GT, SA >::operator()	(	typename GT::Node *	start,
		DynDlist< typename GT::Node * > &	list
	)

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.

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

long Aleph::Compute_Cut_Nodes< GT, SA >::paint_subgraphs ( )

inline

Pinta los componentes conexos en torno a los puntos de corte.

paint_subgraphs() pinta los componentes conexos en torno a los puntos de corte de un grafo.

La rutina requiere que ante se haya invocado al método cut_nodes().

Los "colores" de cada componente son colocados en atributo NODE_COUNTER de cada nodo y arco. El primer color comienza en el valor 1.

Úsese esta rutina si no es necesario o es suficiente con obtener los componentes mediante los colores de los bloques. Esto ahorra el cálculo y la memoria de tener que crear nuevos grafos.

Devuelve: la cantidad de componentes; que es la cantidad de colores.

Excepciones

std::logic_error si el cálculo de los puntos de corte no ha sido previamente invocado.

Referenciado por Aleph::Compute_Cut_Nodes< GT, SA >::compute_blocks().

Gráfico de llamadas a esta función:

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

tpl_cut_nodes.H

Métodos públicos

Descripción detallada

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

Documentación del constructor y destructor

Documentación de las funciones miembro

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