Aleph::Tarjan_Connected_Components< GT, Itor, SA > Class Template Reference

#include <Tarjan.H>

Public Member Functions
	Tarjan_Connected_Components (SA __sa=SA()) noexcept(std::is_nothrow_move_assignable< SA >::value)
void	connected_components (const GT &g, DynList< GT > &blk_list, DynList< typename GT::Arc *> &arc_list)
void	connected_components (const GT &g, DynList< DynList< typename GT::Node *>> &blks)
DynList< DynList< typename GT::Node * > >	connected_components (const GT &g)
void	connected_components (const GT &g, DynList< size_t > &blks)
void	operator() (const GT &g, DynList< GT > &blk_list, DynList< typename GT::Arc *> &arc_list)
void	operator() (const GT &g, DynList< DynList< typename GT::Node *>> &blks)
DynDlist< DynDlist< typename GT::Node * > >	operator() (const GT &g)
void	operator() (const GT &g, DynDlist< GT > &blk_list, DynDlist< typename GT::Arc *> &arc_list)
void	operator() (const GT &g, DynDlist< DynDlist< typename GT::Node *>> &blks)
bool	has_cycle (const GT &g)
	Retorna true si el digrafo g contiene al menos un ciclo.
bool	is_dag (const GT &g)
	Retorna true si el grafo dirigido es acíclico.
bool	compute_cycle (const GT &g, Path< GT > &path)
bool	compute_cycle (const GT &g, typename GT::Node *src, Path< GT > &path)
bool	test_connectivity (const GT &g)

Detailed Description

template<class GT, template< typename, class > class Itor = Out_Iterator, class SA = Dft_Show_Arc<GT>>
class Aleph::Tarjan_Connected_Components< GT, Itor, SA >

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:

1. GT: la clase digrafo.
2. SA: el filtro de arcos que emplea el iterador interno.

Member Function Documentation

connected_components() [1/3]

template<class GT, template< typename, class > class Itor = Out_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components ( const GT &  g, DynList< GT > &  blk_list, DynList< typename GT::Arc *> &  arc_list  )

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.

Parameters

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

Exceptions

bad_alloc

si no hay memoria para construir algún bloque o insertar en la lista.

See also

copy_graph()

Here is the caller graph for this function:

connected_components() [2/3]

template<class GT, template< typename, class > class Itor = Out_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components ( const GT &  g, DynList< DynList< typename GT::Node *>> &  blks  )

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.

Parameters

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

Exceptions

bad_alloc

si no hay memoria para insertar en la lista.

See also

copy_graph()

connected_components() [3/3]

template<class GT, template< typename, class > class Itor = Out_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::connected_components ( const GT &  g, DynList< size_t > &  blks  )

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.

Parameters

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

Exceptions

bad_alloc

si no hay memoria para insertar en la lista.

See also

copy_graph()

operator()() [1/4]

template<class GT, template< typename, class > class Itor = Out_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator() ( const GT &  g, DynList< GT > &  blk_list, DynList< typename GT::Arc *> &  arc_list  )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Here is the call graph for this function:

Here is the caller graph for this function:

operator()() [2/4]

template<class GT, template< typename, class > class Itor = Out_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator() ( const GT &  g, DynList< DynList< typename GT::Node *>> &  blks  )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Here is the call graph for this function:

operator()() [3/4]

template<class GT, template< typename, class > class Itor = Out_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator() ( const GT &  g, DynDlist< GT > &  blk_list, DynDlist< typename GT::Arc *> &  arc_list  )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Here is the call graph for this function:

operator()() [4/4]

template<class GT, template< typename, class > class Itor = Out_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator() ( const GT &  g, DynDlist< DynDlist< typename GT::Node *>> &  blks  )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Here is the call graph for this function:

---

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

• Tarjan.H