Aleph::Path

Referencia de la plantilla de la Clase Path
[Grafos.]

Camino sobre un grafo. Más...

Lista de todos los miembros.

Tipos públicos

typedef GT::Arc_Type Arc_Type
 El tipo de atributo que contienen los arcos del camino.
typedef GT::Node_Type Node_Type
 El tipo de atributo que contienen los nodos del camino.

Métodos públicos

void append (Node *node)
 Concatena un nodo al camino.
void append (Arc *arc)
 Concatena un arco al camino.
void clear_path ()
 Limpia el camino (se eliminan todos sus nodos y arcos).
Arc * get_first_arc ()
 Retorna el primer arco del camino.
Node * get_first_node ()
 Retorna el primer nodo del camino.
Arc * get_last_arc ()
 Retorna el último arco del camino.
Node * get_last_node ()
 Retorna el último nodo del camino.
void init (Node *start_node)
 Inicializa un camino que comienza en start_node.
void insert (Node *node)
 Inserta un nodo como primero del camino.
void insert (Arc *arc)
 Inserta un arco al camino como el primero.
bool inside_graph (GT &gr) const
 retorna true si el camino this refiere al grafo gr
bool is_cycle () const
 Retorna true si el camino conforma un ciclo.
bool is_empty () const
 Retorna true si el camino está vacío.
template<class Operation>
void operate_on_arcs (void *ptr)
 Ejecuta una operación sobre todos los arcos de un camino pasando un parámetro adicional por donde enviar o recibir información.
template<class Operation>
void operate_on_arcs ()
 Ejecuta una operación sobre todos los arcos de un camino.
template<class Operation>
void operate_on_nodes (void *ptr)
 Ejecuta una operación sobre todos los nodos de un camino pasando un parámetro adicional por donde enviar o recibir información.
template<class Operation>
void operate_on_nodes ()
 Ejecuta una operación sobre todos los nodos de un camino.
Path & operator= (const Path &path)
 Asignación de camino; limpia this y copia todos los nodos y arcos de path.
 Path (const Path &path)
 Constructor copia de camino; todos los nodos y arcos se copian.
 Path (GT &_g, Node *start_node)
 Constructor de camino sobre grafo a partir de un nodo inicial.
 Path ()
 Constructor vacío.
 Path (GT &_g)
 Constructor básico.
void remove_first_node ()
 Elimina el primer nodo del camino.
void remove_last_node ()
 Elimina el último nodo del camino.
void set_graph (GT &__g, Node *start_node=NULL)
 Limpia el camino this y los configura a un nuevo grafo.
const long & size () const
 Retorna la longitud del camino en nodos.
void swap (Path &path)
 Intercambias los contenidos del camino this con el de path.

Clases

class  Iterator
 Iterador sobre nodos y arcos de un camino. Más...

Descripción detallada

template<typename GT>
class Aleph::Path< GT >

Muchos problemas sobre grafos requieren la construcción dinámica de caminos. La clase Path<GT> modeliza un camino sobre un grafo de cualquier tipo. La clase está diseñada para construir caminos secuencialmente, mientras se visiten los nodos y arcos en el transcurso de ejecución de un algoritmo.

Los caminos se construyen por sus puntas, bien sea por su primer nodo o por su último nodo. Eventualmente, puede insertarse un camino dentro de un camino.

Parámetros:
GT el tipo de grafo.
Ver también:
Path::Iterator List_Graph

Definición en la línea 582 del archivo tpl_graph.H.

Documentación del constructor y destructor

Path ( GT &  _g  )  [inline]

Parámetros:
[in] _g grafo sobre el cual se construirá el camino.

Definición en la línea 616 del archivo tpl_graph.H.

Path ( GT &  _g,
Node *  start_node 
) [inline]

Parámetros:
[in] _g grafo sobre el cual se realizará el camino.
[in] start_node puntero a nodo por donde se inicia el camino.
Excepciones:
bad_alloc si no hay memoria.
Nota:
No se verifica si start_node pertenece al grafo.

Definición en la línea 636 del archivo tpl_graph.H.

Hace referencia a Path::init().

Documentación de las funciones miembro

void append ( Node *  node  )  [inline]

El método inserta el nodo node como último nodo del camino this.

El nodo node debe estar conectado por alguno de los arcos adyacentes al primer nodo del camino. De lo contrario se genera la excepción domain_error.

La operación busca secuencialmente entre todos los arcos del primer nodo del camino hasta encontrar un arco que conecte al nodo node. El tiempo de ejecución esperado es pues proporcional al número de arcos adyacentes del último nodo del camino.

Este método no es adecuado para multigrafos o multidigrafos, pues el arco asociado al camino será el primero que se encuentre hacia node entre todos los arcos adyacentes del último nodo del camino.

Luego de la operación node deviene el último nodo del camino.

Parámetros:
[in] node nodo a ser insertado en camino.
Excepciones:
bad_alloc si no hay memoria para insertar el arco.
invalid_argument si el arco no está conectado al último nodo del camino
domain_error si node no está conectado por ningún arco del último nodo del camino.

Definición en la línea 759 del archivo tpl_graph.H.

