#include <tpl_maxflow_mincost.H>

Métodos públicos
void	by_cycle_canceling_and_dummy_arc (Net &net) const

template<template< class > class Max_Flow_Algo>
void	by_cycle_canceling (Net &net, bool leave_residual=false)

Descripción detallada

template<class Net>
class Aleph::Max_Flow_Min_Cost< Net >

Clase de cálculo de flujo máximo a coste máximo.

Esta clase emplea como parámetro tipo una red de flujo con costes y ofrece distintas primitivas para maximizar flujo a coste mínimo.

Documentación de las funciones miembro

template<class Net >

template<template< class > class Max_Flow_Algo>

void Aleph::Max_Flow_Min_Cost< Net >::by_cycle_canceling	(	Net &	net,
		bool	leave_residual = `false`
	)

inline

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< Net >::by_cycle_canceling_and_dummy_arc ( Net & net ) const

inline

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.

Hace referencia a Aleph::max_flow_min_cost_by_cycle_canceling().

Gráfico de llamadas para esta función:

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

tpl_maxflow_mincost.H

Métodos públicos

Descripción detallada

template<class Net> class Aleph::Max_Flow_Min_Cost< Net >

Documentación de las funciones miembro

template<class Net>
class Aleph::Max_Flow_Min_Cost< Net >