Рубрики

Алгоритм Push Relabel | Набор 2 (реализация)

Мы настоятельно рекомендуем обратиться к статье ниже, прежде чем перейти к этой статье.
Алгоритм Push Relabel | Комплект 1 (Введение и Иллюстрация)

Постановка задачи: приведен график, представляющий сеть потоков, где каждое ребро имеет пропускную способность. Также, учитывая две вершины источника 's' и приемника 't' в графе, найдите максимально возможный поток от s до t со следующими ограничениями:

а) Поток на ребре не превышает заданную мощность ребра.

б) Входящий поток равен исходящему потоку для каждой вершины, кроме s и t.

Например, рассмотрим следующий график из книги CLRS.

Максимально возможный поток на графике выше 23.

Push-Relabel Algorithm 
1) Initialize PreFlow : Initialize Flows and Heights 

2) While it is possible to perform a Push() or Relablel() on a vertex
   // Or while there is a vertex that has excess flow
           Do Push() or Relabel()

// At this point all vertices have Excess Flow as 0 (Except source
// and sink)
3) Return flow.

Ниже приведены основные операции, выполняемые в алгоритме Push Relabel.

В алгоритме Push-Relabel есть три основных операции

  1. Initialize PreFlow () Инициализирует высоты и потоки всех вершин.
    Preflow() 
    1) Initialize height and flow of every vertex as 0.
    2) Initialize height of source vertex equal to total 
       number of vertices in graph.
    3) Initialize flow of every edge as 0.
    4) For all vertices adjacent to source s, flow and  
       excess flow is equal to capacity initially.
  2. Push () используется для создания потока из узла, который имеет избыточный поток. Если у вершины есть избыточный поток, и есть соседний с меньшей высотой (в остаточном графе), мы продвигаем поток из вершины в соседний с меньшей высотой. Количество проталкиваемого потока через трубу (кромку) равно минимуму избыточного потока и вместимости кромки.
  3. Операция Relabel () используется, когда вершина имеет избыточный поток, и ни одна из ее смежных не находится на более низкой высоте. Мы в основном увеличиваем высоту вершины, чтобы мы могли выполнить push (). Чтобы увеличить высоту, мы выбираем минимальную смежную высоту (в остаточном графе, т. Е. Соседнюю, к которой мы можем добавить поток) и добавляем к ней 1.

Реализация:

Следующая реализация использует структуру ниже для представления сети потока.

struct Vertex 
{
   int h;      // Height of node
   int e_flow; // Excess Flow 
}
struct Edge 
{
   int u, v; // Edge is from u to v       
   int flow; // Current flow
   int capacity; 
}
class Graph 
{
   Edge edge[];   // Array of edges
   Vertex ver[];  // Array of vertices 
}

Приведенный ниже код использует сам данный граф в качестве потоковой сети и остаточного графа. Мы не создали отдельный граф для остаточного графа и использовали тот же граф для простоты.

// C ++ программа для реализации алгоритма push-relbel для
// получаем максимальный поток графика
#include <bits/stdc++.h>

using namespace std;

  

struct Edge

{

    // Для сохранения текущего потока и емкости ребра

    int flow, capacity;

  

    // Ребро u ---> v имеет начальную вершину как u и конец

    // вершина как 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;

    }

};

  
// Представляем вершину

struct Vertex

{

    int h, e_flow;

  

    Vertex(int h, int e_flow)

    {

        this->h = h;

        this->e_flow = e_flow;

    }

};

  
// Представлять сеть потока

class Graph

{

    int V;    // Количество вершин

    vector<Vertex> ver;

    vector<Edge> edge;

  

    // Функция выталкивания лишнего потока из вас

    bool push(int u);

  

    // Функция для перемаркировки вершины u

    void relabel(int u);

  

    // Эта функция вызывается для инициализации

    // предварительный поток

    void preflow(int s);

  

    // Функция для изменения края

    void updateReverseEdgeFlow(int i, int flow);

  

public:

    Graph(int V);  // Конструктор

  

    // функция для добавления ребра на график

    void addEdge(int u, int v, int w);

  

    // возвращает максимальный поток от s до t

    int getMaxFlow(int s, int t);

};

  

Graph::Graph(int V)

{

    this->V = V;

  

    // все вершины инициализируются с 0 высотой

    // и 0 избыточный поток

    for (int i = 0; i < V; i++)

        ver.push_back(Vertex(0, 0));

}

  

void Graph::addEdge(int u, int v, int capacity)

{

    // поток инициализируется с 0 для всех ребер

    edge.push_back(Edge(0, capacity, u, v));

}

  

void Graph::preflow(int s)

{

    // Делаем h исходной вершины равным no. вершин

    // Высота остальных вершин равна 0.

    ver[s].h = ver.size();

  

    //

    for (int i = 0; i < edge.size(); i++)

    {

        // Если текущее ребро идет от источника

        if (edge[i].u == s)

        {

            // Поток равен емкости

            edge[i].flow = edge[i].capacity;

  

            // Инициализируем избыточный поток для соседнего v

            ver[edge[i].v].e_flow += edge[i].flow;

  

            // Добавить ребро из v в s в остаточном графе с

            // емкость равна 0

            edge.push_back(Edge(-edge[i].flow, 0, edge[i].v, s));

        }

    }

}

  
// возвращает индекс переполненной вершины

int overFlowVertex(vector<Vertex>& ver)

{

    for (int i = 1; i < ver.size() - 1; i++)

       if (ver[i].e_flow > 0)

            return i;

  

    // -1 если переполненная вершина отсутствует

    return -1;

}

  
// Обновление обратного потока для потока, добавленного в ih 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;

        }

    }

  

    // добавляем обратный край в остаточный график

    Edge e = Edge(0, flow, u, v);

    edge.push_back(e);

}

  
// Чтобы вытолкнуть поток из переполняющейся вершины u

bool Graph::push(int u)

{

    // Пройдите через все ребра, чтобы найти соседний (из вас)

    // к какому потоку можно подтолкнуть

    for (int i = 0; i < edge.size(); i++)

    {

        // Проверяет u текущего ребра так же, как задано

        // переполняющая вершина

        if (edge[i].u == u)

        {

            // если поток равен пропускной способности, то нет толчка

            // возможно

            if (edge[i].flow == edge[i].capacity)

                continue;

  

            // Push возможен только если высота смежных

            // меньше высоты переполняющейся вершины

            if (ver[u].h > ver[edge[i].v].h)

            {

                // Поток, который нужно протолкнуть, равен минимуму

                // оставшийся поток на краю и избыточный поток.

                int flow = min(edge[i].capacity - edge[i].flow,

                               ver[u].e_flow);

  

                // Уменьшаем лишний поток для переполняющейся вершины

                ver[u].e_flow -= flow;

  

                // Увеличить избыточный поток для соседних

                ver[edge[i].v].e_flow += flow;

  

                // Добавить остаточный поток (с емкостью 0 и отрицательным

                // течь)

                edge[i].flow += flow;

  

                updateReverseEdgeFlow(i, flow);

  

                return true;

            }

        }

    }

    return false;

}

  
// функция для перемаркировки вершины u

void Graph::relabel(int u)

{

    // Инициализируем минимальную высоту соседней

    int mh = INT_MAX;

  

    // Находим соседний с минимальной высотой

    for (int i = 0; i < edge.size(); i++)

    {

        if (edge[i].u == u)

        {

            // если поток равен емкости, то нет

            // перемаркировка

            if (edge[i].flow == edge[i].capacity)

                continue;

  

            // Обновляем минимальную высоту

            if (ver[edge[i].v].h < mh)

            {

                mh = ver[edge[i].v].h;

  

                // Обновление высоты вас

                ver[u].h = mh + 1;

            }

        }

    }

}

  
// основная функция для печати максимального потока графика

int Graph::getMaxFlow(int s, int t)

{

    preflow(s);

  

    // цикл до тех пор, пока ни одна из вершин не будет переполнена

    while (overFlowVertex(ver) != -1)

    {

        int u = overFlowVertex(ver);

        if (!push(u))

            relabel(u);

    }

  

    // ver.back () возвращает последнюю вершину, чья

    // e_flow будет конечным максимальным потоком

    return ver.back().e_flow;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int V = 6;

    Graph g(V);

  

    // Создание показанной выше сети потока

    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);

  

    // Инициализация источника и приемника

    int s = 0, t = 5;

  

    cout << "Maximum flow is " << g.getMaxFlow(s, t);

    return 0;

}

Выход

Maximum flow is 23

Код в этой статье предоставлен Сиддхартом Лалвани и Уткаршем Триведи .

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Алгоритм Push Relabel | Набор 2 (реализация)

0.00 (0%) 0 votes