Collaboration diagram for Redes de Flujo.:

Classes
class	Aleph::Simplex< T >

struct	Aleph::Net_Arc< Arc_Info, F_Type >

struct	Aleph::Net_Filt< Net >

struct	Aleph::Net_Graph< NodeT, ArcT >

class	Aleph::Find_Aumenting_Path< Net, Q >

struct	Aleph::Ford_Fulkerson_Maximum_Flow< Net >

struct	Aleph::Edmonds_Karp_Maximum_Flow< Net >

struct	Aleph::Fifo_Preflow_Maximum_Flow< Net >

struct	Aleph::Heap_Preflow_Maximum_Flow< Net >

struct	Aleph::Random_Preflow_Maximum_Flow< Net >

struct	Aleph::Min_Cut< Net, Maxflow >

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 >

struct	Aleph::Net_Cost_Arc< Arc_Info, F_Type >

struct	Aleph::Net_Cost_Graph< NodeT, ArcT >

Typedefs
template<class Net >
using	Aleph::Parc = tuple< typename Net::Arc *, bool >

template<class Net >
using	Aleph::SemiPath = tuple< bool, typename Net::Flow_Type, DynList< Parc< Net > >>

Functions
template<class Net >
Net::Flow_Type	Aleph::remaining_flow (typename Net::Node src, typename Net::Arc a) noexcept

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

template<class Net >
void	Aleph::increase_flow (Net &net, const DynList< Parc< Net >> &semi_path, const typename Net::Flow_Type slack)

template<class Net >
void	Aleph::decrease_flow (Net &net, const DynList< Parc< Net >> &semi_path, typename Net::Flow_Type slack)

template<class Net , template< typename T > class Q>
Path< Net >	Aleph::find_aumenting_path (const Net &net, const typename Net::Flow_Type &min_slack)

template<class Net >
Path< Net >	Aleph::find_aumenting_path_dfs (const Net &net, const typename Net::Flow_Type &min_slack)

template<class Net >
Path< Net >	Aleph::find_aumenting_path_bfs (const Net &net, const typename Net::Flow_Type &min_slack)

template<class Net , template< typename T > class Q>
SemiPath< Net >	Aleph::find_aumenting_semi_path (const Net &net, const typename Net::Flow_Type &slack)

template<class Net >
SemiPath< Net >	Aleph::find_aumenting_semi_path_dfs (const Net &net, const typename Net::Flow_Type &slack)

template<class Net >
SemiPath< Net >	Aleph::find_aumenting_semi_path_bfs (const Net &net, const typename Net::Flow_Type &slack)

template<class Net , template< typename T > class Q>
SemiPath< Net >	Aleph::find_decrementing_path (const Net &net, const typename Net::Flow_Type &slack)

template<class Net >
SemiPath< Net >	Aleph::find_decrementing_path_dfs (const Net &net, const typename Net::Flow_Type &slack)

template<class Net >
SemiPath< Net >	Aleph::find_decrementing_path_bfs (const Net &net, const typename Net::Flow_Type &slack)

template<class Net , template< class > class Find_Path>
Net::Flow_Type	Aleph::aumenting_path_maximum_flow (Net &net)

template<class Net >
Net::Flow_Type	Aleph::ford_fulkerson_maximum_flow (Net &net)

template<class Net >
Net::Flow_Type	Aleph::edmonds_karp_maximum_flow (Net &net)

template<class Net , class Q_Type >
Net::Flow_Type	Aleph::generic_preflow_vertex_push_maximum_flow (Net &net)

template<class Net >
Net::Flow_Type	Aleph::fifo_preflow_maximum_flow (Net &net)

template<class Net >
Net::Flow_Type	Aleph::heap_preflow_maximum_flow (Net &net)

template<class Net >
Net::Flow_Type	Aleph::random_preflow_maximum_flow (Net &net)

template<class Net , template< class > class Maxflow>
Net::Flow_Type	Aleph::min_cut (Net &net, DynSetTree< typename Net::Node > &vs, DynSetTree< typename Net::Node > &vt, DynList< typename Net::Arc > &cuts, DynList< typename Net::Arc > &cutt)

template<class Net , template< class > class Max_Flow_Algo = Ford_Fulkerson_Maximum_Flow>
tuple< size_t, double >	Aleph::max_flow_min_cost_by_cycle_canceling (Net &net, double it_factor=0.4, size_t step=10)

