Aleph-w  1.5a.2
Biblioteca general de algoritmos y estructuras de datos
 Todo Clases Archivos Funciones Variables 'typedefs' Enumeraciones Amigas Grupos Páginas
Métodos públicos | Lista de todos los miembros
Referencia de la plantilla de la Clase Aleph::Arcs_Index< GT, Compare, Tree, SA >
Grafos.

#include <tpl_graph_indexes.H>

+ Diagrama de herencias de Aleph::Arcs_Index< GT, Compare, Tree, SA >
+ Diagrama de colaboración para Aleph::Arcs_Index< GT, Compare, Tree, SA >:

Métodos públicos

 Arcs_Index (GT &_g, Compare &cmp, SA &_sa)
 
 Arcs_Index (GT &_g, Compare &&cmp=Compare(), SA &&_sa=SA())
 
GT_Arc * insert_in_graph (GT_Node *src, GT_Node *tgt, const GT_Arc_Info &info)
 
GT_Arc * insert_in_graph (GT_Node *src, GT_Node *tgt, const GT_Arc_Info &&info=GT_Arc_Info())
 
GT_Arc * search (GT_Node *src, GT_Node *tgt, const GT_Arc_Info &info)
 
GT_Arc * search (GT_Node *src, GT_Node *tgt, const GT_Arc_Info &&info=GT_Arc_Info())
 
void remove_from_graph (GT_Arc *a) throw (std::exception, std::domain_error)
 
 Arcs_Index (GT &_g, Compare &cmp, SA &_sa)
 
 Arcs_Index (GT &_g, Compare &&cmp=Compare(), SA &&_sa=SA())
 
GT_Arc * insert_in_graph (GT_Node *src, GT_Node *tgt, const GT_Arc_Info &info)
 
GT_Arc * insert_in_graph (GT_Node *src, GT_Node *tgt, const GT_Arc_Info &&info=GT_Arc_Info())
 
GT_Arc * search (GT_Node *src, GT_Node *tgt, const GT_Arc_Info &info)
 
GT_Arc * search (GT_Node *src, GT_Node *tgt, const GT_Arc_Info &&info=GT_Arc_Info())
 
void remove_from_graph (GT_Arc *a) throw (std::exception, std::domain_error)
 
- Métodos públicos heredados desde Aleph::DynSetTree< Tree, GT::Arc *, Compare >
void swap (DynSetTree &dset)
 
 DynSetTree (Compare &&cmp=Compare())
 Instancia un conjunto dinámico vacío.
 
 DynSetTree (Compare &cmp)
 
 DynSetTree (const DynSetTree &srcTree)
 Instancia un conjunto dinámico copia de srcTree.
 
 DynSetTree (const DynList< Tree > &list)
 
 DynSetTree (DynSetTree &&srcTree)
 
void empty ()
 Elimina todos los elementos del conjunto.
 
DynSetTree & operator= (const DynList< Tree > &list)
 
DynSetTree & operator= (const DynSetTree &srcTree)
 Asigna a this el conjunto dinámico srcTree.
 
DynSetTree & operator= (DynSetTree &&srcTree)
 Asigna a this el conjunto dinámico srcTree.
 
virtual ~DynSetTree ()
 Destructor; todos los elementos son liberados.
 
Tree * insert (const Tree &key)
 
Tree * insert (Tree &&key)
 
Tree * append (const Tree &key)
 
Tree * append (Tree &&key)
 
Tree * search_or_insert (const Tree &key)
 
Tree * search_or_insert (Tree &&key)
 
Tree * insert_dup (const Tree &key)
 
Tree * insert_dup (Tree &&key)
 
Tree * put (const Tree &key)
 Seudo sinonimo de insert; no retorna ningún valor.
 
Tree * put (Tree &&key)
 
size_t remove (const Tree &key)
 
bool exist (const Tree &key) const
 Retorna true si key pertenece al conjunto dinámico.
 
bool has (const Tree &key) const
 
bool contains (const Tree &key) const
 
Tree & find (const Tree &key) throw (std::exception, std::domain_error)
 
std::pair< int, Tree * > find_position (const Tree &key) const
 
Tree * search (const Tree &key) const throw (std::exception, std::domain_error)
 
const Tree & min () const
 
const Tree & get_first ()
 
const Tree & max () const
 
const Tree & get_last ()
 
const Tree & get ()
 Sinónimo de max.
 
const size_t & size () const
 Retorna la cardinalidad del conjunto.
 
bool is_empty () const
 Retorna true si el conjunto está vacío.
 
size_t internal_path_length () const
 
Node * get_root_node () const
 
const Tree & get_root () const
 
size_t height () const
 Calcula y retorna la altura del árbol binario de búsqueda.
 
void for_each_in_preorder (void(*visitFct)(Node *, int, int))
 
