 |
Aleph-w
1.5a.2
Biblioteca general de algoritmos y estructuras de datos
|
|
|
Aleph-w
1.5a.2
Biblioteca general de algoritmos y estructuras de datos
|
|
#include <tpl_matgraph.H>
Tipos públicos | |
| 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. | |
Métodos públicos | |
| 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 |
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 NULL 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 NULL 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.
| GT | el tipo de grafo derivado de una clase basada en GT. |
|
inline |
Copia a la matriz el grafo g representado con listas de adyacencia; los valores anteriores de la matriz son borrados.
Hace referencia a Aleph::DynArray< T >::cut(), Aleph::Filter_Iterator< Container, It, Show_Item >::next() y Aleph::quicksort().
Referenciado por Aleph::Map_Matrix_Graph< GT, SA >::Map_Matrix_Graph().
Gráfico de llamadas para esta función: Gráfico de llamadas a esta función:
|
inline |
Retorna el número de nodos que tiene el grafo (equivalente a la dimensión de la matriz.
|
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.
| [in] | i | índice de la matriz. |
| out_of_range | si i es mayor o igual a la cantidad de nodos. |
|
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.
| [in] | node | puntero a nodo en la representación con listas de adyacencia. |
| out_of_range | si i es mayor o igual a la cantidad de nodos. |
|
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 NULL.
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.
| [in] | src_node | puntero al nodo origen. |
| [in] | tgt_node | puntero al nodo destino. |
|
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 NULL.
Este modo de acceso es constante.
| [in] | i | índice del nodo origen. |
| [in] | j | índice del nodo destino. |
| out_of_range | si i o j es mayor o igual a la cantidad de nodos del grafo. |
|
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.
| [in] | g | el grafo representado con listas a ser asignado. |
| bad_alloc | si no hay suficiente memoria para la matriz. |
