Diagrama de colaboración para Redes de Flujo.:

Clases
class	Aleph::Simplex< T >

class	Aleph::Net_Cost_Arc< Arc_Info, F_Type >

class	Aleph::Net_Max_Flow_Min_Cost< NodeT, ArcT >

class	Aleph::Max_Flow_Min_Cost< Net >

class	Aleph::Net_Sup_Dem_Node< Node_Info, F_Type >

class	Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >

class	Aleph::Net_Cap_Node< Node_Info, F_Type >

class	Aleph::Net_Cap_Graph< NodeT, ArcT >

class	Aleph::Net_Arc< Arc_Info, F_Type >

class	Aleph::Net_Node< Node_Info, F_Type >

class	Aleph::Net_Graph< NodeT, ArcT >

class	Aleph::Res_F< N >

class	Aleph::Ford_Fulkerson_Maximum_Flow< Net >

class	Aleph::Edmonds_Karp_Maximum_Flow< Net >

class	Aleph::Res_Arc< N >

class	Aleph::Fifo_Preflow_Maximum_Flow< Net >

class	Aleph::Heap_Preflow_Maximum_Flow< Net >

class	Aleph::Random_Preflow_Maximum_Flow< Net >

class	Aleph::Depth_First_Preflow_Maximum_Flow< Net >

class	Aleph::Breadth_First_Preflow_Maximum_Flow< Net >

class	Aleph::Priority_First_Preflow_Maximum_Flow< Net >

class	Aleph::Random_First_Preflow_Maximum_Flow< Net >

class	Aleph::No_Res_Arc< N >

class	Aleph::Min_Cut< Net, Maxflow >

class	Aleph::Flow_Filter< N >

class	Aleph::Find_Aumenting_Path< Net, Find_Path >

class	Aleph::Find_Decrementing_Path< Net, Find_Path >

Funciones
template<class Net , template< class > class Max_Flow_Algo>
void	Aleph::max_flow_min_cost_by_cycle_canceling (Net &net, bool leave_residual=false)

template<class Net >
void	Aleph::max_flow_min_cost_by_cycle_canceling (Net &net)

template<class Net >
Net::Flow_Type	Aleph::increase_flow (Net &net, Path< Net > &path)

template<class Net >
bool	Aleph::has_aumenting_path (Net &net)

template<class Net , template< class, class > class Find_Path>
Net::Flow_Type	Aleph::aumenting_path_maximum_flow (Net &net, const bool &leave_residual=false)

template<class Net >
Net::Flow_Type	Aleph::ford_fulkerson_maximum_flow (Net &net, const bool &leave_residual=false)

template<class Net >
Net::Flow_Type	Aleph::edmonds_karp_maximum_flow (Net &net, const bool &leave_residual=false)

template<class Net , class Q_Type >
Net::Flow_Type	Aleph::generic_preflow_vertex_push_maximum_flow (Net &net, const bool &leave_residual=false)

template<class Net >
Net::Flow_Type	Aleph::fifo_preflow_maximum_flow (Net &net, const bool &leave_residual=false)

template<class Net >
Net::Flow_Type	Aleph::heap_preflow_maximum_flow (Net &net, const bool &leave_residual=false)

template<class Net >
Net::Flow_Type	Aleph::random_preflow_maximum_flow (Net &net, const bool &leave_residual=false)

template<class Net , class QN_Type , class QA_Type >
Net::Flow_Type	Aleph::generic_preflow_edge_maximum_flow (Net &net, const bool &leave_residual=false)

template<class Net >
Net::Flow_Type	Aleph::depth_first_preflow_edge_maximum_flow (Net &net, const bool &leave_residual=false)

template<class Net >
Net::Flow_Type	Aleph::breadth_first_preflow_edge_maximum_flow (Net &net, const bool leave_residual=false)

template<class Net >
Net::Flow_Type	Aleph::priority_first_preflow_edge_maximum_flow (Net &net, const bool &leave_residual=false)

template<class Net >
Net::Flow_Type	Aleph::random_first_preflow_edge_maximum_flow (Net &net, const bool &leave_residual=false)

