#include <tpl_graph.H>

Clases
class	Iterator

Tipos públicos
typedef GT::Node_Type	Node_Type
	El tipo de atributo que contienen los nodos del camino.

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.

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

Métodos públicos
GT &	get_graph () const
	Obtiene una referencia al grafo sobre el cual se encuentra el camino.

void *&	get_cookie ()

bool	inside_graph (GT &gr) const
	retorna true si el camino this refiere al grafo gr

	Path (GT &_g, void *__cookie=NULL)

	Path ()
	Constructor vacío.

void	init (Node *start_node)

	Path (GT &_g, Node start_node, void __cookie=NULL)

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

const size_t &	size () const
	Retorna la longitud del camino en nodos.

bool	is_empty () const
	Retorna true si el camino está vacío.

void	clear_path ()
	Limpia el camino (se eliminan todos sus nodos y arcos).

void	clear ()

	Path (const Path &path)
	Constructor copia de camino; todos los nodos y arcos se copian.

Path &	operator= (const Path &path)
	Asignación de camino; limpia this y copia todos los nodos y arcos de path.

void	append (Arc *arc)

void	append (Node *node)

void	insert (Arc *arc)

void	insert (Node *node)

Node *	get_first_node () const
	Retorna el primer nodo del camino.

Node *	get_last_node () const
	Retorna el último nodo del camino.

Arc *	get_first_arc ()
	Retorna el primer arco del camino.

Arc *	get_last_arc ()
	Retorna el último arco del camino.

bool	is_cycle () const
	Retorna true si el camino conforma un ciclo.

void	remove_last_node ()
	Elimina el último nodo del camino.

void	remove_first_node ()
	Elimina el primer nodo del camino.

void	swap (Path &path)
	Intercambias los contenidos del camino this con el de path.

template<class Operation >
void	for_each_node (Operation &op) const

template<class Operation >
void	for_each_node (Operation &&op=Operation()) const

template<class Operation >
void	for_each_arc (Operation &op) const

template<class Operation >
void	for_each_arc (Operation &&op=Operation()) const

bool	contains_node (Node *node) const
	Retorna true si nodo pertenece al camino; false de lo contrario.

bool	contains_arc (Arc *arc) const
	Retorna true si nodo pertenece al camino; false de lo contrario.

template<template< typename > class Container = DynList>
Container< Node * >	nodes () const

template<template< typename > class Container = DynList>
Container< Arc * >	arcs () const

bool	operator== (const Path &p) const

bool	operator!= (const Path &p) const

GT &	get_graph ()
	Obtiene una referencia al grafo sobre el cual se encuentra el camino.

void *&	get_cookie ()

bool	inside_graph (GT &gr) const
	retorna true si el camino this refiere al grafo gr

	Path (GT &_g, void *__cookie=NULL)

	Path ()
	Constructor vacío.

void	init (Node *start_node)

	Path (GT &_g, Node start_node, void __cookie=NULL)

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

const size_t &	size () const
	Retorna la longitud del camino en nodos.

bool	is_empty () const
	Retorna true si el camino está vacío.

void	clear_path ()
	Limpia el camino (se eliminan todos sus nodos y arcos).

void	clear ()

	Path (const Path &path)
	Constructor copia de camino; todos los nodos y arcos se copian.

Path &	operator= (const Path &path)
	Asignación de camino; limpia this y copia todos los nodos y arcos de path.

void	append (Arc *arc)

void	append (Node *node)

void	insert (Arc *arc)

void	insert (Node *node)

Node *	get_first_node ()
	Retorna el primer nodo del camino.

Node *	get_last_node ()
	Retorna el último nodo del camino.

Arc *	get_first_arc ()
	Retorna el primer arco del camino.

Arc *	get_last_arc ()
	Retorna el último arco del camino.

bool	is_cycle () const
	Retorna true si el camino conforma un ciclo.

void	remove_last_node ()
	Elimina el último nodo del camino.

void	remove_first_node ()
	Elimina el primer nodo del camino.

