#include <tpl_netcapgraph.H>

Diagrama de herencias de Aleph::Net_Cap_Graph< NodeT, ArcT >

Diagrama de colaboración para Aleph::Net_Cap_Graph< NodeT, ArcT >:

Tipos públicos
typedef Net_Graph< NodeT, ArcT >	Net_Class
	La clase de red tradicional.

typedef ArcT	Arc
	Tipo de arco.

typedef NodeT	Node
	Tipo de node.

typedef Arc::Flow_Type	Flow_Type
	Tipo que representa la capacidad y el flujo.

typedef Node::Node_Type	Node_Type
	Tipo de atributo que almacena un nodo.

typedef Arc::Arc_Type	Arc_Type
	Tipo de atributo que almacena un arco.

typedef Net_Graph< Net_Node < Empty_Class, Flow_Type > , Net_Arc< bool, Flow_Type > >	Aux_Net

Tipos públicos heredados desde Aleph::Net_Graph< NodeT, ArcT >
typedef Array_Digraph< NodeT, ArcT >	Digraph

typedef ArcT	Arc
	Tipo de arco.

typedef NodeT	Node
	Tipo de node.

typedef Arc::Flow_Type	Flow_Type
	Tipo que representa la capacidad y el flujo.

typedef Node::Node_Type	Node_Type
	Tipo de atributo que almacena un nodo.

typedef Arc::Arc_Type	Arc_Type
	Tipo de atributo que almacena un arco.

Tipos públicos heredados desde Aleph::Array_Digraph< NodeT, ArcT >
typedef NodeT	Node

typedef ArcT	Arc

Métodos públicos
Node *	insert_node (const Node_Type &node_info, const Flow_Type &cap=numeric_limits< Flow_Type >::max())

Aux_Net *	get_aux_net ()

Aux_Net *	compute_aux_net ()

void	update ()

void	free_aux_net ()

Métodos públicos heredados desde Aleph::Net_Graph< NodeT, ArcT >
Flow_Type	get_in_cap (Node *node) const
	Retorna la capacidad total de entrada del nodo node.

Flow_Type	get_out_cap (Node *node) const
	Retorna la capacidad total de salida del nodo node.

size_t	get_in_degree (Node *node) const

size_t	get_out_degree (Node *node) const

Flow_Type	get_out_flow (Node *node) const
	Retorna el valor de flujo de salida del nodo.

Flow_Type	get_in_flow (Node *node) const
	Retorna el valor de flujo de entrada del nodo.

bool	is_source (Node *node)
	Retorna true si node es fuente.

bool	is_sink (Node *node)
	Retorna true si node es sumidero.

bool	is_connected (Node *node) const

bool	check_node (Node *node)

Aleph::set< Node * > &	get_src_nodes ()
	Retorna el conjunto de nodos fuente que contiene la red.

Aleph::set< Node * > &	get_sink_nodes ()
	Retorna el conjunto de nodos sumidero que contiene la red.

void	make_super_source ()

void	unmake_super_source ()

void	make_super_sink ()

void	unmake_super_sink ()

void	make_super_nodes ()

void	unmake_super_nodes ()

Node *	get_source ()
	Retorna un nodo fuente de la red.

Node *	get_sink ()
	Retorna un nodo sumidero de la red.

Node *	insert_node (const Node_Type &node_info)

Node *	insert_node ()

Node *	insert_node (Node *p)

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

Arc *	connect_arc (Arc *arc)

virtual Arc *	insert_arc (Node src_node, Node tgt_node, const Flow_Type &cap)

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)

virtual void	remove_arc (Arc *arc)
	Elimina de la red el arco arc.

void	disconnect_arc (Arc *arc)

virtual void	remove_node (Node *p)
	Elimina un nodo de una red de flujo junto con todos sus arcos.

	Net_Graph (Digraph &digraph)

	Net_Graph (Net_Graph &net)

void	set_cap (Arc *arc, const Flow_Type &cap)
	Coloca valor de capacidad a un arco.

void	set_flow (Arc *arc, const Flow_Type &flow)

const Flow_Type &	get_flow (Arc *arc) const
	retorna el valor de capacidad del arco.

