#include <tpl_matgraph.H>

Tipos públicos
typedef GT	Graph_Type
	El tipo de grafo representado con listas de adyacencia.

typedef __Entry_Type	Entry_Type
	El tipo de dato que alberga la matriz.

typedef GT::Node_Type	Node_Type

typedef GT::Arc_Type	Arc_Type

typedef GT::Node	Node
	El tipo de nodo usado en la representación con listas de adyacencia.

typedef GT::Arc	Arc
	El tipo de arco usado en la representación con listas de adyacencia.

Métodos públicos
Node *	operator() (const long &i)

long	operator() (Node *node) const

Entry_Type &	operator() (const long &i, const long &j)

const Entry_Type &	operator() (const long &i, const long &j) const

Entry_Type &	operator() (Node src, Node tgt)

const Entry_Type &	operator() (Node src, Node tgt) const

GT &	get_list_graph ()
	Retorna una referencia al grafo representado con lista de adyacencia.

const Entry_Type &	null_value () const
	Retorna el valor considerado como nulo.

const size_t &	get_num_nodes () const

	Ady_Mat (GT &g)

	Ady_Mat (GT &g, const Entry_Type &null)

void	set_null_value (const Entry_Type &null)
	Declara un valor nulo para la matriz de adyacencia auxiliar.

	Ady_Mat (Ady_Mat &mat)
	Constructor copia.

template<class Operation >
void	operate_all_arcs_list_graph ()

template<class Operation >
void	operate_all_arcs_list_graph (void *ptr)

template<class Operation >
void	operate_all_arcs_matrix ()

template<class Operation >
void	operate_all_arcs_matrix (void *ptr)

Descripción detallada

template<class GT, typename __Entry_Type, class SA = Dft_Show_Arc<GT>>
class Aleph::Ady_Mat< GT, __Entry_Type, SA >

Matriz de adyacencia auxiliar.

Muchas aplicaciones sobre grafos basadas en matrices de adyacencia utilizan información temporal, información de tipo distinto al guardado en los atributos del gafo o una parte de los atributos. En estas tres situaciones el uso del tipo Matriz_Graph o es muy restringido o imposible.

Para paliar la situación anterior, el tipo Ady_Mat define una matriz asociada a un grafo representado con listas de adyacencia pero cuyas entradas son de un tipo definido por el usuario.

Al igual que con otros tipos de matrices de adyacencia, Ady_Mat maneja el elemento nulo Ady_Mat::null_value(), pero en este caso no necesariamente representa presencia o ausencia de arco. Aún así, entradas cuyo valor sea Ady_Mat::null_value() tienden a no ocupar memoria.

Ady_Mat<GT,__Entry_Type> maneja dos parámetros tipo:

GT: el tipo de grafo representado con listas de adyacencia.
__Entry_Type: el tipo de dato a guardar en la matriz

Ver también: Matrix_Graph Map_Matrix_Graph

Documentación de los 'Typedef' miembros de la clase

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

typedef GT::Arc_Type Aleph::Ady_Mat< GT, __Entry_Type, SA >::Arc_Type

El tipo de dato que guardan los arcos en el grafo representado con listas de adyacencia.

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

typedef GT::Node_Type Aleph::Ady_Mat< GT, __Entry_Type, SA >::Node_Type

El tipo de dato que guardan los nodos en el grafo representado con listas de adyacencia.

Documentación del constructor y destructor

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

Aleph::Ady_Mat< GT, __Entry_Type, SA >::Ady_Mat ( GT & g )

inline

Constructor de matriz auxiliar a partir de un grafo representado con listas de adyacencia.

Este constructor toma un grafo g representado con listas de adyacencia y construye una matriz auxiliar cuyas entradas no están inicializadas.

Si se desea explícitamente ahorrar memoria por un elemento designado como valor nulo, entonces éste valor debe indicarse con la primitiva Ady_Mat::set_null_value().

Parámetros

[in] g el grafo representado con listas de adyacencia.

Excepciones

bad_alloc si no hay suficiente memoria.

Ver también: Ady_Mat::set_null_value() Ady_Mat::null_value()

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

Aleph::Ady_Mat< GT, __Entry_Type, SA >::Ady_Mat	(	GT &	g,
		const Entry_Type &	null
	)

inline

Constructor de matriz auxiliar a partir de un grafo representado con listas de adyacencia y con definición de valor nulo.

Este constructor toma un grafo g representado con listas de adyacencia, un valor nulo y construye una matriz auxiliar cuyas entradas no están inicializadas.