Net::Flow_Type	Aleph::Random_First_Preflow_Maximum_Flow< Net >::operator() (Net &net, const bool &leave_residual=false) const

template<class Net , template< class > class Maxflow>
Net::Flow_Type	Aleph::min_cut (Net &net, Aleph::set< typename Net::Node * > &vs, Aleph::set< typename Net::Node * > &vt, DynDlist< typename Net::Arc * > &cuts, DynDlist< typename Net::Arc * > &cutt, const bool leave_residual=false)

template<class Net , template< class, class > class Find_Path>
bool	Aleph::find_aumenting_path (Net &net, Path< Net > &path, const typename Net::Flow_Type &min_slack)

template<class Net , template< class, class > class Find_Path>
bool	Aleph::find_decrementing_path (Net &net, Path< Net > &path, const typename Net::Flow_Type &min_slack)

template<class Net >
void	Aleph::increase_flow (Net &net, Path< Net > &path, const typename Net::Flow_Type &val)

template<class Net >
void	Aleph::decrease_flow (Net &net, Path< Net > &path, const typename Net::Flow_Type &val)

Descripción detallada

Redes de flujo

Una red de flujo es un digrafo dirigido que abstrae una red de tuberías por donde circula un fluido. Los arcos representan tuberías; los nodos las junturas. Cada arco asocia dos valores numéricos: asociados a cada arco:

Capacidad: Máximo valor de flujo que puede circular por el arco.
Valor de flujo: Valor actual del flujo que circula por el arco.

A una red de flujo también se le conoce como red capacitada. En una red capacitada se identifican nodos especiales denominados "fuentes" y "sumideros", respectivamente. Un nodo fuente es uno que no tiene arcos de entrada; consecuentemente, sólo emana flujo. Análogamente, un nodo sumidero es uno que no tiene arcos de salida; en el mismo sentido, sólo recibe flujo.

Puesto que las abstracciones provienen de la teoría física, para cada nodo que no sea fuente o sumidero siempre se debe cumplir que la cantidad total de flujo de entrada debe ser la misma que la de salida.

Las redes capacitadas son un excelente vehículo de resolución de problemas sobre grafos. Aparte del problema del flujo máximo, representable en muchas situaciones de la vida real, una red capacitada sirve para resolver otros problemas de optimización combinatoria: caminos mínimos, emparejamientos, cortes, etc.

Documentación de las funciones

template<class Net , template< class, class > class Find_Path>

Net::Flow_Type Aleph::aumenting_path_maximum_flow	(	Net &	net,
		const bool &	leave_residual = `false`
	)

Maximiza el flujo de la red según búsquedas de caminos de aumento.

aumenting_path_maximum_flow() recibe una red capacitada y maximiza su valor de flujo mediante búsquedas sucesivas de caminos de aumento.

El método recibe dos parámetros tipo:

Net: el tipo de red cuyo flujo se desea maximizar y que debe estar derivado de Net_Graph.
Find_Path: la clase de búsqueda de camino.

La red puede tener múltiples fuentes y sumideros.

Durante el cálculo se construye una red residual parcial, cuyo consumo en espacio es proporcional a la cantidad de arcos.

Parámetros

[in,out]	net	la red capacitada cuyo flujo se desea maximizar.
[in]	leave_residual	indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor de flujo maximizado de la red

Excepciones

bad_alloc	si no hay suficiente memoria para la red residual y para los caminos de aumento internos. En este caso, el estado de la red se corresponde con el último incremento de flujo realizado antes de que ocurra excepción.
domain_error	si la red residual ya ha sido calculada.

template<class Net >

Net::Flow_Type Aleph::breadth_first_preflow_edge_maximum_flow	(	Net &	net,
		const bool	leave_residual = `false`
	)

Flujo máximo de red por empuje de preflujo en amplitud.

breadth_first_preflow_edge_maximum_flow() calcula el flujo máximo de la red net según la técnica de empuje de preflujo. El preflujo es llevado en amplitud hacia el sumidero, lo que puede ser conveniente para grafos de alta excentricidad.

