Aleph::Map_Matrix_Graph< GT, SA > Class Template Reference

#include <tpl_matgraph.H>

Public Types
typedef GT	Graph_Type
	El tipo de Graph_List asociado a la matriz.
typedef GT::Node_Type	Node_Type
	El tipo atributo de nodo que guarda los nodos en el objeto GT.
typedef GT::Arc_Type	Arc_Type
	El tipo atributo de arco que guarda los nodos en el objeto GT.
typedef GT::Node	Node
	El tipo de nodo que se maneja el objeto GT.
typedef GT::Arc	Arc
	El tipo de arco que se maneja el objeto GT.

Public Member Functions
void	copy_list_graph (GT &g)
	Map_Matrix_Graph (GT &g, SA &&__sa=SA())
	Constructor a partir de un grafo representado con listas de adyacencia.
	Map_Matrix_Graph (GT &g, SA &__sa)
	Map_Matrix_Graph (Map_Matrix_Graph &mat)
	Constructor copia.
Map_Matrix_Graph &	operator= (Map_Matrix_Graph &mat)
	Asignación de matriz de adyacencia.
Map_Matrix_Graph &	operator= (GT &g)
Node *	operator() (const long &i)
long	operator() (Node *node) const
Arc *	operator() (Node *src_node, Node *tgt_node) const
Arc *	operator() (const long &i, const long &j) const
GT &	get_list_graph ()
	Retorna una referencia al grafo representado con listas enlazadas.
const size_t &	get_num_nodes () const

Detailed Description

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

Matriz de adyacencia de un grafo mapeada a un grafo representado mediante una variante de GT.

La clase Map_Matrix_Graph modeliza una matriz de adyacencia mapeo hacia los arcos de un grafo representado con listas de adyacencia. Ella constituye la más simple manera de construir una matriz de adyacencia en Aleph. Se trata de una matriz cuyas entradas son punteros hacia arcos de un grafo representado mediante alguna clase basada en GT. Una entrada con valor nullptr indica ausencia de arco.

Para construir un objeto de tipo Map_Matrix_Graph se requiere tener una instancia del grafo basada en un objeto derivado de GT.

El acceso a la matriz se realiza mediante el operador (i,j). Si mat es un objeto de tipo Map_Matrix_Graph, entonces el mat(i,j) refiere al arco entre el nodo i y j. Un valor igual a nullptr indica que no hay arco; de lo contrario, mat(i,j) es un apuntador de tipo GT::Arc al arco en la representación con listas de adyacencia.

Las entradas a las matriz también pueden referirse mediante punteros a nodos. En este sentido mat(src,tgt) refiere al arco entre los nodos apuntados por src y tgt.

Puede decirse que el uso de memoria de un objeto Map_Matrix_Graph trata de ser lo más eficiente posible. Por lo general, el consumo de memoria es proporcional al número de arcos. Internamente, esta eficiencia se implanta a través del uso de un arreglo dinámico DynArray.

No está permitido modificar una entrada de una matrix Map_Matrix_Graph. No hay ningún control sobre la matriz y su relación con el objeto List_graph asociado. Dicho de otro modo, cambios topológicos (inserción y eliminación de nodos y arcos) en el objeto GT no se verán reflejados en la matriz. Sin embargo, la capacidad de acceso nodos y arcos en la representación con listas permite sin ningún problema modificar cualquiera de sus atributos.

Map_Matrix_Graph no está concebido para multigrafos o multidigrafos.

Parameters

GT	el tipo de grafo derivado de una clase basada en GT.

See also

Matrix_Graph Ady_Mat Bit_Mat_Graph DynArray

Member Function Documentation

copy_list_graph()

template<class GT , class SA >

void Aleph::Map_Matrix_Graph< GT, SA >::copy_list_graph ( GT &  g )

inline

Copia a la matriz el grafo g representado con listas de adyacencia; los valores anteriores de la matriz son borrados.

Here is the call graph for this function:

Here is the caller graph for this function:

get_num_nodes()

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

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

inline

Retorna el número de nodos que tiene el grafo (equivalente a la dimensión de la matriz.

operator()() [1/4]

template<class GT , class SA >

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

inline

Retorna el puntero a nodo en la representación con listas correspondiente al índice i en la matriz.

El operador (i) con i entero retorna un puntero al nodo de la representación con listas del grafo asociado a la matriz del índice i.

Parameters

[in]

i

índice de la matriz.

Returns

puntero al nodo de la representación con listas del grafo asociado a la matriz del índice i.

Exceptions

out_of_range

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

Here is the caller graph for this function:

operator()() [2/4]

template<class GT , class SA >

long Aleph::Map_Matrix_Graph< GT, SA >::operator() ( typename GT::Node *  node ) const

inline

Retorna el índice en la matriz del nodo node en la representación con listas.

El operador (node) con node un puntero a nodo, retorna el índice dentro de la matriz de adyacencia.

No se hacen verificaciones sobre la correctitud del puntero.

Parameters

[in]

node

puntero a nodo en la representación con listas de adyacencia.

Returns

puntero al nodo de la representación con listas del grafo asociado a la matriz del índice i.

Exceptions

out_of_range

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

operator()() [3/4]

template<class GT , class SA >

GT::Arc * Aleph::Map_Matrix_Graph< GT, SA >::operator() ( Node *  src_node, Node *  tgt_node  ) const

inline

Retorna un puntero a un arco con nodo origen src_node y destino tgt_node.

El operador (src_node,tgt_node) lee la entrada de la matriz correspondiente al nodo origen src_node y nodo destino tgt_node y retorna un apuntador al arco. Si no existe el arco, entonces se retorna nullptr.

No se realiza verificación sobre la correctitud de los apuntadores.

Este modo de acceso es logarítmico. Por esa razón, es preferible primero indagar los índices de los nodos y luego utilizar el mismo operador (i,j) con los índices de los nodos.

Parameters

[in]	src_node	puntero al nodo origen.
[in]	tgt_node	puntero al nodo destino.

Returns

puntero al arco si éste existe; nullptr de lo contrario.

operator()() [4/4]

template<class GT , class SA >

GT::Arc * Aleph::Map_Matrix_Graph< GT, SA >::operator() ( const long &  i, const long &  j  ) const

inline

Retorna un puntero al arco contenido en la entrada (i,j) de la matriz de adyacencia.

El operador (i,j) lee la entrada de la matriz correspondiente y retorna un apuntador al arco. Si no existe el arco, entonces se retorna nullptr.

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

puntero al arco si éste existe; nullptr de lo contrario.

operator=()

template<class GT , class SA >

Map_Matrix_Graph< GT, SA > & Aleph::Map_Matrix_Graph< GT, SA >::operator= ( GT &  g )

inline

Asignación de grafo representado con listas de adyacencia.

Limpia la matriz (toda la memoria es liberada) y construye una nueva matriz de adyacencia basada en el grafo representado con listas de adyacencia g.

Parameters

[in]

g

el grafo representado con listas a ser asignado.

Exceptions

bad_alloc

si no hay suficiente memoria para la matriz.

Here is the call graph for this function:

---

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

• tpl_matgraph.H