Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Public Member Functions | Private Types | Private Attributes | List of all members
Aleph::Index_Graph< GT, Compare, Tree > Class Template Reference
Graphs

Construye índices de nodos y arcos para su rápida búsqueda y recuperación. More...

#include <tpl_indexGraph.H>

Collaboration diagram for Aleph::Index_Graph< GT, Compare, Tree >:
[legend]

Public Member Functions

 Index_Graph (GT &g)
 Crea un índice del grafo: los nodos y arcos son indizados.
 
GT_Node * insert_node (const GT_Node_Type &info)
 Crea un nuevo nodo y lo inserta en grafo y en el índice.
 
GT_Arc * insert_arc (GT_Node *src, GT_Node *tgt, const GT_Arc_Type &info=GT_Arc_Type())
 Crea un nuevo arco entre dos nodos y lo inserta en el grafo y en el índice.
 
GT_Node * search_node (GT_Node *p)
 Busca en el índice un nodo.
 
GT_Node * search_node (const GT_Node_Type &info)
 Busca en el índice un nodo.
 
GT_Arc * search_arc (GT_Node *src, GT_Node *tgt)
 Busca en el índice un arco dados dos nodos.
 
void remove_node (GT_Node *p)
 Elimina el nodo p del grafo y del índice.
 
void remove_arc (GT_Arc *a)
 Elimina del grafo y del índice el arco a.
 
size_t get_num_arcs () const
 Retorna el número de arcos que contiene el índice.
 
size_t get_num_nodes () const
 Retorna el número de nodos que contiene el índice.
 

Private Types

typedef GT::Arc GT_Arc
 
typedef GT::Node GT_Node
 
typedef GT::Arc_Type GT_Arc_Type
 
typedef GT::Node_Type GT_Node_Type
 

Private Attributes

IndexNode< GT, Compare, Tree > idx_node
 
IndexArc< GT, Tree > idx_arc
 

Detailed Description

template<class GT, class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
class Aleph::Index_Graph< GT, Compare, Tree >

Construye índices de nodos y arcos para su rápida búsqueda y recuperación.

Index_Graph indiza los nodos y arcos a efectos de su recuperación rápida.

A efectos de facilitar el uso y hacer su uso más seguro, Index_Graph ofrece las operaciones topológicas clásicas de un grafo: insert_node(), insert_arc(), etc.

La clase recibe los siguientes parámetros tipo:

  1. GT: el tipo de grafo basado en List_Graph
  2. Compare: clase de comparación para la clave de indización de los nodos. El contrato de esta clase es intrumentar el operador () así:
    template <class GT>
    struct Dft_Node_Cmp
    {
    bool
    operator () (typename GT::Node * p1, typename GT::Node * p2) const
    {
    // acceso a los nodos y comparación según el campo deseado
    }
    };
    Aleph::Dft_Node_Cmp
    Default node comparison class for Nodes_Index.
    Definition tpl_graph_indexes.H:59
    Aleph::Graph_Node< int >

Por omisión esta clase está programada para comparar el valor retornado por get_info() sobre cada nodo. Para ello, el operador < del tipo GT::Node_Type debe estar implementado

  1. Tree: el tipo de árbol binario de búsqueda usado internamente para indizar las claves. Por omisión se usan treaps
See also
IndexArc IndexNode
Author
Leandro Rabindranath León (lrleon en ula punto ve)
Alejandro Mujica (aledrums en gmail punto com)

Definition at line 118 of file tpl_indexGraph.H.

Member Typedef Documentation

◆ GT_Arc

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
typedef GT::Arc Aleph::Index_Graph< GT, Compare, Tree >::GT_Arc
private

Definition at line 122 of file tpl_indexGraph.H.

◆ GT_Arc_Type

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
typedef GT::Arc_Type Aleph::Index_Graph< GT, Compare, Tree >::GT_Arc_Type
private

Definition at line 124 of file tpl_indexGraph.H.

◆ GT_Node

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
typedef GT::Node Aleph::Index_Graph< GT, Compare, Tree >::GT_Node
private

Definition at line 123 of file tpl_indexGraph.H.

◆ GT_Node_Type

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
typedef GT::Node_Type Aleph::Index_Graph< GT, Compare, Tree >::GT_Node_Type
private

Definition at line 125 of file tpl_indexGraph.H.

Constructor & Destructor Documentation

◆ Index_Graph()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
Aleph::Index_Graph< GT, Compare, Tree >::Index_Graph ( GT &  g)
inline

Crea un índice del grafo: los nodos y arcos son indizados.

Definition at line 133 of file tpl_indexGraph.H.

Member Function Documentation

◆ get_num_arcs()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
size_t Aleph::Index_Graph< GT, Compare, Tree >::get_num_arcs ( ) const
inline

Retorna el número de arcos que contiene el índice.