Parámetros

[in,out]	net	la red capacitada cuyo flujo se desea maximizar.
[in]	leave_residual	indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor de flujo maximizado de la red

Excepciones

bad_alloc	si no hay suficiente memoria.
domain_error	si la red residual ya ha sido calculada.

Referenciado por Aleph::Breadth_First_Preflow_Maximum_Flow< Net >::operator()().

Gráfico de llamadas a esta función:

template<class Net >

void Aleph::decrease_flow	(	Net &	net,
		Path< Net > &	path,
		const typename Net::Flow_Type &	val
	)

Decrementa el flujo de una red según un camino de decremento.

decrease_flow(net, path, val) toma el camino de decremento contenido en path y decrementa el valor de flujo la red net en el valor val.

La biblioteca permite calcular caminos de decremento sobre la red residual de dos maneras:

find_path_depth_first<Net, Res_F<Net> >(net, sink, source, path)
find_path_breadth_first<Net, Res_F<Net> >(net, sink, source, path)

Para que tenga sentido cualquiera de estas maneras de encontrar caminos de decremento, la red residual sobre net debe estar instanciada. Para ello, debe haberse llamado previamente a make_residual_net().

Parámetros

[in]	net	la red en la cual se quiere decrementar el flujo por el camino path
[in]	path	el camino de tipo Path donde se quiere almacenar el camino de decremento.
[in]	val	el valor en el cual se desea decrementar el flujo.

Ver también: Path find_path_depth_first() find_path_breadth_first() make_residual_net()

Excepciones

domain_error	si la red residual no ha sido creada o si por el camino de decremento existe algún arco cuyo flujo sea menor que val.
invalid_argument	si el valor de incremento val es menor que el eslabón mínimo del camino de decremento.

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

Gráfico de llamadas para esta función:

template<class Net >

Net::Flow_Type Aleph::depth_first_preflow_edge_maximum_flow	(	Net &	net,
		const bool &	leave_residual = `false`
	)

Flujo máximo de red por empuje de preflujo en profundidad.

depth_first_preflow_edge_maximum_flow() calcula el flujo máximo de la red net según la técnica de empuje de preflujo. El preflujo es llevado en profundidad hacia el sumidero, lo que es conveniente para grafos de baja excentricidad.

Parámetros

[in,out]	net	la red capacitada cuyo flujo se desea maximizar.
[in]	leave_residual	indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor de flujo maximizado de la red

Referenciado por Aleph::Depth_First_Preflow_Maximum_Flow< Net >::operator()().

Gráfico de llamadas a esta función:

template<class Net >

Net::Flow_Type Aleph::edmonds_karp_maximum_flow	(	Net &	net,
		const bool &	leave_residual = `false`
	)

Maximiza el flujo de la red según el algoritmo de Edmonds-Karp.

edmonds_karp_maximum_flow() recibe una red capacitada y maximiza su valor de flujo mediante el algoritmo de Edmonds-Karp.

La red puede tener múltiples fuentes y sumideros.

Durante el cálculo se construye una red residual parcial, cuyo consumo en espacio es proporcional a la cantidad de arcos.

Parámetros

[in,out]	net	la red capacitada cuyo flujo se desea maximizar.
[in]	leave_residual	indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor de flujo maximizado de la red

Excepciones

bad_alloc	si no hay suficiente memoria para la red residual y para los caminos de aumento internos. En este caso, el estado de la red se corresponde con el último incremento de flujo realizado antes de que ocurra excepción.
domain_error	si la red residual ya ha sido calculada.

Referenciado por Aleph::Edmonds_Karp_Maximum_Flow< Net >::operator()().

Gráfico de llamadas a esta función:

template<class Net >

Net::Flow_Type Aleph::fifo_preflow_maximum_flow	(	Net &	net,
		const bool &	leave_residual = `false`
	)

Flujo máximo de empuje de preflujo con cola FIFO de nodos.