Un acceso a la entrada (i,j) retornará el valor Ady_Mat::null_value().

Parámetros

[in]	g	el grafo representado con listas de adyacencia.
[in]	null	el valor del elemento designado como nulo.

Excepciones

bad_alloc si no hay suficiente memoria.

Ver también: Ady_Mat::set_null_value() Ady_Mat::null_value()

Documentación de las funciones miembro

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

const size_t& Aleph::Ady_Mat< GT, __Entry_Type, SA >::get_num_nodes ( ) const

inline

Retorna la cantidad de nodos del grafo (o sea, la dimensión de la matriz).

template<class GT , typename __Entry_Type , class SA >

template<class Operation >

void Aleph::Ady_Mat< GT, __Entry_Type, SA >::operate_all_arcs_list_graph ( )

Efectúa una operación sobre la matriz auxiliar según cada arco del grafo representado con listas de adyacencia.

operate_all_arcs_list_graph() recorre los arcos del grafo representado con listas de adyacencia e invoca a la operación Operation()(mat, arc, i, j, entry) donde:

mat: es una referencia a la matrix sobre el cual se está realizando la operación.
arc: es un apuntador al arco dentro del GT asociado a la matriz.
i: es el índice del nodo origen en la matriz.
j: es el índice del nodo destino en la matriz.
entry: es una referencia al contenido de la entrada (i,j) en la matriz.

El uso de este método es principalmente para escribir los valores iniciales dentro de la matriz según los contenidos de los arcos en el grafo representado con listas de adyacencia.

Nótese que la operación sólo se ejecuta para las entradas que refieren a un arco. El resto de las entradas contiene el valor Ady_Mat::null_value() y probablemente no ocupen memoria.

Hace referencia a Aleph::Filter_Iterator< Container, It, Show_Item >::next() y Aleph::DynArray< T >::touch().

Gráfico de llamadas para esta función:

template<class GT , typename __Entry_Type , class SA >

template<class Operation >

void Aleph::Ady_Mat< GT, __Entry_Type, SA >::operate_all_arcs_list_graph ( void * ptr )

Efectúa una operación sobre la matriz auxiliar según cada arco del grafo representado con listas de adyacencia y le transmite a la operación un puntero opaco por donde enviar y recibir información.

operate_all_arcs_list_graph() recorre los arcos del grafo representado con listas de adyacencia e invoca a la operación Operation()(mat, arc, i, j, entry, ptr) donde:

mat: es una referencia a la matrix sobre el cual se está realizando la operación.
arc: es un apuntador al arco dentro del GT asociado a la matriz.
i: es el índice del nodo origen en la matriz.
j: es el índice del nodo destino en la matriz.
entry: es una referencia al contenido de la entrada (i,j) en la matriz.
ptr: puntero opaco.

El uso de este método es principalmente para escribir los valores iniciales dentro de la matriz según los contenidos de los arcos en el grafo representado con listas de adyacencia.

Nótese que la operación sólo se ejecuta para las entradas que refieren a un arco. El resto de las entradas contiene el valor Ady_Mat::null_value() y probablemente no ocupen memoria.

Parámetros

[in] ptr puntero a información opaca que se desea transmitir a la operación

Hace referencia a Aleph::Filter_Iterator< Container, It, Show_Item >::next() y Aleph::DynArray< T >::touch().

Gráfico de llamadas para esta función:

template<class GT , typename __Entry_Type , class SA >

template<class Operation >

void Aleph::Ady_Mat< GT, __Entry_Type, SA >::operate_all_arcs_matrix ( )

Efectúa una operación sobre todas las entradas de matriz auxiliar.

operate_all_arcs_matrix() recorre todas las entradas de matriz auxiliar e invoca una operación Operation()(mat,src,tgt,s,t,entry) cuyos parámetros se definen así:

mat: referencia a la matriz
src: puntero al nodo origen.
tgt: puntero al nodo destino.
s: índice del nodo origen.
t: índice del nodo destino.
entry: referencia a la entrada de la matriz.

Si se invoca este método, entonces la matriz ocupa el máximo de memoria, pues cada entrada debe ser escrita de modo tal que se garantice una referencia válida a mat(s,t).

Nótese que no hay acceso directo al arco en la representación con listas de adyacencia.

Hace referencia a Aleph::DynArray< T >::touch().

Gráfico de llamadas para esta función:

template<class GT , typename __Entry_Type , class SA >

template<class Operation >

void Aleph::Ady_Mat< GT, __Entry_Type, SA >::operate_all_arcs_matrix ( void * ptr )

