Я пытаюсь получить минимальные сокращения после запуска алгоритма push relbel.
Я взял алгоритм из https://www.geeksforgeeks.org/push-relabel-algorithm-set-2-implementation/
// C++ program to implement push-relabel algorithm for
// getting maximum flow of graph
#include <bits/stdc++.h>
using namespace std;
struct Edge
{
// To store current flow and capacity of edge
int flow, capacity;
// An edge u--->v has start vertex as u and end
// vertex as v.
int u, v;
Edge(int flow, int capacity, int u, int v)
{
this->flow = flow;
this->capacity = capacity;
this->u = u;
this->v = v;
}
};
// Represent a Vertex
struct Vertex
{
int h, e_flow;
Vertex(int h, int e_flow)
{
this->h = h;
this->e_flow = e_flow;
}
};
// To represent a flow network
class Graph
{
int V; // No. of vertices
vector<Vertex> ver;
vector<Edge> edge;
// Function to push excess flow from u
bool push(int u);
// Function to relabel a vertex u
void relabel(int u);
// This function is called to initialize
// preflow
void preflow(int s);
// Function to reverse edge
void updateReverseEdgeFlow(int i, int flow);
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int u, int v, int w);
// returns maximum flow from s to t
int getMaxFlow(int s, int t);
};
Graph::Graph(int V)
{
this->V = V;
// all vertices are initialized with 0 height
// and 0 excess flow
for (int i = 0; i < V; i++)
ver.push_back(Vertex(0, 0));
}
void Graph::addEdge(int u, int v, int capacity)
{
// flow is initialized with 0 for all edge
edge.push_back(Edge(0, capacity, u, v));
}
void Graph::preflow(int s)
{
// Making h of source Vertex equal to no. of vertices
// Height of other vertices is 0.
ver[s].h = ver.size();
//
for (int i = 0; i < edge.size(); i++)
{
// If current edge goes from source
if (edge[i].u == s)
{
// Flow is equal to capacity
edge[i].flow = edge[i].capacity;
// Initialize excess flow for adjacent v
ver[edge[i].v].e_flow += edge[i].flow;
// Add an edge from v to s in residual graph with
// capacity equal to 0
edge.push_back(Edge(-edge[i].flow, 0, edge[i].v, s));
}
}
}
// returns index of overflowing Vertex
int overFlowVertex(vector<Vertex>& ver)
{
for (int i = 1; i < ver.size() - 1; i++)
if (ver[i].e_flow > 0)
return i;
// -1 if no overflowing Vertex
return -1;
}
// Update reverse flow for flow added on ith Edge
void Graph::updateReverseEdgeFlow(int i, int flow)
{
int u = edge[i].v, v = edge[i].u;
for (int j = 0; j < edge.size(); j++)
{
if (edge[j].v == v && edge[j].u == u)
{
edge[j].flow -= flow;
return;
}
}
// adding reverse Edge in residual graph
Edge e = Edge(0, flow, u, v);
edge.push_back(e);
}
// To push flow from overflowing vertex u
bool Graph::push(int u)
{
// Traverse through all edges to find an adjacent (of u)
// to which flow can be pushed
for (int i = 0; i < edge.size(); i++)
{
// Checks u of current edge is same as given
// overflowing vertex
if (edge[i].u == u)
{
// if flow is equal to capacity then no push
// is possible
if (edge[i].flow == edge[i].capacity)
continue;
// Push is only possible if height of adjacent
// is smaller than height of overflowing vertex
if (ver[u].h > ver[edge[i].v].h)
{
// Flow to be pushed is equal to minimum of
// remaining flow on edge and excess flow.
int flow = min(edge[i].capacity - edge[i].flow,
ver[u].e_flow);
// Reduce excess flow for overflowing vertex
ver[u].e_flow -= flow;
// Increase excess flow for adjacent
ver[edge[i].v].e_flow += flow;
// Add residual flow (With capacity 0 and negative
// flow)
edge[i].flow += flow;
updateReverseEdgeFlow(i, flow);
return true;
}
}
}
return false;
}
// function to relabel vertex u
void Graph::relabel(int u)
{
// Initialize minimum height of an adjacent
int mh = INT_MAX;
// Find the adjacent with minimum height
for (int i = 0; i < edge.size(); i++)
{
if (edge[i].u == u)
{
// if flow is equal to capacity then no
// relabeling
if (edge[i].flow == edge[i].capacity)
continue;
// Update minimum height
if (ver[edge[i].v].h < mh)
{
mh = ver[edge[i].v].h;
// updating height of u
ver[u].h = mh + 1;
}
}
}
}
// main function for printing maximum flow of graph
int Graph::getMaxFlow(int s, int t)
{
preflow(s);
// loop untill none of the Vertex is in overflow
while (overFlowVertex(ver) != -1)
{
int u = overFlowVertex(ver);
if (!push(u))
relabel(u);
}
// ver.back() returns last Vertex, whose
// e_flow will be final maximum flow
return ver.back().e_flow;
}
// Driver program to test above functions
int main()
{
int V = 6;
Graph g(V);
// Creating above shown flow network
g.addEdge(0, 1, 16);
g.addEdge(0, 2, 13);
g.addEdge(1, 2, 10);
g.addEdge(2, 1, 4);
g.addEdge(1, 3, 12);
g.addEdge(2, 4, 14);
g.addEdge(3, 2, 9);
g.addEdge(3, 5, 20);
g.addEdge(4, 3, 7);
g.addEdge(4, 5, 4);
// Initialize source and sink
int s = 0, t = 5;
cout << "Maximum flow is " << g.getMaxFlow(s, t);
return 0;
}
Алгоритм работает отлично, но он просто дает окончательный максимальный поток.Я погуглил, чтобы получить минимальное сокращение, и обнаружил, что нам нужно найти все вершины, которые можно посетить из источника в остаточном графе, а затем найти минимальное сокращение.Хотя это имеет смысл, вышеупомянутый алгоритм не дает окончательного остаточного графа, и я думаю, что я должен создать окончательный остаточный граф из всех ребер, что кажется вычислительно дорогим для больших графов.Есть ли способ расчета минимального среза при одновременном вычислении максимального расхода с использованием push-relbel?