fifo_preflow_vertex_push_maximum_flow(net) calcula el flujo máximo de la red net según el algoritmo genérico de Goldberg y Tarjan en donde los nodos activos, aquellos cuyo flujo de entrada es mayor que el de salida son almacenados y procesados según una cola FIFO. Este algoritmo procesa empuja el preflujo por los arcos según una heurística en profundidad.

Durante la ejecución del algoritmo se emplean los contadores y cookies de todos los nodos de la red. El bit Maximum_Flow es usado para los arcos.

Parámetros

[in,out]	net	una red capacitada a maximizar su flujo. net puede tener varios fuentes y sumideros.
[in]	leave_residual	indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor de flujo maximizado de la red

Excepciones

bad_alloc si no hay suficiente memoria.

Hace referencia a Aleph::generic_preflow_vertex_push_maximum_flow().

Referenciado por Aleph::Fifo_Preflow_Maximum_Flow< Net >::operator()().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

template<class Net , template< class, class > class Find_Path>

bool Aleph::find_aumenting_path	(	Net &	net,
		Path< Net > &	path,
		const typename Net::Flow_Type &	min_slack
	)

Busca un camino de aumento por el cual se pueda incrementar el flujo en el valor dado min_slack.

Se manejan los siguientes parámetros tipo:

Net: el tipo de red capacitada.
Find_Path: la clase de búsqueda (profundidad o amplitud) por la cual se desea encontrar el camino.

Parámetros

[in]	net	la red sobre la cual se desea buscar el camino de aumento.
[out]	path	el camino de aumento (si existe) con capacidad restante suficiente para aumentar el flujo en min_slack
[in]	min_slack	el valor mínimo en el cual se desea aumentar el flujo.

Devuelve: true si existe un camino de aumento con capacidad restante suficiente para aumentar el flujo en min_slack

template<class Net , template< class, class > class Find_Path>

bool Aleph::find_decrementing_path	(	Net &	net,
		Path< Net > &	path,
		const typename Net::Flow_Type &	min_slack
	)

Busca un camino de aumento por el cual se pueda decrementar el flujo en el valor dado min_slack.

Se manejan los siguientes parámetros tipo:

Net: el tipo de red capacitada.
Find_Path: la clase de búsqueda (profundidad o amplitud) por la cual se desea encontrar el camino.

Parámetros

[in]	net	la red sobre la cual se desea buscar el camino de decremento.
[out]	path	el camino de aumento (si existe) con flujo suficiente para decrementar el flujo en min_slack
[in]	min_slack	el valor mínimo en el cual se desea decrementar flujo.

Devuelve: true si existe un camino de aumento con flujo suficiente para decrementar el flujo en min_slack.

template<class Net >

Net::Flow_Type Aleph::ford_fulkerson_maximum_flow	(	Net &	net,
		const bool &	leave_residual = `false`
	)

Maximiza el flujo de la red según el algoritmo de Ford-Fulkerson.

ford_fulkerson_maximum_flow() recibe una red capacitada y maximiza su valor de flujo mediante el algoritmo de Ford-Fulkerson.

La red puede tener múltiples fuentes y sumideros.

Durante el cálculo se construye una red residual parcial, cuyo consumo en espacio es proporcional a la cantidad de arcos.

Parámetros

[in,out]	net	la red capacitada cuyo flujo se desea maximizar.
[in]	leave_residual	indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor de flujo maximizado de la red

Excepciones

bad_alloc	si no hay suficiente memoria para la red residual y para los caminos de aumento internos. En este caso, el estado de la red se corresponde con el último incremento de flujo realizado antes de que ocurra excepción.
domain_error	si la red residual ya ha sido calculada.

Referenciado por Aleph::Ford_Fulkerson_Maximum_Flow< Net >::operator()().

Gráfico de llamadas a esta función:

template<class Net , class QN_Type , class QA_Type >

Net::Flow_Type Aleph::generic_preflow_edge_maximum_flow	(	Net &	net,
		const bool &	leave_residual = `false`
	)

Flujo máximo según algoritmo genérico de empuje de preflujo orientado hacia arcos.

generic_preflow_edge_maximum_flow(net) calcula el flujo máximo de la red net según el algoritmo genérico de Goldberg y Tarjan. La función emplea tres parámetros tipo:

Net: una clase de red capacitada derivada del tipo Net_Graph.
QN_Type: una clase conjunto de "nodos activos". Q_Type debe manejar punteros de tipo typename Net::Node y debe soportar las siguientes operaciones:
1. get(): extracción de un nodo.
2. put(p): inserción del nodo p en el conjunto.
3. remove(p): eliminación del nodos específico p.
QA_Type: una clase conjunto de "arcos elegibles". QA_Type debe manejar punteros de tipo typename Net::Arc con las siguientes operaciones:
1. get(): extracción de un arco.
2. put(p): inserción del arco p en el conjunto.

Durante la ejecución del algoritmo se emplean los contadores y cookies de todos los nodos de la red. El bit Maximum_Flow es usado para los arcos.

Parámetros

[in,out]	net	una red capacitada a maximizar su flujo. net puede tener varios fuentes y sumideros.
[in]	leave_residual	indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor de flujo maximizado de la red

Excepciones

bad_alloc	si no hay suficiente memoria.
domain_error	si la red residual ya está calculada.

Ver también: fifo_preflow_maximum_flow() heap_preflow_maximum_flow() random_preflow_maximum_flow()

Hace referencia a Aleph::Filter_Iterator< Container, It, Show_Item >::next().

Gráfico de llamadas para esta función:

template<class Net , class Q_Type >

Net::Flow_Type Aleph::generic_preflow_vertex_push_maximum_flow	(	Net &	net,
		const bool &	leave_residual = `false`
	)

Flujo máximo según algoritmo genérico de empuje de preflujo orientado hacia nodos.

generic_preflow_vertex_push_maximum_flow(net) calcula el flujo máximo de la red net según el algoritmo genérico de Goldberg y Tarjan. La función emplea dos parámetros tipo:

Net: una clase de red capacitada derivada del tipo Net_Graph.
Q_Type: una clase conjunto de "nodos activos". Q_Type debe manejar punteros de tipo typename Net::Node y debe soportar las siguientes operaciones:
1. get(): extracción de un nodo.
2. put(p): inserción del nodo p en el conjunto.

Durante la ejecución del algoritmo se emplean los contadores y cookies de todos los nodos de la red. El bit Maximum_Flow es usado para los arcos.

Parámetros

[in,out]	net	una red capacitada a maximizar su flujo. net puede tener varios fuentes y sumideros.
[in]	leave_residual	indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor de flujo maximizado de la red

Excepciones

bad_alloc	si no hay suficiente memoria.
domain_error	si la red residual ya está calculada.

Ver también: fifo_preflow_maximum_flow() heap_preflow_maximum_flow() random_preflow_maximum_flow()

Referenciado por Aleph::fifo_preflow_maximum_flow(), Aleph::heap_preflow_maximum_flow() y Aleph::random_preflow_maximum_flow().

Gráfico de llamadas a esta función:

template<class Net >

bool Aleph::has_aumenting_path ( Net & net )

Determina si existe o no un camino de aumento.

has_aumenting_path() retorna true si la red this contiene al menos un camino de aumento.

Un camino de aumento es un camino por donde se puede incrementar el valor de flujo de una red capacitada sin alterar sus condiciones de red.

Normalmente la rutina se emplea para determinar si el valor de flujo de la red es o no máximo. En cuyo caso has_aumenting_path() no debe encontrar ningún camino.

El camino de aumento es buscado en profundidad.

La rutina requiere que la red residual haya sido calculada.

Parámetros

[in] net la red de flujo.

Devuelve: true si la red contiene un camino de aumento; false de lo contrario.

Excepciones

domain_error si la red residual no ha sido calculada.

template<class Net >

Net::Flow_Type Aleph::heap_preflow_maximum_flow	(	Net &	net,
		const bool &	leave_residual = `false`
	)

Flujo máximo de empuje de preflujo con cola de prioridad según la altura de los nodos.

