c++ - ford - ¿Es correcto el código Sedgewick?

ford fulkerson python

Question

Estoy resolviendo un problema de optimización en el que, entre otras cosas, debo maximizar las redes de flujo. Implementé un algoritmo de maximización de flujo basado en el código c ++ basado en el siguiente código java que aparece en el libro de Sedgewick "Algorithms in Java, Third Edition, Part 5: Graph Algorithms", que maximiza el flujo de una red utilizando un PREFLOW basado en vértices algoritmo de empuje:

class NetworkMaxFlow
{ private Network G; private int s, t;
private int[] h, wt;
private void initheights()
NetworkMaxFlow(Network G, int s, int t)
{ this.G = G; this.s = s; this.t = t;
wt = new int[G.V()]; h = new int[G.V()];
initheights();
intGQ gQ = new intGQ(G.V());
gQ.put(s); wt[t] = -(wt[s] = Edge.M*G.V());
while (!gQ.empty())
{ int v = gQ.get();
AdjList A = G.getAdjList(v);
for (Edge e = A.beg(); !A.end(); e = A.nxt())
{ int w = e.other(v), cap = e.capRto(w);
int P = cap < wt[v] ? cap : wt[v];
if (P > 0 && v == s || h[v] == h[w]+1) // first observation (see below)
{ e.addflowRto(w, P);
wt[v] -= P; wt[w] += P;
if ((w != s) && (w != t)) gQ.put(w); // enqueue w if it is not source or sink
}
}
if (v != s && v != t && wt[v] > 0) // why check v != t if t never enter the queue?
{ h[v]++; gQ.put(v); }
}
}
}

Mi implementación, basada en ese código, falla al maximizar la siguiente red Después de la ejecución, el flujo resultante es el siguiente Con este flujo, el valor del flujo es 8, pero el máximo es 9, como lo indica el flujo de la siguiente figura Según mi entendimiento, el algoritmo es consistente con la explicación del libro. Sin embargo, veo dos cosas extrañas.

1. No hay una fase explícita de preflujo desde la fuente. Se incluye en el while y se ejecuta primero y solo una vez cuando el predicado P > 0 && v == s es verdadero. Tal vez esto se hizo para acortar el código.
2. Según mi entendimiento, y el discurso del libro, el sumidero nunca entra en la cola. Sin embargo, cuando aumenta la altura, el código comprueba que v! = T. ¿Alguna razón para esto?

Este es un extracto de mi implementación de este algoritmo en C ++

template <class Net, class Q_Type> typename Net::Flow_Type
generic_preflow_vertex_push_maximum_flow(Net & net)
{
init_height_in_nodes(net); // breadth first traverse from sink to
// source. Nodes are labeled with their
// minimal distance (in nodes) to sink
auto source = net.get_source();
auto sink = net.get_sink();
using Itor = __Net_Iterator<Net>;
Q_Type q; // generic queue (can be fifo, heap or random) of active nodes
// preflow: floods all nodes connected to the source
for (Itor it(source); it.has_curr(); it.next())
{
auto arc = it.get_curr();
arc->flow = arc->cap; // saturate arc to its maximum
auto tgt = net.get_tgt_node(arc);
put_in_active_queue(q, tgt);
assert(node_height<Net>(source) == node_height<Net>(tgt) + 1);
assert(not is_residual<Net>(source, arc));
}
while (not q.is_empty()) // while there are active nodes
{
auto src = get_from_active_queue(q);
auto excess = net.get_in_flow(src) - net.get_out_flow(src);
for (Itor it(src); it.has_curr(); it.next())
{
auto arc = it.get_curr();
auto tgt = net.get_connected_node(arc, src);
if (node_height<Net>(src) != node_height<Net>(tgt) + 1)
continue; // this arc is not eligible
typename Net::Flow_Type flow_to_push;
if (is_residual<Net>(src, arc))
{
flow_to_push = std::min(arc->flow, excess);
arc->flow -= flow_to_push;
}
else
{
flow_to_push = std::min(arc->cap - arc->flow, excess);
arc->flow += flow_to_push;
}
excess -= flow_to_push;
if (tgt != sink and tgt != source)
put_in_active_queue(q, tgt);
}
if (excess > 0) // src still active?
{
node_height<Net>(src)++;
put_in_active_queue(q, src);
}
}
return net.flow_value(); // sum of all outing flow from source
}