void	swap (Path &path)
	Intercambias los contenidos del camino this con el de path.

template<class Operation >
void	operate_on_nodes (Operation &&op=Operation())

template<class Operation >
void	operate_on_arcs (Operation &&op=Operation())

template<class Operation >
void	operate_on_nodes (void *ptr)

template<class Operation >
void	operate_on_arcs (void *ptr)

bool	contains_node (Node *node)
	Retorna true si nodo pertenece al camino; false de lo contrario.

bool	contains_arc (Arc *arc)
	Retorna true si nodo pertenece al camino; false de lo contrario.

Descripción detallada

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

Camino sobre un grafo.

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

Documentación del constructor y destructor

template<class GT>

Aleph::Path< GT >::Path	(	GT &	_g,
		void *	__cookie = `NULL`
	)

inline

Constructor básico.

Parámetros

[in]	_g	grafo sobre el cual se construirá el camino.
[in]	__cookie	un cookie para a asociar al camino.

template<class GT>

Aleph::Path< GT >::Path	(	GT &	_g,
		Node *	start_node,
		void *	__cookie = `NULL`
	)

inline

Constructor de camino sobre grafo a partir de un nodo inicial.

Parámetros

[in]	_g	grafo sobre el cual se realizará el camino.
[in]	start_node	puntero a nodo por donde se inicia el camino.
[in]	__cookie	un cookie para a asociar al camino.

Excepciones

bad_alloc si no hay memoria.

Nota: No se verifica si start_node pertenece al grafo.

Hace referencia a Aleph::Path< GT >::init().

Gráfico de llamadas para esta función:

template<class GT>

Aleph::Path< GT >::Path	(	GT &	_g,
		void *	__cookie = `NULL`
	)

inline

Constructor básico.

Parámetros

[in]	_g	grafo sobre el cual se construirá el camino.
[in]	__cookie	un cookie para a asociar al camino.

template<class GT>

Aleph::Path< GT >::Path	(	GT &	_g,
		Node *	start_node,
		void *	__cookie = `NULL`
	)

inline

Constructor de camino sobre grafo a partir de un nodo inicial.

Parámetros

[in]	_g	grafo sobre el cual se realizará el camino.
[in]	start_node	puntero a nodo por donde se inicia el camino.
[in]	__cookie	un cookie para a asociar al camino.

Excepciones

bad_alloc si no hay memoria.

Nota: No se verifica si start_node pertenece al grafo.

Documentación de las funciones miembro

template<class GT>

void Aleph::Path< GT >::append ( Arc * arc )

inline

Concatena un arco al camino.

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.

template<class GT>

void Aleph::Path< GT >::append ( Node * node )

inline

Concatena un nodo al camino.

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.

Hace referencia a Aleph::search_arc().

Gráfico de llamadas para esta función:

template<class GT>

void Aleph::Path< GT >::append ( Arc * arc )

inline

Concatena un arco al camino.

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.