heap_preflow_vertex_push_maximum_flow(net) calcula el flujo máximo de la red net en donde los nodos activos, aquellos cuyo flujo de entrada es mayor que el de salida son almacenados en una cola de prioridad. El preflujo se empuja desde el fuente hasta el sumidero según una heurística en amplitud.

heap_preflow_vertex_push_maximum_flow() es uno de los mejores algoritmos generales de cálculo de flujo máximo. Su desempeño para el peor caso es de $O(V^3)$ .

Durante la ejecución del algoritmo se emplean los contadores y cookies de todos los nodos de la red. El bit Maximum_Flow es usado para los arcos.

Parámetros

[in,out]	net	una red capacitada a maximizar su flujo. net puede tener varios fuentes y sumideros.
[in]	leave_residual	indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor de flujo maximizado de la red

Excepciones

bad_alloc si no hay suficiente memoria.

Hace referencia a Aleph::generic_preflow_vertex_push_maximum_flow().

Referenciado por Aleph::Heap_Preflow_Maximum_Flow< Net >::operator()().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

template<class Net >

Net::Flow_Type Aleph::increase_flow	(	Net &	net,
		Path< Net > &	path
	)

Incrementa el flujo de una red según un camino de aumento.

increase_flow(net, path) toma el camino de aumento contenido en path e incrementa el valor de flujo de net en el eslabón mínimo (slack) del camino.

La biblioteca permite calcular caminos de aumento sobre la red residual de dos maneras:

find_path_depth_first<Net, Res_F<Net> >(net, source, sink, path)
find_path_breadth_first<Net, Res_F<Net> >(net, source, sink, path)

Para que tenga sentido cualquiera de estas maneras de encontrar caminos de aumento, la red residual sobre net debe estar instanciada. Pare ello, debe haberse llamado previamente a make_residual_net().

Parámetros

[in]	net	la red capacitada por donde se desea incrementar el flujo por el camino de aumento.
[in]	path	el camino de tipo Path donde se quiere almacenar el camino de aumento.

Devuelve: el valor en que ha sido aumentado el flujo.

Ver también: Path find_path_depth_first() find_path_breadth_first() make_residual_net()

Excepciones

domain_error si la red residual no ha sido creada

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

Gráfico de llamadas para esta función:

template<class Net >

void Aleph::increase_flow	(	Net &	net,
		Path< Net > &	path,
		const typename Net::Flow_Type &	val
	)

Incrementa el flujo de una red según un camino de aumento.

increase_flow(net, path, val) toma el camino de aumento contenido en path e incrementa el valor de flujo la red net en el valor val.

La biblioteca permite calcular caminos de aumento sobre la red residual de dos maneras:

find_path_depth_first<Net, Res_F<Net> >(net, source, sink, path)
find_path_breadth_first<Net, Res_F<Net> >(net, source, sink, path)

Para que tenga sentido cualquiera de estas maneras de encontrar caminos de aumento, la red residual sobre net debe estar instanciada. Pare ello, debe haberse llamado previamente a make_residual_net().

Parámetros

[in]	net	la red por la cual se desea incrementar el flujo dado el camino de aumento path.
[in]	path	el camino de tipo Path donde se quiere almacenar el camino de aumento.
	val	el valor en el cual se desea incrementar el flujo.

Ver también: Path find_path_depth_first() find_path_breadth_first() make_residual_net()

Excepciones

domain_error	si la red residual no ha sido creada o si el eslabón mínimo del camino es menor que val.
invalid_argument	si el valor de incremento val es menor que el eslabón mínimo del camino de aumento.

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

Gráfico de llamadas para esta función:

template<class Net , template< class > class Max_Flow_Algo>

void Aleph::max_flow_min_cost_by_cycle_canceling	(	Net &	net,
		bool	leave_residual = `false`
	)

Calcula el flujo máximo a coste mínimo mediante la técnica de cancelación de ciclos.

Esta primitiva emplea el típico algoritmo de cancelación de ciclos para calcular el flujo máximo a coste mínimo de una red capacitada de flujo.