Definition at line 229 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_arc.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ get_num_nodes()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
size_t Aleph::Index_Graph< GT, Compare, Tree >::get_num_nodes ( ) const
inline

Retorna el número de nodos que contiene el índice.

Definition at line 232 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_node.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ insert_arc()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
GT_Arc * Aleph::Index_Graph< GT, Compare, Tree >::insert_arc ( GT_Node *  src,
GT_Node *  tgt,
const GT_Arc_Type &  info = GT_Arc_Type() 
)
inline

Crea un nuevo arco entre dos nodos y lo inserta en el grafo y en el índice.

Parameters
[in]srcnodo origen.
[in]tgtnodo destino.
[in]infoinformación a copiarse en el arco. Por omisión es la que dé el constructor GT_Arc_Type().
Returns
puntero al nuevo arco.
Exceptions
bad_allocsi no hay suficiente memoria.

Definition at line 159 of file tpl_indexGraph.H.

References ah_domain_error_if, Aleph::Index_Graph< GT, Compare, Tree >::idx_arc, Aleph::Index_Graph< GT, Compare, Tree >::idx_node, and Aleph::maps().

Referenced by main(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ insert_node()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
GT_Node * Aleph::Index_Graph< GT, Compare, Tree >::insert_node ( const GT_Node_Type &  info)
inline

Crea un nuevo nodo y lo inserta en grafo y en el índice.

Parameters
[in]infoinformación a copiarse en el nodo.
Returns
puntero al nuevo nodo.
Exceptions
bad_allocsi no hay suficiente memoria.

Definition at line 144 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_node, and Aleph::maps().

Referenced by main(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ remove_arc()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
void Aleph::Index_Graph< GT, Compare, Tree >::remove_arc ( GT_Arc *  a)
inline

Elimina del grafo y del índice el arco a.

Definition at line 223 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_arc.

Referenced by TEST_F(), TEST_F(), and TEST_F().

◆ remove_node()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
void Aleph::Index_Graph< GT, Compare, Tree >::remove_node ( GT_Node *  p)
inline

Elimina el nodo p del grafo y del índice.

Parameters
[in]ppuntero al nodo a eliminar

Definition at line 212 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_arc, and Aleph::Index_Graph< GT, Compare, Tree >::idx_node.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ search_arc()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
GT_Arc * Aleph::Index_Graph< GT, Compare, Tree >::search_arc ( GT_Node *  src,
GT_Node *  tgt 
)
inline

Busca en el índice un arco dados dos nodos.

Parameters
[in]srcpuntero al nodo origen.
[in]tgtpuntero al nodo destino.
Returns
puntero al arco en caso de encontrarse en el índice; nullptr de lo contrario.

Definition at line 203 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_arc.

Referenced by main(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ search_node() [1/2]

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
GT_Node * Aleph::Index_Graph< GT, Compare, Tree >::search_node ( const GT_Node_Type &  info)
inline

Busca en el índice un nodo.

Parameters
[in]infoinformación según la cual se buscará el nodo.
Returns
puntero al nodo en caso de encontrarse en el índice; nullptr de lo contrario.
Warning
Tome en consideración que la búsqueda se realiza según la implementación de la clase de comparación Compare pasada en tiempo de instanciación.

Definition at line 191 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_node, and Aleph::maps().

◆ search_node() [2/2]

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
GT_Node * Aleph::Index_Graph< GT, Compare, Tree >::search_node ( GT_Node *  p)
inline

Busca en el índice un nodo.

Parameters
[in]ppuntero al nodo.
Returns
puntero al nodo en caso de encontrarse en el índice; nullptr de lo contrario.

Definition at line 177 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_node.

Referenced by main(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

Member Data Documentation

◆ idx_arc

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
IndexArc<GT, Tree> Aleph::Index_Graph< GT, Compare, Tree >::idx_arc
private

Definition at line 128 of file tpl_indexGraph.H.

Referenced by Aleph::Index_Graph< GT, Compare, Tree >::get_num_arcs(), Aleph::Index_Graph< GT, Compare, Tree >::insert_arc(), Aleph::Index_Graph< GT, Compare, Tree >::remove_arc(), Aleph::Index_Graph< GT, Compare, Tree >::remove_node(), and Aleph::Index_Graph< GT, Compare, Tree >::search_arc().

◆ idx_node

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
IndexNode<GT, Compare, Tree> Aleph::Index_Graph< GT, Compare, Tree >::idx_node
private

Definition at line 127 of file tpl_indexGraph.H.

Referenced by Aleph::Index_Graph< GT, Compare, Tree >::get_num_nodes(), Aleph::Index_Graph< GT, Compare, Tree >::insert_arc(), Aleph::Index_Graph< GT, Compare, Tree >::insert_node(), Aleph::Index_Graph< GT, Compare, Tree >::remove_node(), Aleph::Index_Graph< GT, Compare, Tree >::search_node(), and Aleph::Index_Graph< GT, Compare, Tree >::search_node().

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