Referenciado por Aleph::Path< GT >::append(), find_min_path(), Aleph::find_min_path(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::get_min_path() y Aleph::search_cycle().

Gráfico de llamadas a esta función:

template<class GT>

void Aleph::Path< GT >::append ( Node * node )

inline

Concatena un nodo al camino.

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.

Hace referencia a Aleph::Path< GT >::append(), Aleph::Path< GT >::get_last_node(), Aleph::Path< GT >::init() y Aleph::search_arc().

Gráfico de llamadas para esta función:

template<class GT>

void Aleph::Path< GT >::clear ( )

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.

template<class GT>

void Aleph::Path< GT >::clear ( )

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::Path< GT >::clear_path().

Gráfico de llamadas para esta función:

template<class GT>

template<class Operation >

void Aleph::Path< GT >::for_each_arc ( Operation & op ) const

inline

Ejecuta una operación sobre todos los arcos de un camino.

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

Parámetros

[in,out] op operación a ejecutar sobre cada arco

Hace referencia a Aleph::Path< GT >::Iterator::has_current_arc().

Gráfico de llamadas para esta función:

template<class GT>

template<class Operation >

void Aleph::Path< GT >::for_each_node ( Operation & op ) const

inline

Ejecuta una operación sobre todos los nodos de un camino.

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

Parámetros

[in,out] op operación a ejecutar sobre cada nodo

Hace referencia a Aleph::Dlink::Iterator::has_current().

Gráfico de llamadas para esta función:

template<class GT>

void Aleph::Path< GT >::init ( Node * start_node )

inline

Inicializa un camino que comienza en start_node.

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.

template<class GT>

void Aleph::Path< GT >::init ( Node * start_node )

inline

Inicializa un camino que comienza en start_node.

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.

Referenciado por Aleph::Path< GT >::append(), Aleph::find_path_depth_first(), Aleph::Dijkstra_Min_Paths< GT, Distance, Plus, SA >::get_min_path(), Aleph::Path< GT >::insert(), Aleph::Path< GT >::Path() y Aleph::Path< GT >::set_graph().

Gráfico de llamadas a esta función:

template<class GT>

void Aleph::Path< GT >::insert ( Arc * arc )

inline

Inserta un arco al camino como el primero.

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.

Hace referencia a Aleph::list< T >::insert().

Gráfico de llamadas para esta función:

template<class GT>

void Aleph::Path< GT >::insert ( Node * node )

inline

Inserta un nodo como primero del camino.

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.

Hace referencia a Aleph::search_arc().

Gráfico de llamadas para esta función:

template<class GT>

void Aleph::Path< GT >::insert ( Arc * arc )

inline

Inserta un arco al camino como el primero.

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.

Hace referencia a Aleph::list< T >::insert().

Referenciado por Aleph::find_path_breadth_first() y Aleph::Path< GT >::insert().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

template<class GT>

void Aleph::Path< GT >::insert ( Node * node )

inline

Inserta un nodo como primero del camino.

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.

Hace referencia a Aleph::Path< GT >::get_first_node(), Aleph::Path< GT >::init(), Aleph::Path< GT >::insert() y Aleph::search_arc().

Gráfico de llamadas para esta función:

template<class GT>

template<class Operation >

void Aleph::Path< GT >::operate_on_arcs ( Operation && op = Operation() )

inline

Ejecuta una operación sobre todos los arcos de un camino.

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

Parámetros

[in,out] op operación a ejecutar sobre cada arco

Hace referencia a Aleph::Dlink::Iterator::has_current().

Gráfico de llamadas para esta función:

template<class GT>

template<class Operation >

void Aleph::Path< GT >::operate_on_arcs ( void * ptr )

inline

Ejecuta una operación sobre todos los arcos de un camino pasando un parámetro adicional por donde enviar o recibir información.

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.

Hace referencia a Aleph::Path< GT >::Iterator::has_current_arc().

Gráfico de llamadas para esta función:

template<class GT>

template<class Operation >

void Aleph::Path< GT >::operate_on_nodes ( Operation && op = Operation() )

inline

Ejecuta una operación sobre todos los nodos de un camino.

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

Parámetros

[in,out] op operación a ejecutar sobre cada nodo

Hace referencia a Aleph::Dlink::Iterator::has_current().

Gráfico de llamadas para esta función:

template<class GT>

template<class Operation >

void Aleph::Path< GT >::operate_on_nodes ( void * ptr )

inline

Ejecuta una operación sobre todos los nodos de un camino pasando un parámetro adicional por donde enviar o recibir información.

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.

Hace referencia a Aleph::Path< GT >::Iterator::has_current_node().

Gráfico de llamadas para esta función:

template<class GT>

void Aleph::Path< GT >::set_graph	(	GT &	__g,
		Node *	start_node = `NULL`
	)

inline

Limpia el camino this y los configura a un nuevo grafo.

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.

template<class GT>

void Aleph::Path< GT >::set_graph	(	GT &	__g,
		Node *	start_node = `NULL`
	)

inline

Limpia el camino this y los configura a un nuevo grafo.

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