Primero, la rutina calcula un flujo máximo mediante un algoritmo de maximización de flujo. El algoritmo es un parámetro tipo, llamado Max_Flow_Algo, instanciado sobre una red de tipo genérico Net. Una vez calculado un flujo máximo inicial, el algoritmo busca ciclos negativos sobre la red residual mediante el algoritmo de Bellman-Ford. Por cada ciclo encontrado, se aumenta el flujo para eliminarlo.

El procedimiento anterior se repite hasta que ya no se encuentren más ciclos negativos. Momento en el cual el flujo es máximo y el coste mínimo.

Parámetros

[in]	net	la red a maximizar flujo y minimizar coste.
[in]	leave_residual	indica si la red residual debe o no eliminarse. Por omisión, el valor es false.

Excepciones

bad_alloc si no hay suficiente memoria.

template<class Net >

void Aleph::max_flow_min_cost_by_cycle_canceling ( Net & net )

Calcula el flujo máximo a coste mínimo mediante la técnica de cancelación de ciclos.

Esta primitiva emplea el típico algoritmo de cancelación de ciclos para calcular el flujo máximo a coste mínimo de una red capacitada de flujo.

La rutina crean un ciclo negativo ficticio por añadidura de un arco negativo, con suficiente capacidad, entre el fuente y el sumidero. A partir de este ciclo negativo, el algoritmo busca ciclos negativos sobre la red residual mediante el algoritmo de Bellman-Ford. Por cada ciclo encontrado, se aumenta el flujo para eliminarlo.

El procedimiento anterior se repite hasta que ya no se encuentren más ciclos negativos. Momento en el cual el flujo es máximo y el coste mínimo.

Parámetros

[in] net la red a maximizar flujo y minimizar coste.

Excepciones

bad_alloc si no hay suficiente memoria.

Referenciado por Aleph::Max_Flow_Min_Cost< Net >::by_cycle_canceling_and_dummy_arc().

Gráfico de llamadas a esta función:

template<class Net , template< class > class Maxflow>

Net::Flow_Type Aleph::min_cut	(	Net &	net,
		Aleph::set< typename Net::Node * > &	vs,
		Aleph::set< typename Net::Node * > &	vt,
		DynDlist< typename Net::Arc * > &	cuts,
		DynDlist< typename Net::Arc * > &	cutt,
		const bool	leave_residual = `false`
	)

Calcula el flujo máximo de una red capacitada y determina el corte mínimo.

min_cut() recibe una red capacitada cuyo flujo es maximizado y luego, a partir del flujo máximo, se calcula el corte mínimo. La rutina recibe dos parámetros tipo:

Net: la clase de red, la cual debe ser derivada de la clase Net_Graph.
Maxflow: la clase del algoritmo de cálculo de flujo máximo que se desea emplear.

Parámetros

[in,out]	net	la red a maximizar el flujo y de la cual se desea calcular un corte mínimo
[out]	vs	el conjunto de nodos .
[out]	vt	el conjunto de nodos .
[out]	cuts	el conjunto de arcos que van de hacia . Este es el corte.
[out]	cutt	el conjunto de arcos que van de hacia .
	leave_residual	leave_residual indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor del flujo maximizado (que es igual a la capacidad del corte mínimo)

Ver también: Edmonds_Karp_Maximum_Flow Random_First_Preflow_Maximum_Flow Priority_First_Preflow_Maximum_Flow Breadth_First_Preflow_Maximum_Flow Depth_First_Preflow_Maximum_Flow Random_Preflow_Maximum_Flow Heap_Preflow_Maximum_Flow Fifo_Preflow_Maximum_Flow Ford_Fulkerson_Maximum_Flow

Hace referencia a Aleph::set< T, Compare, Tree >::count(), Aleph::DynDlist< T >::insert(), Aleph::set< T, Compare, Tree >::insert(), IS_NODE_VISITED y Aleph::set< T, Compare, Tree >::size().

Gráfico de llamadas para esta función:

template<class Net >

Net::Flow_Type Aleph::Random_First_Preflow_Maximum_Flow< Net >::operator()	(	Net &	net,
		const bool &	leave_residual = `false`
	)		const

