El algoritmo push-relabel (alternativamente, algoritmo preflow-push) es un algoritmo para calcular los flujos máximos en una red de flujo. Los algoritmos Push-relabel funcionan de una manera más localizada que el método Ford Fulkerson . En lugar de examinar toda la red residual para encontrar una ruta de aumento, los algoritmos push-relabel funcionan en un vértice a la vez, observando solo los vecinos del vértice en la red residual.
Intuición
El algoritmo de reetiquetado de empuje se puede entender en términos de flujos de fluidos. Todos los vértices representan uniones de tuberías y todos los bordes dirigidos representan tuberías que tienen una capacidad específica. Cada vértice tiene dos propiedades especiales. Contienen un depósito para almacenar el exceso de caudal y el vértice junto con el depósito se colocan sobre una plataforma a una altura determinada.
Podemos empujar el flujo solo cuesta abajo, es decir, desde un vértice a mayor altura a uno a menor altura. Inicialmente, la fuente está a una altura de V (número de vértices) y el sumidero está a una altura de 0. La altura de todos los demás vértices es 0 y aumenta a medida que avanza el algoritmo. Primero, enviamos tanto flujo como podamos desde la fuente a todos sus vértices intermedios, donde se almacena en su depósito.
Ahora todos los vértices intermedios de la fuente están desbordados. No podemos empujar el flujo hacia adelante ya que estarán ubicados a una altura 0. Para enviar el flujo hacia adelante, debemos aumentar su altura en 1.
El proceso continúa hasta llegar al fregadero.
Al final, vaciamos todo el exceso de líquido almacenado en cualquiera de los depósitos de vértice (si los hay) enviando el flujo de regreso a la fuente. El caudal obtenido entonces será caudal máximo.
Operaciones
- Empuje: la operación de empuje se aplica en un vértice desbordado para empujar el flujo hacia adelante. El algoritmo encuentra vértices adyacentes de u que están a una altura menor que u . Para cada vértice adyacente, envía el flujo máximo posible, que es el mínimo de exceso de flujo en u y la capacidad del borde que conecta u con v .
- Relabel: la operación Relabel se aplica en un vértice u desbordado para aumentar su altura. El algoritmo encuentra el vértice adyacente v de u que tiene la altura mínima. Luego se actualiza
*** QuickLaTeX no puede compilar la fórmula: *** Mensaje de error: Error: nada que mostrar, la fórmula está vacía
Algoritmo
El algoritmo genérico push-relabel utiliza una función de inicialización – flujo previo. La función se presenta a continuación seguida del algoritmo.
Inicializar-Preflujo
1. inicializar la altura y el exceso de flujo de cada vértice a 0
2. establecer la altura de la fuente al número de vértices
3. inicializa el flujo de cada borde a 0
4. para cada vértice adyacente de la fuente, ajuste su flujo y exceso de flujo a la capacidad del borde que los conecta
Generic-Push-Relabel
1. Inicializar-Preflujo
2. mientras exista una operación de inserción o reetiquetado aplicable
3. seleccione una operación de empujar o volver a etiquetar aplicable y realizarla
4. flujo de retorno
FIFO Push-Relabel vs Push-Relabel
FIFO push rebel es una optimización en el push rebel original . En lugar de gastar tiempo lineal en encontrar el vértice desbordado, organizamos todos los vértices desbordados en una cola . Si lo hace, nos permite encontrar un vértice desbordante en tiempo constante . Esto reduce la complejidad del tiempo a O(V 3 ) desde O(V 2 E).
Implementación del algoritmo FIFO Push-Relabel
Declaración de problema de ejemplo: en el código siguiente, se ha encapsulado un gráfico dirigido en una clase DirectedGraph que se ha implementado primero. Contiene una clase anidada Vertex que encapsula el borde del gráfico. Considere el gráfico que se muestra a continuación:
El borde de 0 -> 1 será encapsulado por un objeto de vértice V (1, 3) donde 1 es el destino y 3 es el peso. Se almacenará en el índice 0 de la array de adyacencia. Aquí está la array de adyacencia del gráfico anterior.
0: [[1, 3], [3, 4]] 1: [[2, 1]] 2: [[3, 2]] 3: []
Java
import java.util.ArrayList;
import java.util.LinkedList;
// DirectedGraph class explained above
class DirectedGraph {
public static class Vertex {
// number of the end vertex
// weight or capacity
// associated with the edge
Integer i;
Integer w;
public Vertex(Integer i, Integer w)
{
this.i = i;
this.w = w;
}
}
final ArrayList<ArrayList<Vertex> > adjacencyList;
int vertices;
public DirectedGraph(int vertices)
{
this.vertices = vertices;
adjacencyList = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++)
adjacencyList.add(new ArrayList<>());
}
public void addEdge(Integer u, Integer v,
Integer weight)
{
adjacencyList.get(u)
.add(new Vertex(v, weight));
}
boolean hasEdge(int u, int v)
{
if (u >= vertices)
return false;
for (Vertex vertex : adjacencyList.get(u))
if (vertex.i == v)
return true;
return false;
}
// Returns null if no edge
// is found between u and v
DirectedGraph.Vertex getEdge(int u, int v)
{
for (DirectedGraph.Vertex vertex :
adjacencyList.get(u))
if (vertex.i == v)
return vertex;
return null;
}
}
public class MaxFlow {
private final int source;
private final int sink;
private final DirectedGraph graph;
private DirectedGraph residualGraph;
public MaxFlow(DirectedGraph graph,
int source,
int sink)
{
this.graph = graph;
this.source = source;
this.sink = sink;
}
private void initResidualGraph()
{
residualGraph
= new DirectedGraph(graph.vertices);
// Construct residual graph
for (int u = 0; u < graph.vertices; u++) {
for (DirectedGraph.Vertex v :
graph.adjacencyList.get(u)) {
// If forward edge already
// exists, update its weight
if (residualGraph.hasEdge(u, v.i))
residualGraph.getEdge(u, v.i).w
+= v.w;
// In case it does not
// exist, create one
else
residualGraph.addEdge(u, v.i, v.w);
// If backward edge does
// not already exist, add it
if (!residualGraph.hasEdge(v.i, u))
residualGraph.addEdge(v.i, u, 0);
}
}
}
public int FIFOPushRelabel()
{
initResidualGraph();
LinkedList<Integer> queue
= new LinkedList<>();
// Step 1: Initialize pre-flow
// to store excess flow
int[] e = new int[graph.vertices];
// to store height of vertices
int[] h
= new int[graph.vertices];
boolean[] inQueue
= new boolean[graph.vertices];
// set the height of source to V
h = graph.vertices;
// send maximum flow possible
// from source to all its adjacent vertices
for (DirectedGraph.Vertex v :
graph.adjacencyList.get(source)) {
residualGraph.getEdge(source, v.i).w = 0;
residualGraph.getEdge(v.i, source).w = v.w;
// update excess flow
e[v.i] = v.w;
if (v.i != sink) {
queue.add(v.i);
inQueue[v.i] = true;
}
}
// Step 2: Update the pre-flow
// while there remains an applicable
// push or relabel operation
while (!queue.isEmpty()) {
// vertex removed from
// queue in constant time
int u = queue.removeFirst();
inQueue[u] = false;
relabel(u, h);
push(u, e, h, queue, inQueue);
}
return e[sink];
}
private void relabel(int u, int[] h)
{
int minHeight = Integer.MAX_VALUE;
for (DirectedGraph.Vertex v :
residualGraph.adjacencyList.get(u)) {
if (v.w > 0)
minHeight = Math.min(h[v.i],
minHeight);
}
h[u] = minHeight + 1;
}
private void push(int u, int[] e, int[] h,
LinkedList<Integer> queue,
boolean[] inQueue)
{
for (DirectedGraph.Vertex v :
residualGraph.adjacencyList.get(u)) {
// after pushing flow if
// there is no excess flow,
// then break
if (e[u] == 0)
break;
// push more flow to
// the adjacent v if possible
if (v.w > 0 && h[v.i] < h[u]) {
// flow possible
int f = Math.min(e[u], v.w);
v.w -= f;
residualGraph.getEdge(v.i, u).w += f;
e[u] -= f;
e[v.i] += f;
// add the new overflowing
// immediate vertex to queue
if (!inQueue[v.i] && v.i != source
&& v.i != sink) {
queue.add(v.i);
inQueue[v.i] = true;
}
}
}
// if after sending flow to all the
// intermediate vertices, the
// vertex is still overflowing.
// add it to queue again
if (e[u] != 0) {
queue.add(u);
inQueue[u] = true;
}
}
public static void main(String[] args)
{
final int vertices = 6;
final int source = 0;
final int sink = 5;
DirectedGraph dg
= new DirectedGraph(vertices);
dg.addEdge(0, 1, 16);
dg.addEdge(0, 2, 13);
dg.addEdge(1, 2, 10);
dg.addEdge(2, 1, 4);
dg.addEdge(1, 3, 12);
dg.addEdge(3, 2, 9);
dg.addEdge(2, 4, 14);
dg.addEdge(4, 5, 4);
dg.addEdge(4, 3, 7);
dg.addEdge(3, 5, 20);
MaxFlow maxFlow
= new MaxFlow(
dg, source, sink);
System.out.println(
"Max flow: "
+ maxFlow.FIFOPushRelabel());
}
}
C#
using System;
using System.Collections.Generic;
// DirectedGraph class explained above
class DirectedGraph
{
public class Vertex
{
// number of the end vertex
// weight or capacity
// associated with the edge
public int i;
public int w;
public Vertex(int i, int w)
{
this.i = i;
this.w = w;
}
}
readonly public List<List<Vertex> > adjacencyList;
public int vertices;
public DirectedGraph(int vertices)
{
this.vertices = vertices;
adjacencyList = new List<List<Vertex> >(vertices);
for (int i = 0; i < vertices; i++)
adjacencyList.Add(new List<Vertex>());
}
public void addEdge(int u, int v,
int weight)
{
adjacencyList[u]
.Add(new Vertex(v, weight));
}
public bool hasEdge(int u, int v)
{
if (u >= vertices)
return false;
foreach (Vertex vertex in adjacencyList[u])
if (vertex.i == v)
return true;
return false;
}
// Returns null if no edge
// is found between u and v
public DirectedGraph.Vertex getEdge(int u, int v)
{
foreach (DirectedGraph.Vertex vertex in
adjacencyList[u])
if (vertex.i == v)
return vertex;
return null;
}
}
public class MaxFlow {
private readonly int source;
private readonly int sink;
private readonly DirectedGraph graph;
private DirectedGraph residualGraph;
MaxFlow(DirectedGraph graph,
int source,
int sink)
{
this.graph = graph;
this.source = source;
this.sink = sink;
}
private void initResidualGraph()
{
residualGraph
= new DirectedGraph(graph.vertices);
// Construct residual graph
for (int u = 0; u < graph.vertices; u++) {
foreach (DirectedGraph.Vertex v in
graph.adjacencyList[u]) {
// If forward edge already
// exists, update its weight
if (residualGraph.hasEdge(u, v.i))
residualGraph.getEdge(u, v.i).w
+= v.w;
// In case it does not
// exist, create one
else
residualGraph.addEdge(u, v.i, v.w);
// If backward edge does
// not already exist, add it
if (!residualGraph.hasEdge(v.i, u))
residualGraph.addEdge(v.i, u, 0);
}
}
}
public int FIFOPushRelabel()
{
initResidualGraph();
List<int> queue
= new List<int>();
// Step 1: Initialize pre-flow
// to store excess flow
int[] e = new int[graph.vertices];
// to store height of vertices
int[] h
= new int[graph.vertices];
bool[] inQueue
= new bool[graph.vertices];
// set the height of source to V
h = graph.vertices;
// send maximum flow possible
// from source to all its adjacent vertices
foreach (DirectedGraph.Vertex v in
graph.adjacencyList) {
residualGraph.getEdge(source, v.i).w = 0;
residualGraph.getEdge(v.i, source).w = v.w;
// update excess flow
e[v.i] = v.w;
if (v.i != sink) {
queue.Add(v.i);
inQueue[v.i] = true;
}
}
// Step 2: Update the pre-flow
// while there remains an applicable
// push or relabel operation
while (queue.Count!=0) {
// vertex removed from
// queue in constant time
int u = queue[0];
queue.RemoveAt(0);
inQueue[u] = false;
relabel(u, h);
push(u, e, h, queue, inQueue);
}
return e[sink];
}
private void relabel(int u, int[] h)
{
int minHeight = int.MaxValue;
foreach (DirectedGraph.Vertex v in
residualGraph.adjacencyList[u]) {
if (v.w > 0)
minHeight = Math.Min(h[v.i],
minHeight);
}
h[u] = minHeight + 1;
}
private void push(int u, int[] e, int[] h,
List<int> queue,
bool[] inQueue)
{
foreach (DirectedGraph.Vertex v in
residualGraph.adjacencyList[u])
{
// after pushing flow if
// there is no excess flow,
// then break
if (e[u] == 0)
break;
// push more flow to
// the adjacent v if possible
if (v.w > 0 && h[v.i] < h[u]) {
// flow possible
int f = Math.Min(e[u], v.w);
v.w -= f;
residualGraph.getEdge(v.i, u).w += f;
e[u] -= f;
e[v.i] += f;
// add the new overflowing
// immediate vertex to queue
if (!inQueue[v.i] && v.i != source
&& v.i != sink) {
queue.Add(v.i);
inQueue[v.i] = true;
}
}
}
// if after sending flow to all the
// intermediate vertices, the
// vertex is still overflowing.
// add it to queue again
if (e[u] != 0) {
queue.Add(u);
inQueue[u] = true;
}
}
public static void Main(String[] args)
{
int vertices = 6;
int source = 0;
int sink = 5;
DirectedGraph dg
= new DirectedGraph(vertices);
dg.addEdge(0, 1, 16);
dg.addEdge(0, 2, 13);
dg.addEdge(1, 2, 10);
dg.addEdge(2, 1, 4);
dg.addEdge(1, 3, 12);
dg.addEdge(3, 2, 9);
dg.addEdge(2, 4, 14);
dg.addEdge(4, 5, 4);
dg.addEdge(4, 3, 7);
dg.addEdge(3, 5, 20);
MaxFlow maxFlow
= new MaxFlow(
dg, source, sink);
Console.WriteLine(
"Max flow: "
+ maxFlow.FIFOPushRelabel());
}
}
// This code is contributed by 29AjayKumar
Max flow: 23
Complejidad del Tiempo: O(V 3 )
Publicación traducida automáticamente
Artículo escrito por anujanonymous y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA