Referencia de la plantilla de la Clase Aleph::Compute_Min_Cut< GT, Max_Flow, SA >

#include <tpl_kgraph.H>

Métodos públicos
long	operator() (GT &g, Aleph::set< typename GT::Node * > &l, Aleph::set< typename GT::Node * > &r, DynDlist< typename GT::Arc * > &cut)

Descripción detallada

template<class GT, template< class > class Max_Flow = Heap_Preflow_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
class Aleph::Compute_Min_Cut< GT, Max_Flow, SA >

Clase de cálculo de corte mínimo de un grafo.

compute_min_cut(g, l, r, cut) indaga la conectividad en arcos del grafo g y retorna los conjuntos de nodos y arcos que conforman el corte.

El algoritmo construye una red capacitada unitaria equivalente y mediante sucesivas maximizaciones de flujo indaga la conectividad en arcos.

La rutina recibe dos paráetros tipo:

1. GT: el tipo grafo sobre al cual se le desea averiguar su conectividad.
2. Max_Flow el algoritmo de maximización de flujo a emplear para averiguar conectividad. Por omisión, el algoritmo de maximización es por empuje de preflujo con heap.

Parámetros

[in]	g	el grafo sobre el cual se desea calcular el corte mínimo.
[out]	l	un conjunto de nodos origen que involucra los arcos parte del corte.
[out]	r	un conjunto de nodos destino que involucra los arcos parte del corte y que son destino de los nodos en l.
[out]	cut	el conjunto de arcos parte del corte.

Devuelve

la conectividad en arcos del grafo.

Excepciones

bad_alloc

si no hay suficiente memoria.

---

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

• tpl_kgraph.H