inline

Flujo máximo de red por empuje de preflujo aleatorio.

random_first_preflow_edge_maximum_flow() calcula el flujo máximo de la red net según la técnica de empuje de preflujo. El preflujo es llevado aleatoriamente hacia el sumidero.

Parámetros

[in,out]	net	la red capacitada cuyo flujo se desea maximizar.
[in]	leave_residual	indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor de flujo maximizado de la red

Excepciones

bad_alloc	si no hay suficiente memoria.
domain_error	si la red residual ya ha sido calculada.

Hace referencia a Aleph::random_first_preflow_edge_maximum_flow().

Gráfico de llamadas para esta función:

template<class Net >

Net::Flow_Type Aleph::priority_first_preflow_edge_maximum_flow	(	Net &	net,
		const bool &	leave_residual = `false`
	)

Flujo máximo de red por empuje de preflujo en prioridad.

priority_first_preflow_edge_maximum_flow() calcula el flujo máximo de la red net según la técnica de empuje de preflujo. El preflujo es llevado hacia el sumidero por los arcos que emanen desde los nodos más distantes del sumidero hacia los más cercanos. Cuando ocurra un empate, se escoge el arco con mayor capacidad bajo la expectativa de que por éste se empuje mayor preflujo.

En general, este es uno de los mejores algoritmos de cálculo de flujo máximo.

Parámetros

[in,out]	net	la red capacitada cuyo flujo se desea maximizar.
[in]	leave_residual	indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor de flujo maximizado de la red

Excepciones

bad_alloc	si no hay suficiente memoria.
domain_error	si la red residual ya ha sido calculada.

Referenciado por Aleph::Priority_First_Preflow_Maximum_Flow< Net >::operator()().

Gráfico de llamadas a esta función:

template<class Net >

Net::Flow_Type Aleph::random_first_preflow_edge_maximum_flow	(	Net &	net,
		const bool &	leave_residual = `false`
	)

Flujo máximo de red por empuje de preflujo aleatorio.

random_first_preflow_edge_maximum_flow() calcula el flujo máximo de la red net según la técnica de empuje de preflujo. El preflujo es llevado aleatoriamente hacia el sumidero.

Parámetros

[in,out]	net	la red capacitada cuyo flujo se desea maximizar.
[in]	leave_residual	indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor de flujo maximizado de la red

Excepciones

bad_alloc	si no hay suficiente memoria.
domain_error	si la red residual ya ha sido calculada.

Referenciado por Aleph::Random_First_Preflow_Maximum_Flow< Net >::operator()().

Gráfico de llamadas a esta función:

template<class Net >

Net::Flow_Type Aleph::random_preflow_maximum_flow	(	Net &	net,
		const bool &	leave_residual = `false`
	)

Flujo máximo de empuje de preflujo con cola aleatoria de nodos activos.

random_preflow_vertex_push_maximum_flow(net) calcula el flujo máximo de la red net en donde los nodos activos, aquellos cuyo flujo de entrada es mayor que el de salida son almacenados en una cola aleatoria.

Durante la ejecución del algoritmo se emplean los contadores y cookies de todos los nodos de la red. El bit Maximum_Flow es usado para los arcos.

Parámetros

[in,out]	net	una red capacitada a maximizar su flujo. net puede tener varios fuentes y sumideros.
[in]	leave_residual	indica si la red residual requerida para los cálculos parciales debe dejarse instanciada o no. Por omisión, la red residual, así como el supra grafo en caso de que la red tenga varios fuentes o sumideros, son liberados al final del cálculo. Si el parámetro es true, entonces la red residual queda instanciada y eventualmente utilizable por otros algoritmos.

Devuelve: el valor de flujo maximizado de la red

Excepciones

bad_alloc si no hay suficiente memoria.

Hace referencia a Aleph::generic_preflow_vertex_push_maximum_flow().

Referenciado por Aleph::Random_Preflow_Maximum_Flow< Net >::operator()().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

Clases

Funciones

Descripción detallada

Documentación de las funciones