Aleph::Compute_Min_Cut< GT, Max_Flow, SA > Class Template Reference

#include <tpl_kgraph.H>

Public Member Functions
long	operator() (GT &g, Aleph::set< typename GT::Node *> &l, Aleph::set< typename GT::Node *> &r, DynDlist< typename GT::Arc *> &cut)

Detailed Description

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.

Parameters

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

Returns

la conectividad en arcos del grafo.

Exceptions

bad_alloc

si no hay suficiente memoria.

---

The documentation for this class was generated from the following file:

• tpl_kgraph.H