#include <tpl_graph.H>

Diagrama de herencias de Aleph::List_Graph< __Graph_Node, __Graph_Arc >

Diagrama de colaboración para Aleph::List_Graph< __Graph_Node, __Graph_Arc >:

Clases
class	Arc_Iterator

class	Node_Arc_Iterator

class	Node_Iterator

Tipos públicos
typedef __Graph_Node	Node

typedef __Graph_Arc	Arc

typedef Node::Node_Info	Node_Type

typedef Arc::Arc_Info	Arc_Type

Tipos públicos heredados desde Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >
typedef __Graph_Node	Node

typedef __Graph_Arc	Arc

typedef Node::Node_Type	Node_Type

typedef Arc::Arc_Type	Arc_Type

Métodos públicos
virtual Node *	insert_node (Node *node)

virtual Node *	insert_node (const Node_Type &node_info)

virtual Node *	insert_node (Node_Type &&node_info=Node_Type())
	overload insert_node

virtual void	remove_node (Node *node)

Node *	get_first_node () const

Arc *	get_first_arc (Node *) const

virtual Arc *	insert_arc (Node src_node, Node tgt_node, const typename Arc::Arc_Type &arc_info)

virtual Arc *	insert_arc (Node src_node, Node tgt_node, typename Arc::Arc_Type &&arc_info)

virtual Arc *	insert_arc (Node src_node, Node tgt_node)

virtual void	remove_arc (Arc *arc)

virtual void	disconnect_arc (Arc *arc)

virtual Arc *	connect_arc (Arc *arc)

Arc *	get_first_arc () const

template<class Compare >
void	sort_arcs (Compare &&cmp=Compare())

template<class Compare >
void	sort_arcs (Compare &cmp)

	List_Graph (const List_Graph &g)

	List_Graph (List_Graph &&g)

List_Graph &	operator= (const List_Graph &g)

List_Graph &	operator= (List_Graph &&g)

virtual	~List_Graph ()

void	swap (List_Graph &g)

	GRAPH_FUNCTIONAL_METHODS (List_Graph)

virtual Node *	insert_node (Node *node)

virtual Node *	insert_node (const Node_Type &node_info)

virtual Node *	insert_node (Node_Type &&node_info=Node_Type())
	overload insert_node

virtual void	remove_node (Node *node)

Node *	get_first_node ()

Arc *	get_first_arc (Node *)

virtual Arc *	insert_arc (Node src_node, Node tgt_node, const typename Arc::Arc_Type &arc_info)

virtual Arc *	insert_arc (Node src_node, Node tgt_node, typename Arc::Arc_Type &&arc_info)

virtual Arc *	insert_arc (Node src_node, Node tgt_node)

virtual void	remove_arc (Arc *arc)

virtual void	disconnect_arc (Arc *arc)

virtual Arc *	connect_arc (Arc *arc)

Arc *	get_first_arc ()

template<class Compare >
void	sort_arcs (Compare &&cmp=Compare())

template<class Compare >
void	sort_arcs (Compare &cmp)

	List_Graph (const List_Graph &g)

	List_Graph (List_Graph &&g)

List_Graph &	operator= (const List_Graph &g)

List_Graph &	operator= (List_Graph &&g)

virtual	~List_Graph ()

void	swap (List_Graph &g)

Métodos públicos heredados desde Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >
	Aleph_Graph (bool _digraph)

void *&	get_cookie ()

bool	is_digraph () const

const size_t &	get_num_nodes () const

const size_t &	vsize () const

Node *	get_src_node (Arc *arc)

Node *	get_tgt_node (Arc *arc)

Node *	get_connected_node (Arc arc, Node node)

const size_t &	get_num_arcs () const

const size_t &	esize () const

const size_t &	get_num_arcs (Node *node) const

Bit_Fields &	get_control_bits (Node *node)

void	reset_bit (Node *node, const int &bit)

void	reset_bits (Node *node)