Detailed Description

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.

Typedef Documentation

◆ Parc

template<class Net >

using Aleph::Parc = typedef tuple<typename Net::Arc*, bool>

Define un arco que pertenece a un semicamino

◆ SemiPath

template<class Net >

using Aleph::SemiPath = typedef tuple<bool, typename Net::Flow_Type, DynList<Parc<Net> >>

Define un semicamino compuesto por: -. bool: dise si el camino fue o no encontrado -. Flow_Type: el valor del slack del camino -. Lista de pares arco e indicaciÃ³n de si es normal o reducido. true ==> normal

Function Documentation

◆ aumenting_path_maximum_flow()

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

Net::Flow_Type Aleph::aumenting_path_maximum_flow ( Net & net )

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 tres 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.

Parameters

[in,out]	net	la red capacitada cuyo flujo se desea maximizar.
[in]	sa	el estado del filtro de arcos

Returns: el valor de flujo maximizado de la red

◆ decrease_flow()

template<class Net >

void Aleph::decrease_flow	(	Net &	net,
		const DynList< Parc< Net >> &	semi_path,
		typename Net::Flow_Type	slack
	)

Decrementa el flujo de una red segÃºn un camino de aumento.

decrease_flow(net, semi_path) toma el camino de aumento contenido en path y decrementa el valor de flujo de net en el eslabÃ³n mÃnimo (slack) del camino.

Parameters

[in]	net	la red capacitada por donde se desea incrementar el flujo por el camino de aumento.
[in]	semi_path	semicamino por donde se aumentarÃ¡ el flujo
[in]	slack	valor de aumento dl camino. Debe ser menor o igual al slack mÃnimo del camino.

Warning: No se valida el slack

Here is the call graph for this function:

◆ edmonds_karp_maximum_flow()

template<class Net >

Net::Flow_Type Aleph::edmonds_karp_maximum_flow ( Net & net )

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.

Parameters

[in,out]	net	la red capacitada cuyo flujo se desea maximizar.
[in]	sa	el filtro de arcos

Returns: el valor de flujo maximizado de la red

◆ fifo_preflow_maximum_flow()

template<class Net >

Net::Flow_Type Aleph::fifo_preflow_maximum_flow ( Net & net )

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.

Parameters