Hace referencia a Path::append(), Path::get_last_node(), y Path::init().

void append ( Arc *  arc  )  [inline]

El método inserta el arco arc e inserta su extremo como último nodo del camino this.

Uno de los extremos del arco debe ser el último nodo del camino.

La operación toma tiempo constante.

Después de la operación el último nodo del camino es extremo del arco recién insertado.

Esta es la operación más común y con más sentido para construir progresivamente un camino. Ella opera sobre todos los tipos de grafos, digrafos, multigrafos o multidigrafos.

Si se trata de un grafo, entonces el camino debe tener al menos un nodo insertado. De lo contrario, se dispara la excepción domain_error.

Parámetros:
[in] arc arco a ser insertado en camino.
Excepciones:
bad_alloc si no hay memoria para insertar el arco.
invalid_argument si el arco no está conectado al último nodo del camino
domain_error si el camino está vacío.

Definición en la línea 716 del archivo tpl_graph.H.

Referenciado por Path::append(), y Aleph::dijkstra_min_path().

void init ( Node *  start_node  )  [inline]

Parámetros:
start_node puntero a nodo por donde se inicia el camino.
Excepciones:
bad_alloc si no hay memoria.
Nota:
No se verifica si start_node pertenece al grafo.

Definición en la línea 625 del archivo tpl_graph.H.

Referenciado por Path::append(), Aleph::dijkstra_min_path(), Aleph::find_path_depth_first(), Path::insert(), Path::Path(), y Path::set_graph().

void insert ( Node *  node  )  [inline]

El método inserta el nodo node como primer nodo del camino this.

El nodo node debe estar conectado por alguno de los arcos adyacentes al primer nodo del camino. De lo contrario se genera la excepción domain_error.

La operación busca secuencialmente entre todos los arcos del primer nodo del camino hasta encontrar un arco que conecte al nodo node. El tiempo de ejecución esperado es pues proporcional al número de arcos adyacentes del primer nodo del camino.

Este método no es adecuado para multigrafos o multidigrafos, pues el arco asociado al camino será el primero que se encuentre hacia node entre todos los arcos adyacentes del último nodo del camino.

Luego de la operación node deviene el primer nodo del camino.

Parámetros:
[in] node nodo a ser insertado en camino.
Excepciones:
bad_alloc si no hay memoria para insertar el arco.
invalid_argument si el arco no está conectado al primer nodo del camino
domain_error si node no está conectado por ningún arco del primer nodo del camino.

Definición en la línea 845 del archivo tpl_graph.H.

Hace referencia a Path::get_first_node(), Path::init(), y Path::insert().

void insert ( Arc *  arc  )  [inline]

El método inserta el arco arc e inserta su extremo como primer nodo del camino this.

Uno de los extremos del arco debe ser el primer nodo del camino.

La operación toma tiempo constante.

Después de la operación el primer nodo del camino es extremo del arco recién insertado.

La operación opera sobre todos los tipos de grafos, digrafos, multigrafos o multidigrafos.

Si se trata de un grafo, entonces el camino debe tener al menos un nodo insertado. De lo contrario, se dispara la excepción domain_error.

Parámetros:
[in] arc arco a ser insertado en camino.
Excepciones:
bad_alloc si no hay memoria para insertar el arco.
invalid_argument si el arco no está conectado al primer nodo del camino
domain_error si el camino está vacío.

Definición en la línea 803 del archivo tpl_graph.H.

Referenciado por Path::insert().

void operate_on_arcs ( void *  ptr  )  [inline]

Este actuador recorre cada arco del camino y ejecuta la operación Operation(ptr)(arco).

Parámetros:
[in,out] ptr puntero opaco hacia información que se le transmite a la operación y por donde también puede recibir resultados.

Definición en la línea 990 del archivo tpl_graph.H.

void operate_on_arcs (  )  [inline]

Este actuador recorre cada arco del camino y ejecuta la operación Operation()(arco).

Definición en la línea 959 del archivo tpl_graph.H.

void operate_on_nodes ( void *  ptr  )  [inline]

Este actuador recorre cada nodo del camino y ejecuta la operación Operation(ptr)(node).

Parámetros:
[in,out] ptr puntero opaco hacia información que se le transmite a la operación y por donde también puede recibir resultados.

Definición en la línea 974 del archivo tpl_graph.H.

void operate_on_nodes (  )  [inline]

Este actuador recorre cada nodo del camino y ejecuta la operación Operation()(node).

Definición en la línea 949 del archivo tpl_graph.H.

void set_graph ( GT &  __g,
Node *  start_node = NULL 
) [inline]

El método limpia el camino this (se eliminan todos sus nodos y arcos) y reinicializa el camino a que se construya sobre el grafo __g con nodo inicial start_node.

Parámetros:
[in] __g grafo sobre el cual se realizará el camino.
[in] start_node puntero a nodo por donde se inicia el camino.
Excepciones:
bad_alloc si no hay memoria.
Nota:
No se verifica si start_node pertenece al grafo.

Definición en la línea 651 del archivo tpl_graph.H.

Hace referencia a Path::clear_path(), y Path::init().

La documentación para esta clase fue generada a partir del siguiente fichero:
Leandro R. León