const Flow_Type &	get_cap (Arc *arc) const
	Retorna el valor de flujo de un arco.

void	reset ()

bool	check_network ()

Flow_Type	flow_value ()

void	insert_residual_arc (Arc *arc)

void	make_residual_net ()

void	unmake_residual_net ()

bool	is_there_residual_net () const
	Retorna true si la red residual está creada; false de lo contrario.

Arc *	get_residual_arc (Arc *a)
	Obtiene el arco residual de a.

void	increase_out_flow (Node *p, const Flow_Type &flow)

void	decrease_out_flow (Node *p, const Flow_Type &flow)

void	increase_in_flow (Node *p, const Flow_Type &flow)

void	decrease_in_flow (Node *p, const Flow_Type &flow)

Métodos públicos heredados desde Aleph::Array_Digraph< NodeT, ArcT >
	Array_Digraph (const Array_Digraph &dg)

	Array_Digraph (Array_Digraph &&dg)

Array_Digraph &	operator= (const Array_Digraph< Node, Arc > &g)

Array_Digraph &	operator= (Array_Digraph< Node, Arc > &&g)

Métodos públicos heredados desde Aleph::Array_Graph< NodeT, ArcT >
virtual Node *	insert_node (Node *p)

void	compress ()

Arc *	connect_arc (Arc *arc)

Arc *	disconnect_arc (Arc *arc)

virtual void	remove_arc (Arc *a)

virtual void	remove_node (Node *p)

Node *	get_first_node () const

Arc *	get_first_arc () const

Arc *	get_first_arc (Node *p) const

	Array_Graph (const Array_Graph &g)

	Array_Graph (Array_Graph &&g)

void	swap (Array_Graph &g)

Array_Graph &	operator= (const Array_Graph &g)

Array_Graph &	operator= (Array_Graph &&g)

void	sort_arcs (Compare &)

void	sort_arcs (Compare &&)

	GRAPH_FUNCTIONAL_METHODS (Array_Graph)

Otros miembros heredados
Atributos públicos heredados desde Aleph::Net_Graph< NodeT, ArcT >
Flow_Type	Infinity

bool	with_super_source
	true si a la red se le ha añadido un supra fuente.

bool	with_super_sink
	true si a la red se le ha añadido un supra sumidero.

bool	residual_net

Atributos públicos heredados desde Aleph::Array_Graph< NodeT, ArcT >
	GRAPH_ITERATIVE_METHODS

	GRAPH_SEARCH_METHODS

	GRAPH_INSERTION_METHODS

Descripción detallada

template<class NodeT, class ArcT>
class Aleph::Net_Cap_Graph< NodeT, ArcT >

Red capacitada con límites de capacidad en nodos.

Net_Cap_Graph define una red capacitada en la cual los nodos tienen límite de flujo entrante o saliente.

La clase recibe dos parámetros tipo:

NodeT: el tipo de nodo de la red, el cual debe ser descendiente de la clase Net_Node.
ArcT: el tipo de arco de la red, el cual debe ser descendiente de la clase Net_Arc.

Una red definida mediante Net_Cap_Graph no es usable por los algoritmos de maximización de flujo. En su lugar, puede obtenerse una red de tipo Net_Graph equivalente. La red equivalente es de tipo Net_Cap_Graph::Aux_Net, el cual fundamentalmente es Net_Graph sin capacidades en los nodos.

La red equivalente puede calcularse mediante compute_aux_net().

Ver también: Net_Graph compute_aux_net()

Documentación de los 'Typedef' miembros de la clase

template<class NodeT , class ArcT >

typedef Net_Graph<Net_Node<Empty_Class, Flow_Type>, Net_Arc<bool, Flow_Type> > Aleph::Net_Cap_Graph< NodeT, ArcT >::Aux_Net

El tipo de red tradicional equivalente a la red con capacidades en los nodos.

Net_Graph::Aux_Net representa el tipo de red capacitada equivalente a la red con capacidades en los nodos (Net_Cap_Graph).

Para obtener la red equivalente se invoca a compute_aux_net(). La red resultado está mapeada tanto en arcos como nodos.