void	set_bit (Node *node, const int bit, const int value)

Bit_Fields &	get_control_bits (Arc *arc)

void	reset_bit (Arc *arc, const int bit)

void	reset_bits (Arc *arc)

void	set_bit (Arc *arc, const int bit, const int value)

void *&	get_cookie (Node *node)

void *&	get_cookie (Arc *arc)

long &	get_counter (Node *node)

void	reset_counter (Node *node)

void	reset_node (Node *node)

long &	get_counter (Arc *arc)

void	reset_counter (Arc *arc)

void	reset_arc (Arc *arc)

Atributos públicos
	GRAPH_SEARCH_METHODS

	GRAPH_ITERATIVE_METHODS

Otros miembros heredados
Métodos públicos estáticos heredados desde Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >
template<class N1 , class N2 >
static void	map_nodes (N1 p, N2 q)

template<class A1 , class A2 >
static void	map_arcs (A1 p, A2 q)

Métodos protegidos heredados desde Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >
void	init ()

void	common_swap (Aleph_Graph &g)

Atributos protegidos heredados desde Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >
void *	cookie

size_t	num_nodes

size_t	num_arcs

bool	digraph

Descripción detallada

template<typename __Graph_Node, typename __Graph_Arc>
class Aleph::List_Graph< __Graph_Node, __Graph_Arc >

Clase grafo implementado con listas de adyacencia.

List_Graph<Node, Arc> es una clase que modeliza grafos representados mediante listas de adyacencia.

La clase maneja dos parámetros tipo fundamentales:

__Graph_Node: el tipo de los nodos que debe estar definido mediante la clase Graph_Node.
__Graph_Arc: el tipo de los nodos que debe estar definido mediante la clase Graph_Arc.

Estas clases deben haberse definido previamente.

Una vez instanciado un List_Graph<Node, Arc>, los nodos y arcos deben accederse mediante los tipos internos:

List_Graph<Node, Arc>::Node
List_Graph<Node, Arc>::Arc

Parámetros

__Graph_Node	El tipo de nodo. Debe estar definido a partir de la clase `__Graph_Node`, bien sea por inclusión de atributos, por derivación o por combinación de ambos
__Graph_Arc	El tipo de arco. Debe estar definido a partir de la clase `__Graph_Arc`, bien sea por inclusión de atributos, por derivación o por combinación de ambos

Ver también: Graph_Node Graph_Arc; List_Digraph Path

Documentación del constructor y destructor

template<typename Node , typename Arc >

Aleph::List_Graph< Node, Arc >::List_Graph ( const List_Graph< __Graph_Node, __Graph_Arc > & g )

inline

Constructor copia de un grafo.

Instancia un nuevo grafo copia de g. Toda la estructura es copiada con contenidos tanto en los nodos como en los arcos.

Parámetros

[in] g grafo a copiar

Excepciones

bad_alloc si no hay suficiente memoria para la copia.

Nota: La copia no incluye los atributos de control del grafo (bit, contador y cookies)

Hace referencia a Aleph::copy_graph().

Gráfico de llamadas para esta función:

template<typename Node , typename Arc >

Aleph::List_Graph< Node, Arc >::~List_Graph ( )

inlinevirtual