[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.

Returns: el valor de flujo maximizado de la red

Exceptions

bad_alloc si no hay suficiente memoria.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_aumenting_path()

template<class Net , template< typename T > class Q>

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

Encuentra un camino de aumento mediante una bÃºsqueda en profundidad o en amplitud segÃºn sea el valor del parÃ¡metro plantilla Q. Q puede ser una pila, en cuyo caso la bÃºsqueda serÃ¡ en profundidad, o una cola, en cuyo caso la bÃºsqueda serÃ¡ en amplitud

Parameters

[in]	net	red capacitada de flujo
[in]	min_slack	valor mÃnimo de decremento del camino
[in]	sa	valor del filtro de arcos

◆ find_aumenting_path_bfs()

template<class Net >

Path<Net> Aleph::find_aumenting_path_bfs	(	const Net &	net,
		const typename Net::Flow_Type &	min_slack
	)

Encuentra un camino de aumento mediante una bÃºsqueda en amplitud.

Parameters

[in]	net	red capacitada de flujo
[in]	min_slack	valor mÃnimo de aumento del camino
[in]	sa	valor del filtro de arcos

◆ find_aumenting_path_dfs()

template<class Net >

Path<Net> Aleph::find_aumenting_path_dfs	(	const Net &	net,
		const typename Net::Flow_Type &	min_slack
	)

Encuentra un camino de aumento mediante una bÃºsqueda en profundidad.

Parameters

[in]	net	red capacitada de flujo
[in]	min_slack	valor mÃnimo de aumento del camino
[in]	sa	valor del filtro de arcos

◆ find_aumenting_semi_path()

template<class Net , template< typename T > class Q>

SemiPath<Net> Aleph::find_aumenting_semi_path	(	const Net &	net,
		const typename Net::Flow_Type &	slack
	)

Encuentra un camino de aumento en forma de semicamino mediante una bÃºsqueda en profundidad o en amplitud segÃºn sea el valor del parÃ¡metro plantilla Q. Q puede ser una pila, en cuyo caso la bÃºsqueda serÃ¡ en profundidad, o una cola, en cuyo caso la bÃºsqueda serÃ¡ en amplitud

Parameters

[in]	net	red capacitada de flujo
[out]	semi_path	lista de pares (Arc,bool) que describe el semicamino
[in]	min_slack	valor mÃnimo de decremento del camino
[in]	sa	valor del filtro de arcos

Returns: en slack del semicamino. Un valor igual al dado en parÃ¡metro indica que el camino fue encontrado satisfactoriamente

◆ find_aumenting_semi_path_bfs()

template<class Net >

SemiPath<Net> Aleph::find_aumenting_semi_path_bfs	(	const Net &	net,
		const typename Net::Flow_Type &	slack
	)

Encuentra un camino de aumento en forma de semicamino mediante una bÃºsqueda en amplitud.

Parameters

[in]	net	red capacitada de flujo
[out]	semi_path	lista de pares (Arc,bool) que describe el semicamino
[in]	min_slack	valor mÃnimo de decremento del camino
[in]	sa	valor del filtro de arcos

Returns: en slack del semicamino. Un valor igual al dado en parÃ¡metro indica que el camino fue encontrado satisfactoriamente

◆ find_aumenting_semi_path_dfs()

template<class Net >

SemiPath<Net> Aleph::find_aumenting_semi_path_dfs	(	const Net &	net,
		const typename Net::Flow_Type &	slack
	)

Encuentra un camino de aumento en forma de semicamino mediante una bÃºsqueda en profundidad.

Parameters

[in]	net	red capacitada de flujo
[out]	semi_path	lista de pares (Arc,bool) que describe el semicamino
[in]	min_slack	valor mÃnimo de decremento del camino
[in]	sa	valor del filtro de arcos

Returns: en slack del semicamino. Un valor igual al dado en parÃ¡metro indica que el camino fue encontrado satisfactoriamente

◆ find_decrementing_path()

template<class Net , template< typename T > class Q>

SemiPath<Net> Aleph::find_decrementing_path	(	const Net &	net,
		const typename Net::Flow_Type &	slack
	)

Encuentra un camino de decremento mediante una bÃºsqueda en profundidad o en amplitud segÃºn sea el valor del parÃ¡metro plantilla Q. Q puede ser una pila, en cuyo caso la bÃºsqueda serÃ¡ en profundidad, o una cola, en cuyo caso la bÃºsqueda serÃ¡ en amplitud

Parameters

[in]	net	red capacitada de flujo
[in]	min_slack	valor mÃnimo de decremento del camino
[out]	semi_path	lista de pares arco,forward que caracteriza el semi-camino
[in]	sa	valor del filtro de arcos

Returns: el valor del slack. Si es igual al solicitado, entonces el semi-camino fue encontrado

◆ find_decrementing_path_bfs()

template<class Net >

SemiPath<Net> Aleph::find_decrementing_path_bfs	(	const Net &	net,
		const typename Net::Flow_Type &	slack
	)

Encuentra un camino de aumento mediante una bÃºsqueda en amplitud.

Parameters

[in]	net	red capacitada de flujo
[in]	min_slack	valor mÃnimo de aumento del camino
[in]	sa	valor del filtro de arcos

Here is the call graph for this function:

◆ find_decrementing_path_dfs()

template<class Net >

SemiPath<Net> Aleph::find_decrementing_path_dfs	(	const Net &	net,
		const typename Net::Flow_Type &	slack
	)

Encuentra un camino de aumento mediante una bÃºsqueda en amplitud.

Parameters

[in]	net	red capacitada de flujo
[in]	min_slack	valor mÃnimo de aumento del camino
[in]	sa	valor del filtro de arcos

◆ ford_fulkerson_maximum_flow()

template<class Net >

Net::Flow_Type Aleph::ford_fulkerson_maximum_flow ( Net & net )

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.

Parameters

[in,out]	net	la red capacitada cuyo flujo se desea maximizar.
[in]	sa	el filtro de arcos

Returns: el valor de flujo maximizado de la red

Exceptions

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.

Here is the caller graph for this function:

◆ generic_preflow_vertex_push_maximum_flow()

template<class Net , class Q_Type >

Net::Flow_Type Aleph::generic_preflow_vertex_push_maximum_flow ( Net & net )

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.

Parameters

[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.

Returns: el valor de flujo maximizado de la red

Exceptions

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

See also: fifo_preflow_maximum_flow() heap_preflow_maximum_flow() random_preflow_maximum_flow()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ heap_preflow_maximum_flow()

template<class Net >

Net::Flow_Type Aleph::heap_preflow_maximum_flow ( Net & net )

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.

Parameters

[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.

Returns: el valor de flujo maximizado de la red

Exceptions

bad_alloc si no hay suficiente memoria.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ increase_flow() [1/2]

template<class Net >

Net::Flow_Type Aleph::increase_flow	(	Net &	net,
		const 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().

Parameters

[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.

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

See also: Path find_path_depth_first() find_path_breadth_first() make_residual_net()

Exceptions

domain_error si la red residual no ha sido creada

Here is the call graph for this function:

◆ increase_flow() [2/2]

template<class Net >

void Aleph::increase_flow	(	Net &	net,
		const DynList< Parc< Net >> &	semi_path,
		const typename Net::Flow_Type	slack
	)

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

increase_flow(net, semi_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.

Parameters

[in]	net	la red capacitada por donde se desea incrementar el flujo por el camino de aumento.
[in]	semi_path	semicamino por donde se aumentarÃ¡ el flujo
[in]	slack	valor de aumento dl camino. Debe ser menor o igual al slack mÃnimo del camino.

Warning: No se valida el slack

Here is the caller graph for this function:

◆ max_flow_min_cost_by_cycle_canceling()

template<class Net , template< class > class Max_Flow_Algo = Ford_Fulkerson_Maximum_Flow>

tuple<size_t, double> Aleph::max_flow_min_cost_by_cycle_canceling	(	Net &	net,
		double	it_factor = `0.4`,
		size_t	step = `10`
	)

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 negativo encontrado, se cancela el ciclo por aumento del flujo por el ciclo y asÃ se elimina.

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.

Parameters

[in]	net	la red a maximizar flujo y minimizar coste.
[in]	it_factor	factor de iteraciones en el cual el algoritmo de Bellman-Ford comenzarÃ¡ a buscar ciclos negativos

Exceptions

bad_alloc si no hay suficiente memoria.

Returns: Una dupla con la cantidad de ciclos encontrados y el factor final de iteraciones

Here is the call graph for this function:

◆ min_cut()

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

Net::Flow_Type Aleph::min_cut	(	Net &	net,
		DynSetTree< typename Net::Node *> &	vs,
		DynSetTree< typename Net::Node *> &	vt,
		DynList< typename Net::Arc *> &	cuts,
		DynList< typename Net::Arc *> &	cutt
	)

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.

Parameters

[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.

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

See also: 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

Here is the call graph for this function:

◆ random_preflow_maximum_flow()

template<class Net >

Net::Flow_Type Aleph::random_preflow_maximum_flow ( Net & net )

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.

Parameters

[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.

Returns: el valor de flujo maximizado de la red

Exceptions

bad_alloc si no hay suficiente memoria.

Here is the caller graph for this function:

◆ remaining_flow()

template<class Net >

Net::Flow_Type Aleph::remaining_flow	(	typename Net::Node *	src,
		typename Net::Arc *	a
	)

noexcept

Retorna el flujo restante segÃºn que a respecto al nodo p sea o no un arco residual.

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ Parc

◆ SemiPath

Function Documentation

◆ aumenting_path_maximum_flow()

◆ decrease_flow()

◆ edmonds_karp_maximum_flow()

◆ fifo_preflow_maximum_flow()

◆ find_aumenting_path()

◆ find_aumenting_path_bfs()

◆ find_aumenting_path_dfs()

◆ find_aumenting_semi_path()

◆ find_aumenting_semi_path_bfs()

◆ find_aumenting_semi_path_dfs()

◆ find_decrementing_path()

◆ find_decrementing_path_bfs()

◆ find_decrementing_path_dfs()

◆ ford_fulkerson_maximum_flow()

◆ generic_preflow_vertex_push_maximum_flow()

◆ heap_preflow_maximum_flow()

◆ increase_flow() [1/2]

◆ increase_flow() [2/2]

◆ max_flow_min_cost_by_cycle_canceling()

◆ min_cut()

◆ random_preflow_maximum_flow()

◆ remaining_flow()