long position (const Tree &key) const
 
Tree & select (const size_t &i)
 
const Tree & select (const size_t &i) const
 
Tree & operator() (const size_t &i)
 
Tree & access (const size_t &i)
 
bool verify ()
 
void for_each_preorder (Key_Op &key_op)
 
void for_each_preorder (Key_Op &&key_op=Key_Op())
 
void for_each_inorder (Key_Op &key_op)
 
void for_each_inorder (Key_Op &&key_op=Key_Op())
 
void for_each_postorder (Key_Op &key_op)
 
void for_each_postorder (Key_Op &&key_op=Key_Op())
 
DynSetTree & join (DynSetTree &t, DynSetTree &dup)
 
DynSetTree & join (DynSetTree &t, DynSetTree &&dup=DynSetTree())
 
DynSetTree & join_dup (DynSetTree &t)
 
bool split_key (const Tree &key, DynSetTree &l, DynSetTree &r)
 
void split_pos (const size_t pos, DynSetTree &l, DynSetTree &r)
 
void split_key_dup (const Tree &key, DynSetTree &l, DynSetTree &r)
 
bool traverse (Operation &op)
 
bool traverse (Operation &&op=Operation())
 
bool traverse (Operation &op) const
 
bool traverse (Operation &&op=Operation()) const
 
 Functional_Methods (Tree)
 
 Generic_Keys (Tree)
 
 Equal_To_Method (DynSetTree)
 
- Métodos públicos heredados desde Aleph::DynSetTree< GT::Arc *, Tree, Compare >
void swap (DynSetTree &dset)
 
 DynSetTree (Compare &&cmp=Compare())
 Instancia un conjunto dinámico vacío.
 
 DynSetTree (Compare &cmp)
 
 DynSetTree (const DynSetTree &srcTree)
 Instancia un conjunto dinámico copia de srcTree.
 
 DynSetTree (const DynList< GT::Arc * > &list)
 
 DynSetTree (DynSetTree &&srcTree)
 
void empty ()
 Elimina todos los elementos del conjunto.
 
DynSetTree & operator= (const DynList< GT::Arc * > &list)
 
DynSetTree & operator= (const DynSetTree &srcTree)
 Asigna a this el conjunto dinámico srcTree.
 
DynSetTree & operator= (DynSetTree &&srcTree)
 Asigna a this el conjunto dinámico srcTree.
 
virtual ~DynSetTree ()
 Destructor; todos los elementos son liberados.
 
GT::Arc ** insert (const GT::Arc *&key)
 
GT::Arc ** insert (GT::Arc *&&key)
 
GT::Arc ** append (const GT::Arc *&key)
 
GT::Arc ** append (GT::Arc *&&key)
 
GT::Arc ** search_or_insert (const GT::Arc *&key)
 
GT::Arc ** search_or_insert (GT::Arc *&&key)
 
GT::Arc ** insert_dup (const GT::Arc *&key)
 
GT::Arc ** insert_dup (GT::Arc *&&key)
 
GT::Arc ** put (const GT::Arc *&key)
 Seudo sinonimo de insert; no retorna ningún valor.
 
GT::Arc ** put (GT::Arc *&&key)
 
size_t remove (const GT::Arc *&key)
 
bool exist (const GT::Arc *&key) const
 Retorna true si key pertenece al conjunto dinámico.
 
bool has (const GT::Arc *&key) const
 
bool contains (const GT::Arc *&key) const
 
GT::Arc *& find (const GT::Arc *&key) throw (std::exception, std::domain_error)
 
std::pair< int, GT::Arc ** > find_position (const GT::Arc *&key) const
 
GT::Arc ** search (const GT::Arc *&key) const throw (std::exception, std::domain_error)
 
const GT::Arc *& min () const
 
const GT::Arc *& get_first ()
 
const GT::Arc *& max () const
 
const GT::Arc *& get_last ()
 
const GT::Arc *& get ()
 Sinónimo de max.
 
const size_t & size () const
 Retorna la cardinalidad del conjunto.
 
bool is_empty () const
 Retorna true si el conjunto está vacío.
 
size_t internal_path_length () const
 
Node * get_root_node () const
 
const GT::Arc *& get_root () const
 
size_t height () const
 Calcula y retorna la altura del árbol binario de búsqueda.
 
void for_each_in_preorder (void(*visitFct)(Node *, int, int))
 
long position (const GT::Arc *&key) const
 
GT::Arc *& select (const size_t &i)
 
const GT::Arc *& select (const size_t &i) const
 
GT::Arc *& operator() (const size_t &i)
 
GT::Arc *& access (const size_t &i)
 
bool verify ()
 
void for_each_preorder (Key_Op &key_op)
 
void for_each_preorder (Key_Op &&key_op=Key_Op())
 
