Aleph-w  1.5a.2
Biblioteca general de algoritmos y estructuras de datos
 Todo Clases Archivos Funciones Variables 'typedefs' Enumeraciones Amigas Grupos Páginas
Métodos públicos | Lista de todos los miembros
Referencia de la plantilla de la Clase Aleph::Kosaraju_Connected_Components< GT, SA >
Grafos.

#include <kosaraju.H>

Métodos públicos

void operator() (GT &g, DynDlist< GT > &blk_list, DynDlist< typename GT::Arc * > &arc_list)
 
void operator() (GT &g, DynDlist< DynDlist< typename GT::Node * > > &list)
 

Descripción detallada

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

Calcula los componentes fuertemente conexos de un grafo según el algoritmo de Kosaraju.

Kosaraju_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 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 clase se basa en el algoritmo de Kosaraju.

La función emplea dos parámetros tipo:

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

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.

Ver también
Tarjan_Connected_Components()

Documentación de las funciones miembro

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::Kosaraju_Connected_Components< GT, SA >::operator() ( GT &  g,
DynDlist< GT > &  blk_list,
DynDlist< typename GT::Arc * > &  arc_list 
)
inline

Calcula los componentes fuertemente conexos de un grafo según el algoritmo de Kosaraju.

Parámetros
[in]gel grafo.
[out]blk_listlista de sub-grafos mapeados a g correspondiente a los componentes fuertemente conexos de g.
[out]arc_listlista de arcos de cruce entre los componentes.
template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::Kosaraju_Connected_Components< GT, SA >::operator() ( GT &  g,
DynDlist< DynDlist< typename GT::Node * > > &  list 
)
inline

Calcula los componentes fuertemente conexos de un grafo según el algoritmo de Kosaraju.

Parámetros
[in]gel grafo.
[out]listlista de listas de nodos que conforman los componentes. Cada lista es una listas de los nodos del componente.
La documentación para esta clase fue generada a partir del siguiente fichero:
Leandro Rabindranath León