¿Alguien encuentra alguna inconsistencia lógica entre mi código y el código de Sedgewick? Tengo la impresión de que mi código (y quizás también el de Sedgewick) no está manejando adecuadamente los aumentos de altura. Pero no logro entender por qué.

Muestro una traza de ejecución detallada con la red que falla al maximizar (la traza comienza desde el primer q.get () de while. Los valores entre paréntesis son los valores de las alturas. IN es el flujo entrante al nodo. FUERA del uno de salida

Como ejemplo, la línea.

 4104 (2) --> 0 (1) pushing 1 from 4104 toward 0

Se refiere al arco elegible 4104 -> 0. El nodo 4104 tiene altura 2 y el nodo 0 tiene altura 1. La expresión "empujar 1" significa que 1 unidad de flujo se empuja hacia el nodo objetivo (0). La línea ================ separa cada extracción de cola. La cola es FIFO y su estado se imprime al final de cada procesamiento.

Tenga en cuenta que muchas veces las unidades de flujo cero se empujan o reducen, pero el nodo de destino se activa.

Esta es la traza de ejecución.

Initial Queue = 4104 4105 4106 4107 4108
Active node 4104 Height = 2 IN = 1 OUT = 0
4104 (2) --> source (3) not eligible
4104 (2) --> 0 (1) pushing 1 from 4104 toward 0
4104 (2) --> 1 (1) pushing 0 from 4104 toward 1
4104 (2) --> 2 (1) pushing 0 from 4104 toward 2
4104 (2) --> 4 (1) pushing 0 from 4104 toward 4
Excess = 0
Queue = 4105 4106 4107 4108 0 1 2 4
================
Active node 4105 Height = 2 IN = 3 OUT = 0
4105 (2) --> source (3) not eligible
4105 (2) --> 1 (1) pushing 1 from 4105 toward 1
4105 (2) --> 4 (1) pushing 1 from 4105 toward 4
4105 (2) --> 6 (1) pushing 1 from 4105 toward 6
Excess = 0
Queue = 4106 4107 4108 0 1 2 4 6
================
Active node 4106 Height = 2 IN = 1 OUT = 0
4106 (2) --> source (3) not eligible
4106 (2) --> 1 (1) pushing 1 from 4106 toward 1
4106 (2) --> 5 (1) pushing 0 from 4106 toward 5
Excess = 0
Queue = 4107 4108 0 1 2 4 6 5
================
Active node 4107 Height = 2 IN = 1 OUT = 0
4107 (2) --> source (3) not eligible
4107 (2) --> 1 (1) pushing 1 from 4107 toward 1
4107 (2) --> 2 (1) pushing 0 from 4107 toward 2
4107 (2) --> 3 (1) pushing 0 from 4107 toward 3
4107 (2) --> 4 (1) pushing 0 from 4107 toward 4
4107 (2) --> 6 (1) pushing 0 from 4107 toward 6
Excess = 0
Queue = 4108 0 1 2 4 6 5 3
================
Active node 4108 Height = 2 IN = 3 OUT = 0
4108 (2) --> source (3) not eligible
4108 (2) --> 1 (1) pushing 1 from 4108 toward 1
4108 (2) --> 2 (1) pushing 1 from 4108 toward 2
4108 (2) --> 4 (1) pushing 1 from 4108 toward 4
4108 (2) --> 5 (1) pushing 0 from 4108 toward 5
4108 (2) --> 6 (1) pushing 0 from 4108 toward 6
Excess = 0
Queue = 0 1 2 4 6 5 3
================
Active node 0 Height = 1 IN = 1 OUT = 0
0 (1) --> sink (0) pushing 1 from 0 toward sink
0 (1) --> 4104 (2) not eligible
Excess = 0
Queue = 1 2 4 6 5 3
================
Active node 1 Height = 1 IN = 4 OUT = 0
1 (1) --> sink (0) pushing 2 from 1 toward sink
1 (1) --> 4105 (2) not eligible
1 (1) --> 4106 (2) not eligible
1 (1) --> 4107 (2) not eligible
1 (1) --> 4108 (2) not eligible
Excess = 2 1 goes back onto queue with label 2
Queue = 2 4 6 5 3 1
================
Active node 2 Height = 1 IN = 1 OUT = 0
2 (1) --> sink (0) pushing 1 from 2 toward sink
2 (1) --> 4108 (2) not eligible
Excess = 0
Queue = 4 6 5 3 1
================
Active node 4 Height = 1 IN = 2 OUT = 0
4 (1) --> sink (0) pushing 2 from 4 toward sink
4 (1) --> 4105 (2) not eligible
4 (1) --> 4108 (2) not eligible
Excess = 0
Queue = 6 5 3 1
================
Active node 6 Height = 1 IN = 1 OUT = 0
6 (1) --> sink (0) pushing 1 from 6 toward sink
6 (1) --> 4105 (2) not eligible
Excess = 0
Queue = 5 3 1
================
Active node 5 Height = 1 IN = 0 OUT = 0
5 (1) --> sink (0) pushing 0 from 5 toward sink
Excess = 0
Queue = 3 1
================
Active node 3 Height = 1 IN = 0 OUT = 0
3 (1) --> sink (0) pushing 0 from 3 toward sink
Excess = 0
Queue = 1
================
Active node 1 Height = 2 IN = 4 OUT = 2
1 (2) --> 4105 (2) not eligible
1 (2) --> 4106 (2) not eligible
1 (2) --> 4107 (2) not eligible
1 (2) --> 4108 (2) not eligible
Excess = 2 1 goes back onto queue with label 3
Queue = 1
================
Active node 1 Height = 3 IN = 4 OUT = 2
1 (3) --> 4105 (2) Reducing 1 from 1 toward 4105
1 (3) --> 4106 (2) Reducing 1 from 1 toward 4106
1 (3) --> 4107 (2) Reducing 0 from 1 toward 4107
1 (3) --> 4108 (2) Reducing 0 from 1 toward 4108
Excess = 0
Queue = 4105 4106 4107 4108
================
Active node 4105 Height = 2 IN = 3 OUT = 2
4105 (2) --> source (3) not eligible
4105 (2) --> 1 (3) not eligible
Excess = 1 4105 goes back onto queue with label 3
Queue = 4106 4107 4108 4105
================
Active node 4106 Height = 2 IN = 1 OUT = 0
4106 (2) --> source (3) not eligible
4106 (2) --> 1 (3) not eligible
4106 (2) --> 5 (1) pushing 1 from 4106 toward 5
Excess = 0
Queue = 4107 4108 4105 5
================
Active node 4107 Height = 2 IN = 1 OUT = 1
4107 (2) --> source (3) not eligible
4107 (2) --> 2 (1) pushing 0 from 4107 toward 2
4107 (2) --> 3 (1) pushing 0 from 4107 toward 3
4107 (2) --> 4 (1) pushing 0 from 4107 toward 4
4107 (2) --> 6 (1) pushing 0 from 4107 toward 6
Excess = 0
Queue = 4108 4105 5 2 3 4 6
================
Active node 4108 Height = 2 IN = 3 OUT = 3
4108 (2) --> source (3) not eligible
4108 (2) --> 5 (1) pushing 0 from 4108 toward 5
4108 (2) --> 6 (1) pushing 0 from 4108 toward 6
Excess = 0
Queue = 4105 5 2 3 4 6
================
Active node 4105 Height = 3 IN = 3 OUT = 2
4105 (3) --> source (3) not eligible
4105 (3) --> 1 (3) not eligible
Excess = 1 4105 goes back onto queue with label 4
Queue = 5 2 3 4 6 4105
================
Active node 5 Height = 1 IN = 1 OUT = 0
5 (1) --> sink (0) pushing 1 from 5 toward sink
5 (1) --> 4106 (2) not eligible
Excess = 0
Queue = 2 3 4 6 4105
================
Active node 2 Height = 1 IN = 1 OUT = 1
2 (1) --> sink (0) pushing 0 from 2 toward sink
2 (1) --> 4108 (2) not eligible
Excess = 0
Queue = 3 4 6 4105
================
Active node 3 Height = 1 IN = 0 OUT = 0
3 (1) --> sink (0) pushing 0 from 3 toward sink
Excess = 0
Queue = 4 6 4105
================
Active node 4 Height = 1 IN = 2 OUT = 2
4 (1) --> 4105 (4) not eligible
4 (1) --> 4108 (2) not eligible
Excess = 0
Queue = 6 4105
================
Active node 6 Height = 1 IN = 1 OUT = 1
6 (1) --> sink (0) pushing 0 from 6 toward sink
6 (1) --> 4105 (4) not eligible
Excess = 0
Queue = 4105
================
Active node 4105 Height = 4 IN = 3 OUT = 2
4105 (4) --> source (3) Reducing 1 from 4105 toward source
4105 (4) --> 1 (3) pushing 0 from 4105 toward 1
Excess = 0
Queue = 1
================
Active node 1 Height = 3 IN = 2 OUT = 2
1 (3) --> 4107 (2) Reducing 0 from 1 toward 4107
1 (3) --> 4108 (2) Reducing 0 from 1 toward 4108
Excess = 0
Queue = 4107 4108
================
Active node 4107 Height = 2 IN = 1 OUT = 1
4107 (2) --> source (3) not eligible
4107 (2) --> 2 (1) pushing 0 from 4107 toward 2
4107 (2) --> 3 (1) pushing 0 from 4107 toward 3
4107 (2) --> 4 (1) pushing 0 from 4107 toward 4
4107 (2) --> 6 (1) pushing 0 from 4107 toward 6
Excess = 0
Queue = 4108 2 3 4 6
================
Active node 4108 Height = 2 IN = 3 OUT = 3
4108 (2) --> source (3) not eligible
4108 (2) --> 5 (1) pushing 0 from 4108 toward 5
4108 (2) --> 6 (1) pushing 0 from 4108 toward 6
Excess = 0
Queue = 2 3 4 6 5
================
Active node 2 Height = 1 IN = 1 OUT = 1
2 (1) --> sink (0) pushing 0 from 2 toward sink
2 (1) --> 4108 (2) not eligible
Excess = 0
Queue = 3 4 6 5
================
Active node 3 Height = 1 IN = 0 OUT = 0
3 (1) --> sink (0) pushing 0 from 3 toward sink
Excess = 0
Queue = 4 6 5
================
Active node 4 Height = 1 IN = 2 OUT = 2
4 (1) --> 4105 (4) not eligible
4 (1) --> 4108 (2) not eligible
Excess = 0
Queue = 6 5
================
Active node 6 Height = 1 IN = 1 OUT = 1
6 (1) --> sink (0) pushing 0 from 6 toward sink
6 (1) --> 4105 (4) not eligible
Excess = 0
Queue = 5
================
Active node 5 Height = 1 IN = 1 OUT = 1
5 (1) --> sink (0) pushing 0 from 5 toward sink
5 (1) --> 4106 (2) not eligible
Excess = 0
Queue =

Answer 1

Tus preguntas

Preflujo

No hay una fase explícita de preflujo desde la source . Se incluye en el while y se ejecuta primero y solo una vez cuando el predicado P > 0 && v == s es true . Tal vez esto se hizo para acortar el código.

Sí, creo que se hizo para compactar el código. Debido a la asignación wt[s] = Edge.M*GV() al principio, la fuente tiene suficiente exceso "virtual" para alimentar el preflujo en la primera iteración del algoritmo. Si quisiera hacer el mismo truco en su implementación, tendría que inflar el excess variable (que calcula sobre la marcha en lugar de almacenarlo en una matriz como Sedgewick) durante la primera iteración, cuando se encuentra con el nodo de origen. Pero no tiene que hacerlo de esa manera, su preflooding explícito parece estar bien y probablemente incluso hace las cosas más legibles.

También sospecho que en la condición P > 0 && v == s || h[v] == h[w]+1 P > 0 && v == s || h[v] == h[w]+1 la prioridad implícita del operador (P > 0 && v == s) || h[v] == h[w]+1 (P > 0 && v == s) || h[v] == h[w]+1 no fue pensado. La forma en que está escrito, la comprobación P > 0 solo se realiza para el caso de origen. No comprobarlo en los otros casos no se verá afectado porque ejecutar el cuerpo con P == 0 solo empujará un exceso de 0 a otros nodos (lo que no hace nada) y agregará innecesariamente esos otros nodos a la cola, solo para ellos siendo removido de nuevo inmediatamente. He visto que lo implementaste de la misma manera. Eso está bien, aunque sea una pequeña pérdida de tiempo computacional. Probablemente P > 0 && (v == s || h[v] == h[w]+1) fue realmente la intención.

Hundirse en la cola

Según mi entendimiento, y el discurso del libro, el sumidero nunca entra en la cola. Sin embargo, cuando aumenta la altura, el código comprueba que v! = T. ¿Alguna razón para esto?

Estoy de acuerdo, esto es raro. La única forma en que el sumidero puede ingresar a la cola es ser la fuente al mismo tiempo (en un gráfico con un solo nodo y sin bordes). Sin embargo, en ese caso, la condición v != s ya evita el bucle infinito, no es necesaria ninguna condición adicional.

Resultados erróneos

Después de la ejecución, el flujo resultante es el siguiente [...] Con este flujo, el valor del flujo es 8, pero el máximo es 9

Alturas iniciales

Estás obteniendo resultados erróneos porque tus alturas iniciales están equivocadas. No puedo comparar el código de inicialización de Sedgewick con el tuyo porque tu publicación tampoco especifica. Pero aprendo de su archivo de registro que está comenzando con una altura de 3 para la source . Esto está claramente en contra de las condiciones para las funciones de altura : la source debe comenzar con una altura igual al número de nodos en su gráfica y la mantendrá durante todo el algoritmo.

En su caso, la altura de la source está demasiado cerca de la altura de sus vecinos aguas abajo. Esto hace que los vecinos del flujo descendente devuelvan algo de flujo a la fuente muy pronto, antes de esforzarse lo suficiente para dejar que fluya más río abajo. Se supone que deben hacerlo solo si no hay forma de dejar que fluya hacia el fregadero.

¿Gráfico roto?

Lo que más me preocupa es que el borde [4104 -> 1] parece desaparecer. Si bien se menciona durante el procesamiento del nodo 4104, nunca aparece durante el procesamiento del nodo 1. Se mencionan todos los demás bordes entrantes, ya sea con respecto a "no elegible", "empuje" o "reducción". Espero que aparezca como uno de los tres tipos, al igual que los otros. Pero, de nuevo, no sé exactamente dónde colocas esas declaraciones de registro. Aún así, deja un poco de preocupación y pensé que lo mencionaría en caso de que todavía tengas problemas después de fijar tus alturas.