void for_each_inorder (Key_Op &key_op)
 
void for_each_inorder (Key_Op &&key_op=Key_Op())
 
void for_each_postorder (Key_Op &key_op)
 
void for_each_postorder (Key_Op &&key_op=Key_Op())
 
DynSetTree & join (DynSetTree &t, DynSetTree &dup)
 
DynSetTree & join (DynSetTree &t, DynSetTree &&dup=DynSetTree())
 
DynSetTree & join_dup (DynSetTree &t)
 
bool split_key (const GT::Arc *&key, DynSetTree &l, DynSetTree &r)
 
void split_pos (const size_t pos, DynSetTree &l, DynSetTree &r)
 
void split_key_dup (const GT::Arc *&key, DynSetTree &l, DynSetTree &r)
 
bool traverse (Operation &op)
 
bool traverse (Operation &&op=Operation())
 
bool traverse (Operation &op) const
 
bool traverse (Operation &&op=Operation()) const
 
 Functional_Methods (GT::Arc *)
 
 Generic_Keys (GT::Arc *)
 
 Equal_To_Method (DynSetTree)
 

Otros miembros heredados

- Tipos públicos heredados desde Aleph::DynSetTree< Tree, GT::Arc *, Compare >
typedef GT::Arc *< Tree,
Compare >::Node 		Node
 
typedef DynSetTree Set_Type
 
typedef Tree Item_Type
 
typedef Tree Key_Type
 
- Tipos públicos heredados desde Aleph::DynSetTree< GT::Arc *, Tree, Compare >
typedef Tree< GT::Arc
*, Compare >::Node 		Node
 
typedef DynSetTree Set_Type
 
typedef GT::Arc * Item_Type
 
typedef GT::Arc * Key_Type
 

Descripción detallada

template<class GT, class Compare = Dft_Arc_Cmp<GT>, template< typename, class > class Tree = Treap, class SA = Dft_Show_Arc<GT>>
class Aleph::Arcs_Index< GT, Compare, Tree, SA >

Construye un índice de arcos para su rápida búsqueda y recuperación dado sus nodos.

IndexArc indiza los arcos de un grafo según el par de nodos que el arco relaciona. La idea es implementar la detección de existencia de arco y su recuperación en tiempo logarítmico.

La clase recibe los siguientes parámetros tipo:

  1. GT: el tipo de grafo basado en List_Graph.
  2. Tree: el tipo de árbol binario de búsqueda usado internamente para indizar las claves. Por omisión se usan treaps.
Atención
Para que la compilación correcta es imperativo que el exista el constructor GT::Arc(void * src, void * tgt, GT::Arc_Type). Del mismo modo, también debe existir el constructor por omisión GT::Arc_Type().
Ver también
IndexNode Index_Graph
Autor
Leandro Rabindranath León (lrleon en ula punto ve)
Alejandro Mujica (aledrums en gmail punto com)

Documentación de las funciones miembro

template<class GT , class Compare = Dft_Arc_Cmp<GT>, template< typename, class > class Tree = Treap, class SA = Dft_Show_Arc<GT>>
GT_Arc* Aleph::Arcs_Index< GT, Compare, Tree, SA >::insert_in_graph ( GT_Node *  src,
GT_Node *  tgt,
const GT_Arc_Info &  info 
)
inline

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

Parámetros
[in]srcnodo origen.
[in]tgtnodo destino.
[in]infoinformación a copiarse como contenido del nodo. Por omisión se copia el contenido que arroje el constructor GT::Arc_Type().
Devuelve
puntero al arco creado.
Excepciones
bad_allocsi no hay suficiente memoria.

Hace referencia a Aleph::DynSetTree< Tree, GT::Arc *, Compare >::insert().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Arc_Cmp<GT>, template< typename, class > class Tree = Treap, class SA = Dft_Show_Arc<GT>>
GT_Arc* Aleph::Arcs_Index< GT, Compare, Tree, SA >::insert_in_graph ( GT_Node *  src,
GT_Node *  tgt,
const GT_Arc_Info &&  info = GT_Arc_Info() 
)
inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

Hace referencia a Aleph::Arcs_Index< GT, Compare, Tree, SA >::insert_in_graph().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Arc_Cmp<GT>, template< typename, class > class Tree = Treap, class SA = Dft_Show_Arc<GT>>
GT_Arc* Aleph::Arcs_Index< GT, Compare, Tree, SA >::insert_in_graph ( GT_Node *  src,
GT_Node *  tgt,
const GT_Arc_Info &  info 
)
inline

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

Parámetros
[in]srcnodo origen.
[in]tgtnodo destino.
[in]infoinformación a copiarse como contenido del nodo. Por omisión se copia el contenido que arroje el constructor GT::Arc_Type().
Devuelve
puntero al arco creado.
Excepciones
bad_allocsi no hay suficiente memoria.