Un nodo en Net_Cap_Graph es mapeado a un arco con valor de capacidad del nodo. Dado un nodo p en Net_Cap_Graph, el arco en Aux_Net se obtiene a través de NODE_COOKIE(p).

Un arco en Net_Cap_Graph es mapeado a un arco con el mismo valor de capacidad. Un arco en Aux_Net tiene un solo atributo lógico. Si el valor en true, entonces el arco mapea a un nodo, cuyo valor de capacidad es el mismo que la capacidad del nodo. De lo contrario, el arco mapea a otro arco.

Documentación de las funciones miembro

template<class NodeT , class ArcT >

Aux_Net* Aleph::Net_Cap_Graph< NodeT, ArcT >::compute_aux_net ( )

inline

Calcula la red tradicional equivalente a la con capacidades en los nodos.

Dada una red con capacidades en los nodos (representada en this), compute_aux_net() calcula la red tradicional equivalente sobre la cual se pueden realizar cálculos de maximización de flujo, corte equivalente, etc.

Devuelve: un puntero a la red equivalente.

Excepciones

bad_alloc	si no hay suficiente memoria para crear la red equivalente.
domain_error	si la red equivalente ya ha sido calculada.

Hace referencia a ARC_COOKIE, Aleph::Net_Cap_Graph< NodeT, ArcT >::free_aux_net(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), Aleph::Filter_Iterator< Container, It, Show_Item >::next() y NODE_COOKIE.

Gráfico de llamadas para esta función:

template<class NodeT , class ArcT >

void Aleph::Net_Cap_Graph< NodeT, ArcT >::free_aux_net ( )

inline

Libera la memoria de la red equivalente. Dispara excepción domain_error si la red equivalente no ha sido creada.

Hace referencia a Aleph::clear_graph().

Referenciado por Aleph::Net_Cap_Graph< NodeT, ArcT >::compute_aux_net().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

template<class NodeT , class ArcT >

Aux_Net* Aleph::Net_Cap_Graph< NodeT, ArcT >::get_aux_net ( )

inline

Retorna un apuntador a la red equivalente a this. Previamente debe haberse creado mediante

template<class NodeT , class ArcT >

Node* Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node	(	const Node_Type &	node_info,
		const Flow_Type &	cap = `numeric_limits<Flow_Type>::max()`
	)

inline

Crea un nuevo nodo capacitado y lo inserta en la red.

Parámetros

[in]	node_info	la información a guardar en el nodo según como ésta se haya definido al momento de especificación del nodo.
[in]	cap	valor de flujo máximo que puede recibir o dejar el nodo. Por omisión este valor está fijado al valor máximo.

Devuelve: un puntero al nodo creado e insertado en la red.

Excepciones

bad_alloc si no hay suficiente memoria.

Hace referencia a Aleph::Net_Graph< NodeT, ArcT >::insert_node().

Gráfico de llamadas para esta función:

template<class NodeT , class ArcT >

void Aleph::Net_Cap_Graph< NodeT, ArcT >::update ( )

inline

Actualiza los valores de flujo de la red equivalente a this.

update() recorre la red capacitad equivalente, previamente calculada mediante compute_aux_net(), y actualiza los valores de flujo sobre la red this.

update() debe ser invocado antes de liberar la red equivalente, a efectos de reflejar sobre this los cálculos realizados sobre la red equivalente. Por ejemplo, si se desea maximizar el flujo de this, entonces se maximiza el flujo de la red equivalente y luego los valores se actualizan sobre this mediante update().

Excepciones

domain_error si la red equivalente no ha sido generada.

Hace referencia a ARC_COOKIE.

La documentación para esta clase fue generada a partir del siguiente fichero:

tpl_netcapgraph.H

Tipos públicos

Métodos públicos

Otros miembros heredados

Descripción detallada

template<class NodeT, class ArcT> class Aleph::Net_Cap_Graph< NodeT, ArcT >

Documentación de los 'Typedef' miembros de la clase

Documentación de las funciones miembro

template<class NodeT, class ArcT>
class Aleph::Net_Cap_Graph< NodeT, ArcT >