destruye enteramente el grafo (nodos y arcos se eliminan y la memoria se libera.

Hace referencia a Aleph::clear_graph().

Gráfico de llamadas para esta función:

template<typename __Graph_Node, typename __Graph_Arc>

Aleph::List_Graph< __Graph_Node, __Graph_Arc >::List_Graph ( const List_Graph< __Graph_Node, __Graph_Arc > & g )

inline

Constructor copia de un grafo.

Instancia un nuevo grafo copia de g. Toda la estructura es copiada con contenidos tanto en los nodos como en los arcos.

Parámetros

[in] g grafo a copiar

Excepciones

bad_alloc si no hay suficiente memoria para la copia.

Nota: La copia no incluye los atributos de control del grafo (bit, contador y cookies)

template<typename __Graph_Node, typename __Graph_Arc>

virtual Aleph::List_Graph< __Graph_Node, __Graph_Arc >::~List_Graph ( )

inlinevirtual

destruye enteramente el grafo (nodos y arcos se eliminan y la memoria se libera.

Documentación de las funciones miembro

template<typename Node , typename Arc >

Arc * Aleph::List_Graph< Node, Arc >::connect_arc ( Arc * arc )

inlinevirtual

Conecta un arco previamente insertado y desconectado.

Este método toma un puntero a un arco arc, previamente desconectado mediante, disconnect_arc(), y lo re-inserta en el grafo.

El arco, por supuesto, debe haber sido previamente insertado en el grafo. A este respecto, no se hace ninguna verificación.

No se realiza ninguna verificación de existencia previa de un arco entre los nodos involucrados (esto es necesario para operar con multigrafos).

Parámetros

[in] arc puntero al arco a re-insertar.

Devuelve: puntero al arco re-insertado

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

Hace referencia a Aleph::Dlink::append().

Gráfico de llamadas para esta función:

template<typename __Graph_Node, typename __Graph_Arc>

virtual Arc* Aleph::List_Graph< __Graph_Node, __Graph_Arc >::connect_arc ( Arc * arc )

inlinevirtual

Conecta un arco previamente insertado y desconectado.

Este método toma un puntero a un arco arc, previamente desconectado mediante, disconnect_arc(), y lo re-inserta en el grafo.

El arco, por supuesto, debe haber sido previamente insertado en el grafo. A este respecto, no se hace ninguna verificación.

No se realiza ninguna verificación de existencia previa de un arco entre los nodos involucrados (esto es necesario para operar con multigrafos).

Parámetros

[in] arc puntero al arco a re-insertar.

Devuelve: puntero al arco re-insertado

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

template<typename Node , typename Arc >

void Aleph::List_Graph< Node, Arc >::disconnect_arc ( Arc * arc )

inlinevirtual

Desconecta el arco arc.

La operación desconecta del grafo el arco arc. Eventualmente, el arco puede guardarse y luego reinsertarse mediante connect_arc().

El arco debe pertenecer al grafo y no se realiza ninguna verificación al respecto.

Parámetros

[in] arc puntero al arco a desconectar

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

Hace referencia a Aleph::Dlink::del().

Gráfico de llamadas para esta función:

template<typename __Graph_Node, typename __Graph_Arc>

virtual void Aleph::List_Graph< __Graph_Node, __Graph_Arc >::disconnect_arc ( Arc * arc )

inlinevirtual

Desconecta el arco arc.

La operación desconecta del grafo el arco arc. Eventualmente, el arco puede guardarse y luego reinsertarse mediante connect_arc().

El arco debe pertenecer al grafo y no se realiza ninguna verificación al respecto.

Parámetros

[in] arc puntero al arco a desconectar

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

template<typename Node , typename Arc >

Arc * Aleph::List_Graph< Node, Arc >::get_first_arc ( ) const

inline

Retorna el primer arco del grafo.

Esta rutina debe considerarse como un punto de entrada al grafo independientemente del valor del arc. Por lo general, no es recomendable asumir cuál será el nodo retornado por esta rutina. Sin embargo, a la excepción de su equivalente para nodos, los arcos pueden ordenarse según algún criterio específico de comparación (pesos por ejemplo). Consecuentemente, en caso de ordenamiento, el primer arco a retornar será el menor (o mayor) según el criterio de ordenamiento.

Devuelve: puntero al primer nodo del grafo.

Ver también: sort_arcs()

template<typename Node , typename Arc >

Arc * Aleph::List_Graph< Node, Arc >::get_first_arc ( )

inlinevirtual

Retorna el primer arco del grafo.

Esta rutina debe considerarse como un punto de entrada al grafo independientemente del valor del arc. Por lo general, no es recomendable asumir cuál será el nodo retornado por esta rutina. Sin embargo, a la excepción de su equivalente para nodos, los arcos pueden ordenarse según algún criterio específico de comparación (pesos por ejemplo). Consecuentemente, en caso de ordenamiento, el primer arco a retornar será el menor (o mayor) según el criterio de ordenamiento.

Devuelve: puntero al primer nodo del grafo.

Ver también: sort_arcs()

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

template<typename Node , typename Arc >

Node * Aleph::List_Graph< Node, Arc >::get_first_node ( ) const

inline

Retorna el primer nodo del grafo.

Esta rutina debe considerarse como un punto de entrada al grafo independientemente del valor del nodo. No debe asumirse ninguna consideración acerca cuál será el nodo retornado por esta rutina.

Devuelve: puntero al primer nodo del grafo.

template<typename Node , typename Arc >

Node * Aleph::List_Graph< Node, Arc >::get_first_node ( )

inlinevirtual

Retorna el primer nodo del grafo.

Esta rutina debe considerarse como un punto de entrada al grafo independientemente del valor del nodo. No debe asumirse ninguna consideración acerca cuál será el nodo retornado por esta rutina.

Devuelve: puntero al primer nodo del grafo.

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

template<typename Node , typename Arc >

Arc * Aleph::List_Graph< Node, Arc >::insert_arc	(	Node *	src_node,
		Node *	tgt_node,
		const typename Arc::Arc_Type &	arc_info
	)

inlinevirtual

Crea un nuevo arco entre dos nodos.

Este método aparta memoria para un nuevo arco entre los nodos previamente definidos, src_node y tgt_node con valor de contenido en el arco arc_info.

Los nodos deben haber sido previamente insertados en el grafo. A este respecto, no se hace ninguna verificación. El operador de asignación de la clase Arc::Arc_Type debe haber sido definido.

No se realiza ninguna verificación de existencia previa de un arco entre los nodos involucrados (esto es necesario para operar con multigrafos).

Parámetros

[in]	src_node	puntero al nodo origen.
[in]	tgt_node	puntero al nodo destino.
[in]	arc_info	valor de información a ser copiado en el arco.

Devuelve: puntero al arco insertado

Excepciones

bad_alloc si no hay memoria para el arco.

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

template<typename __Graph_Node, typename __Graph_Arc>

virtual Arc* Aleph::List_Graph< __Graph_Node, __Graph_Arc >::insert_arc	(	Node *	src_node,
		Node *	tgt_node,
		const typename Arc::Arc_Type &	arc_info
	)

inlinevirtual

Crea un nuevo arco entre dos nodos.

Este método aparta memoria para un nuevo arco entre los nodos previamente definidos, src_node y tgt_node con valor de contenido en el arco arc_info.

Los nodos deben haber sido previamente insertados en el grafo. A este respecto, no se hace ninguna verificación. El operador de asignación de la clase Arc::Arc_Type debe haber sido definido.

No se realiza ninguna verificación de existencia previa de un arco entre los nodos involucrados (esto es necesario para operar con multigrafos).

Parámetros

[in]	src_node	puntero al nodo origen.
[in]	tgt_node	puntero al nodo destino.
[in]	arc_info	valor de información a ser copiado en el arco.

Devuelve: puntero al arco insertado

Excepciones

bad_alloc si no hay memoria para el arco.

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

template<typename Node , typename Arc >

Node * Aleph::List_Graph< Node, Arc >::insert_node ( Node * node )

inlinevirtual

Inserción de un nodo cuya memoria ya ha sido apartada.

Este método asume un nodo de tipo List_Graph::Node apuntado por el parámetro node y lo inserta en el grafo.

Parámetros

[in] node puntero a un nodo ya creado que no pertenece a ningún grafo.

Devuelve: Puntero al nodo insertado.

Nota: Puesto que cuando se elimine el nodo o se destruya el grafo se invocará al operador delete, node debe haber sido imperativamente apartado con new.; Por lo general, esta rutina no debe usarse. En su lugar debe utilizarse la otra inserción (que aparta memoria automáticamente.

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

Reimplementado en Aleph::Euclidian_Graph< __Euclidian_Node, __Euclidian_Arc >.

Hace referencia a Aleph::Dlink::append().

Referenciado por Aleph::Euclidian_Graph< __Euclidian_Node, __Euclidian_Arc >::insert_node() y Aleph::List_Graph< __Graph_Node, __Graph_Arc >::insert_node().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

template<typename __Graph_Node, typename __Graph_Arc>

virtual Node* Aleph::List_Graph< __Graph_Node, __Graph_Arc >::insert_node ( const Node_Type & node_info )

inlinevirtual

Crea un nuevo nodo en un grafo.

Este método aparta memoria para un nodo de tipo List_Graph::Node y le asigna como atributo el valor node_info.

Parámetros

[in] node_info Información que se desea copiar en el nodo. Es imperativo que exista el constructor copia Node_Info.

Devuelve: puntero al nodo recién creado.

Excepciones

bad_alloc si no hay memoria para el nuevo.

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

Reimplementado en Aleph::Euclidian_Graph< __Euclidian_Node, __Euclidian_Arc >.

template<typename __Graph_Node, typename __Graph_Arc>

virtual Node* Aleph::List_Graph< __Graph_Node, __Graph_Arc >::insert_node ( Node * node )

inlinevirtual

Inserción de un nodo cuya memoria ya ha sido apartada.

Este método asume un nodo de tipo List_Graph::Node apuntado por el parámetro node y lo inserta en el grafo.

Parámetros

[in] node puntero a un nodo ya creado que no pertenece a ningún grafo.

Devuelve: Puntero al nodo insertado.

Nota: Puesto que cuando se elimine el nodo o se destruya el grafo se invocará al operador delete, node debe haber sido imperativamente apartado con new.; Por lo general, esta rutina no debe usarse. En su lugar debe utilizarse la otra inserción (que aparta memoria automáticamente.

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

Reimplementado en Aleph::Euclidian_Graph< __Euclidian_Node, __Euclidian_Arc >.

template<typename __Graph_Node, typename __Graph_Arc>

virtual Node* Aleph::List_Graph< __Graph_Node, __Graph_Arc >::insert_node ( const Node_Type & node_info )

inlinevirtual

Crea un nuevo nodo en un grafo.

Este método aparta memoria para un nodo de tipo List_Graph::Node y le asigna como atributo el valor node_info.

Parámetros

[in] node_info Información que se desea copiar en el nodo. Es imperativo que exista el constructor copia Node_Info.

Devuelve: puntero al nodo recién creado.

Excepciones

bad_alloc si no hay memoria para el nuevo.

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

Reimplementado en Aleph::Euclidian_Graph< __Euclidian_Node, __Euclidian_Arc >.

template<typename Node , typename Arc >

List_Graph< Node, Arc > & Aleph::List_Graph< Node, Arc >::operator= ( const List_Graph< __Graph_Node, __Graph_Arc > & g )

inline

Asignación de grafo.

Limpia todos el grafo this (sus nodos y arcos son eliminados y la memoria es liberada); luego copia enteramente el grafo g a this.

Parámetros

[in] g el grafo a asignar

Excepciones

bad_alloc si no hay suficiente memoria para la copia.

Nota: La copia no incluye los atributos de control del grafo (bit, contador y cookies)

Hace referencia a Aleph::copy_graph().

Gráfico de llamadas para esta función:

template<typename __Graph_Node, typename __Graph_Arc>

List_Graph& Aleph::List_Graph< __Graph_Node, __Graph_Arc >::operator= ( const List_Graph< __Graph_Node, __Graph_Arc > & g )

inline

Asignación de grafo.

Limpia todos el grafo this (sus nodos y arcos son eliminados y la memoria es liberada); luego copia enteramente el grafo g a this.

Parámetros

[in] g el grafo a asignar

Excepciones

bad_alloc si no hay suficiente memoria para la copia.

Nota: La copia no incluye los atributos de control del grafo (bit, contador y cookies)

template<typename Node , typename Arc >

void Aleph::List_Graph< Node, Arc >::remove_arc ( Arc * arc )

inlinevirtual

Elimina el arco arc.

La operación elimina del grafo el arco arc y luego libera su memoria.

El arco debe pertenecer al grafo y no se realiza ninguna verificación al respecto.

Parámetros

[in] arc puntero al arco a eliminar.

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

Hace referencia a Aleph::Dlink::del().

Referenciado por Aleph::List_Graph< __Graph_Node, __Graph_Arc >::remove_node().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

template<typename __Graph_Node, typename __Graph_Arc>

virtual void Aleph::List_Graph< __Graph_Node, __Graph_Arc >::remove_arc ( Arc * arc )

inlinevirtual

Elimina el arco arc.

La operación elimina del grafo el arco arc y luego libera su memoria.

El arco debe pertenecer al grafo y no se realiza ninguna verificación al respecto.

Parámetros

[in] arc puntero al arco a eliminar.

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

template<typename Node , typename Arc >

void Aleph::List_Graph< Node, Arc >::remove_node ( Node * node )

inlinevirtual

Elimina un nodo junto con todos sus arcos.

Esta rutina elimina todos los arcos del nodo node y luego elimina el mismo nodo. Toda la memoria ocupada por los arcos y el nodo es liberada.

Parámetros

[in] node nodo a ser eliminado.

Nota: Si this es un digrafo, este método puede ser muy ineficiente, pues requiere recorrer todos los arcos del digrafo y eliminar aquellos que apunten a node. En general no es recomendable usar esta rutina sobre digrafos.

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

Hace referencia a Aleph::Dlink::Iterator::has_current() y Aleph::List_Graph< __Graph_Node, __Graph_Arc >::remove_arc().

Gráfico de llamadas para esta función:

template<typename __Graph_Node, typename __Graph_Arc>

virtual void Aleph::List_Graph< __Graph_Node, __Graph_Arc >::remove_node ( Node * node )

inlinevirtual

Elimina un nodo junto con todos sus arcos.

Esta rutina elimina todos los arcos del nodo node y luego elimina el mismo nodo. Toda la memoria ocupada por los arcos y el nodo es liberada.

Parámetros

[in] node nodo a ser eliminado.

Nota: Si this es un digrafo, este método puede ser muy ineficiente, pues requiere recorrer todos los arcos del digrafo y eliminar aquellos que apunten a node. En general no es recomendable usar esta rutina sobre digrafos.

Implementa Aleph::Aleph_Graph< __Graph_Node, __Graph_Arc >.

template<typename Node , typename Arc >

template<class Compare >

void Aleph::List_Graph< Node, Arc >::sort_arcs ( Compare && cmp = Compare() )

inline

Ordena los arcos de un grafo.

Ordena los arcos de un grafo según el criterio de comparación Compare.

Parámetros

[in,out] cmp operación de compración.

template<typename __Graph_Node, typename __Graph_Arc>

template<class Compare >

void Aleph::List_Graph< __Graph_Node, __Graph_Arc >::sort_arcs ( Compare && cmp = Compare() )

inline

Ordena los arcos de un grafo.

Ordena los arcos de un grafo según el criterio de comparación Compare.

Parámetros

[in,out] cmp operación de compración.

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

Clases

Tipos públicos

Métodos públicos

Atributos públicos

Otros miembros heredados

Descripción detallada

template<typename __Graph_Node, typename __Graph_Arc> class Aleph::List_Graph< __Graph_Node, __Graph_Arc >

Documentación del constructor y destructor

Documentación de las funciones miembro

template<typename __Graph_Node, typename __Graph_Arc>
class Aleph::List_Graph< __Graph_Node, __Graph_Arc >