Hace referencia a Aleph::DynSetTree< Tree, GT::Arc *, Compare >::insert().

Referenciado por Aleph::Arcs_Index< GT, Compare, Tree, SA >::insert_in_graph().

+ Gráfico de llamadas para esta función:

+ Gráfico de llamadas a esta función:

template<class GT , class Compare = Dft_Arc_Cmp<GT>, template< typename, class > class Tree = Treap, class SA = Dft_Show_Arc<GT>>
GT_Arc* Aleph::Arcs_Index< GT, Compare, Tree, SA >::insert_in_graph ( GT_Node *  src,
GT_Node *  tgt,
const GT_Arc_Info &&  info = GT_Arc_Info() 
)
inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

Hace referencia a Aleph::Arcs_Index< GT, Compare, Tree, SA >::insert_in_graph().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Arc_Cmp<GT>, template< typename, class > class Tree = Treap, class SA = Dft_Show_Arc<GT>>
void Aleph::Arcs_Index< GT, Compare, Tree, SA >::remove_from_graph ( GT_Arc *  a)
throw (std::exception,
std::domain_error
)
inline

Elimina el arco a del grafo y del ìndice.

Parámetros
[in]apuntero al arco a eliminar
Excepciones
domain_errorsi el arco no està insertado en el índice (lo que posiblemente signifique que tampoco en el grafo).

Hace referencia a Aleph::DynSetTree< Tree, GT::Arc *, Compare >::find().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Arc_Cmp<GT>, template< typename, class > class Tree = Treap, class SA = Dft_Show_Arc<GT>>
void Aleph::Arcs_Index< GT, Compare, Tree, SA >::remove_from_graph ( GT_Arc *  a)
throw (std::exception,
std::domain_error
)
inline

Elimina el arco a del grafo y del ìndice.

Parámetros
[in]apuntero al arco a eliminar
Excepciones
domain_errorsi el arco no està insertado en el índice (lo que posiblemente signifique que tampoco en el grafo).

Hace referencia a Aleph::DynSetTree< Key, Tree, Compare >::find() y Aleph::DynSetTree< Key, Tree, Compare >::remove().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Arc_Cmp<GT>, template< typename, class > class Tree = Treap, class SA = Dft_Show_Arc<GT>>
GT_Arc* Aleph::Arcs_Index< GT, Compare, Tree, SA >::search ( GT_Node *  src,
GT_Node *  tgt,
const GT_Arc_Info &  info 
)
inline

Busca un arco que conecte a dos nodos.

Parámetros
[in]srcnodo origen.
[in]tgtnodo destino.
[in]infoinformación asociada al arco.
Devuelve
puntero al arco si éste existe o NULL de lo contrario.

Hace referencia a Aleph::DynSetTree< Key, Tree, Compare >::search().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Arc_Cmp<GT>, template< typename, class > class Tree = Treap, class SA = Dft_Show_Arc<GT>>
GT_Arc* Aleph::Arcs_Index< GT, Compare, Tree, SA >::search ( GT_Node *  src,
GT_Node *  tgt,
const GT_Arc_Info &&  info = GT_Arc_Info() 
)
inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

Hace referencia a Aleph::Arcs_Index< GT, Compare, Tree, SA >::search().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Arc_Cmp<GT>, template< typename, class > class Tree = Treap, class SA = Dft_Show_Arc<GT>>
GT_Arc* Aleph::Arcs_Index< GT, Compare, Tree, SA >::search ( GT_Node *  src,
GT_Node *  tgt,
const GT_Arc_Info &  info 
)
inline

Busca un arco que conecte a dos nodos.

Parámetros
[in]srcnodo origen.
[in]tgtnodo destino.
[in]infoinformación asociada al arco.
Devuelve
puntero al arco si éste existe o NULL de lo contrario.

Hace referencia a Aleph::DynSetTree< Key, Tree, Compare >::search().

Referenciado por Aleph::Arcs_Index< GT, Compare, Tree, SA >::search().

+ Gráfico de llamadas para esta función:

+ Gráfico de llamadas a esta función:

template<class GT , class Compare = Dft_Arc_Cmp<GT>, template< typename, class > class Tree = Treap, class SA = Dft_Show_Arc<GT>>
GT_Arc* Aleph::Arcs_Index< GT, Compare, Tree, SA >::search ( GT_Node *  src,
GT_Node *  tgt,
const GT_Arc_Info &&  info = GT_Arc_Info() 
)
inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

Hace referencia a Aleph::Arcs_Index< GT, Compare, Tree, SA >::search().

+ Gráfico de llamadas para esta función:

La documentación para esta clase fue generada a partir de los siguientes ficheros:
Leandro Rabindranath León