Глава 22. Потоки в сетях. Такой подход позволяет отделить абстракцию, необходимую рассматриваемым нами алгоритмам (ребра идут в обоих направлениях)

Такой подход позволяет отделить абстракцию, необходимую рассматриваемым нами алгоритмам (ребра идут в обоих направлениях), от конкретной структуры данных клиента, и ставит перед этими алгоритмами простую цель: присвоить элементам данных flow в реб­рах клиента такие значения, которые обеспечивают максимизацию потока через сеть. В самом деле, критическая компонента в нашей реализации требует замены абстракции сети, которая зависит от значений потока и реализуется посредством функций-элементов класса EDGE. Мы будем рассматривать реализацию функций класса EDGE (программа 22.2) в разделе 22.2.

Поскольку транспортные сети, как правило, разрежены, мы воспользуемся классом GRAPH, в основу которого положено представление графа в виде списка смежных вер­шин, подобное реализации класса SparceMultiGRAPH (разреженный мультиграф) из про­граммы 20.5. Что более важно, типовые транспортные сети могут иметь параллельные ребра (различной пропускной способности), соединяющие две вершины. Такая ситуация не требует специальных мер с применением класса SparceMultiGRAPH, тем не менее, в случае представления графа в виде матрицы смежности, клиенты должны объединить все параллельные ребра в одно ребро.

В сетях, представленных в главах 20 и 21, мы пришли к соглашению о том, что веса представляются вещественными числами в диапазоне от 0 до 1. В этой главе мы полага­ем, что веса (пропускная способность и величина потоков) суть m-разрядные целые числа (в промежутке от 0 до 2^т-1). Это мы делаем, по меньшей мере, по двум причинам. Во-первых, нам довольно часто придется проверять на равенство различные комбинации ве­сов, и делать это в представлении соответствующих величин в виде вещественных чисел с плавающей точкой может оказаться неудобным. Во-вторых, время выполнения рассмат­риваемых нами алгоритмов может зависеть от относительных значений весов, а параметр M = 2™ дает удобный способ ограничения значений весов. Например, отношение наиболь­шего веса к наименьшему ненулевому весу принимает значение, меньшее М. Использо­вание целочисленных весов есть одна из многочисленных возможных альтернатив (см., например, упражнение 20.8), которые мы можем выбрать при решении такого рода за­дач.

Иногда нам приходится рассматривать ребра с неограниченной пропускной способностью. Это может означать, что мы не соотносим поток с пропускной способностью такого реб­ра, либо мы можем воспользоваться сигнальным значением, которое принимает заведо­мо большее значение, чем величина любого потока.

Программа 22.1 представляет собой клиентскую функцию, которая проверяет, удов­летворяют ли потоки условию равновесия в каждом узле и возвращает значение величи­ны потока, если поток удовлетворяет этому условию. В большинстве случаев мы включаем вызов этой функции в алгоритм вычисления максимального потока в качестве заключи­тельной операции. Несмотря на все доверие, которое мы испытываем к свойству 22.1, характерная для всех программистов параноидная подозрительность нашептывает нам, что мы должны также проверить, равен ли поток, истекающий из истока, потоку, втекающе­му в сток. Возможно, мы благоразумно поступим, если проверим, что ни в одном ребре поток не превосходит по величине пропускную способность этого ребра и что структу­ры данных внутренне непротиворечивы (см. упражнение 22.12).

Часть 5. Алгоритмы на графах

Программа 22.1. Проверка потока и вычисление мощности потока____________________

За счет обращения к функции flow(G, v) вычисляется разность между втекающим и вытекающим потоками в вершине v сети G. Посредством вызова flow(G, s, t) проверяются величины потоков сети из истока (s) в сток (t), при этом 0 возвращается в тех случаях, когда втекающий поток в некотором внутреннем узле не равен вытекающему потоку или если величина какого-либо потока принимает отрицательное значение; в противном случае возвращается величина потока.

template < class Graph, class Edge> class check

public:

static int flow (Graph & G, int v) { int x = 0;

typename Graph:: adjIterator A(G, v); for (Edge* e = A.beg();! A.end(); e = A.nxt())

x += e-> from(v)? e-> flow(): -e-> flow(); return x;

static bool flow (Graph & G, int s, int t)

for (int v = 0; v < G.V(); v++) if ((v! = s) & & (v! = t))

if (flow(G, v)! = 0) return false; int sflow = flow(G, s); if (sflow < 0) return false; if (sflow + flow(G, t)! = 0) return false; return true;