Efectúa una operación sobre todas las entradas de matriz auxiliar con un puntero opaco por donde enviar o recibir información.

operate_all_arcs_matrix() recorre todas las entradas de matriz auxiliar e invoca una operación Operation()(mat,src,tgt,s,t,entry) cuyos parámetros se definen así:

mat: referencia a la matriz
src: puntero al nodo origen.
tgt: puntero al nodo destino.
s: índice del nodo origen.
t: índice del nodo destino.
entry: referencia a la entrada de la matriz.
ptr: puntero opaco a pasar a la operación.

Si se invoca este método, entonces la matriz ocupa el máximo de memoria, pues cada entrada debe ser escrita de modo tal que se garantice una referencia válida a mat(s,t).

Nótese que no hay acceso directo al arco en la representación con listas de adyacencia.

Parámetros

[in] ptr puntero a información opaca que se desea transmitir a la operación

Hace referencia a Aleph::DynArray< T >::touch().

Gráfico de llamadas para esta función:

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

Node* Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator() ( const long & i )

inline

retorna el puntero al nodo dentro de la representación con listas de adyacencia del índice i en la matriz auxiliar.

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

long Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator() ( Node * node ) const

inline

Retorna el índice dentro de la matriz auxiliar de node dentro en la representación mediante listas de adyacencia.

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

Entry_Type& Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()	(	const long &	i,
		const long &	j
	)

inline

Retorna una referencia a la entrada (i,j) de la matriz de adyacencia auxiliar.

El operador (i,j) lee la entrada de la matriz auxiliar correspondiente y retorna su entrada.

Este modo de acceso es constante.

Parámetros

[in]	i	índice del nodo origen.
[in]	j	índice del nodo destino.

Excepciones

out_of_range si i o j es mayor o igual a la cantidad de nodos del grafo.

Devuelve: referencia a la entrada (i,j).

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

const Entry_Type& Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()	(	const long &	i,
		const long &	j
	)		const

inline

Retorna una referencia constante a la entrada (i,j) de la matriz de adyacencia auxiliar.

El operador (i,j) lee la entrada de la matriz auxiliar correspondiente y retorna su entrada.

Este modo de acceso es constante.

Parámetros

[in]	i	índice del nodo origen.
[in]	j	índice del nodo destino.

Excepciones

out_of_range si i o j es mayor o igual a la cantidad de nodos del grafo.

Devuelve: una referencia constante a la entrada (i,j).

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

Entry_Type& Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()	(	Node *	src,
		Node *	tgt
	)

inline

Retorna una referencia a una entrada de la matriz de adyacencia auxiliar dados los punteros a sus nodos origen y destino dentro de la representación con listas de adyacencia.

El operador (src,tgt) lee la entrada de la matriz auxiliar correspondiente a los punteros a los nodos src y tgt en la representación con listas de adyacencia y retorna su entrada.

Este modo de acceso es logarítmico. Por tanto, es recomendable utilizar los índices de los nodos.

Parámetros

[in]	src	puntero al nodo origen en la representación con listas de adyacencia.
[in]	tgt	puntero al nodo destino en la representación con listas de adyacencia.

Devuelve: una referencia constante a la entrada correspondiente.

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

const Entry_Type& Aleph::Ady_Mat< GT, __Entry_Type, SA >::operator()	(	Node *	src,
		Node *	tgt
	)		const

inline

Retorna una referencia constante a una entrada de la matriz de adyacencia auxiliar dados los punteros a sus nodos origen y destino dentro de la representación con listas de adyacencia.

El operador (src,tgt) lee la entrada de la matriz auxiliar correspondiente a los punteros a los nodos src y tgt en la representación con listas de adyacencia y retorna su entrada.

Este modo de acceso es logarítmico. Por tanto, es recomendable utilizar los índices de los nodos.

Parámetros

[in]	src	puntero al nodo origen en la representación con listas de adyacencia.
[in]	tgt	puntero al nodo destino en la representación con listas de adyacencia.

Devuelve: una referencia constante a la entrada correspondiente.

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

tpl_matgraph.H

Tipos públicos

Métodos públicos

Descripción detallada

template<class GT, typename __Entry_Type, class SA = Dft_Show_Arc<GT>> class Aleph::Ady_Mat< GT, __Entry_Type, SA >

Documentación de los 'Typedef' miembros de la clase

Documentación del constructor y destructor

Documentación de las funciones miembro

template<class GT, typename __Entry_Type, class SA = Dft_Show_Arc<GT>>
class Aleph::Ady_Mat< GT, __Entry_Type, SA >