Aleph::Ady_Mat< GT, __Entry_Type, SA > Class Template Reference

#include <tpl_matgraph.H>

Public Types
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.

Public Member Functions
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)

Detailed Description

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:

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

See also

Matrix_Graph Map_Matrix_Graph

Member Typedef Documentation

Arc_Type

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.

Node_Type

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.

Constructor & Destructor Documentation

Ady_Mat() [1/2]

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().

Parameters

[in]

g

el grafo representado con listas de adyacencia.

Exceptions

bad_alloc

si no hay suficiente memoria.

See also

Ady_Mat::set_null_value() Ady_Mat::null_value()

Ady_Mat() [2/2]

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().

Parameters

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

Exceptions

bad_alloc

si no hay suficiente memoria.

See also

Ady_Mat::set_null_value() Ady_Mat::null_value()

Member Function Documentation

get_num_nodes()

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

Here is the caller graph for this function:

operate_all_arcs_list_graph() [1/2]

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:

1. mat: es una referencia a la matrix sobre el cual se está realizando la operación.
2. arc: es un apuntador al arco dentro del GT asociado a la matriz.
3. i: es el índice del nodo origen en la matriz.
4. j: es el índice del nodo destino en la matriz.
5. 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.

Here is the call graph for this function:

operate_all_arcs_list_graph() [2/2]

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:

1. mat: es una referencia a la matrix sobre el cual se está realizando la operación.
2. arc: es un apuntador al arco dentro del GT asociado a la matriz.
3. i: es el índice del nodo origen en la matriz.
4. j: es el índice del nodo destino en la matriz.
5. entry: es una referencia al contenido de la entrada (i,j) en la matriz.
6. 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.

Parameters

[in]

ptr

puntero a información opaca que se desea transmitir a la operación

Here is the call graph for this function:

operate_all_arcs_matrix() [1/2]

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í:

1. mat: referencia a la matriz
2. src: puntero al nodo origen.
3. tgt: puntero al nodo destino.
4. s: índice del nodo origen.
5. t: índice del nodo destino.
6. 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.

Here is the call graph for this function:

operate_all_arcs_matrix() [2/2]

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í:

1. mat: referencia a la matriz
2. src: puntero al nodo origen.
3. tgt: puntero al nodo destino.
4. s: índice del nodo origen.
5. t: índice del nodo destino.
6. entry: referencia a la entrada de la matriz.
7. 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.

Parameters

[in]

ptr

puntero a información opaca que se desea transmitir a la operación

Here is the call graph for this function:

operator()() [1/6]

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.

operator()() [2/6]

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.

operator()() [3/6]

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.

Parameters

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

Exceptions

out_of_range

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

Returns

referencia a la entrada (i,j).

operator()() [4/6]

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.

Parameters

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

Exceptions

out_of_range

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

Returns

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

operator()() [5/6]

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.

Parameters

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

Returns

una referencia constante a la entrada correspondiente.

operator()() [6/6]

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.

Parameters

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

Returns

una referencia constante a la entrada correspondiente.

---

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

• tpl_matgraph.H