Как преобразовать сеть предварительного потока с избыточным потоком в сеть потока

Question

Я реализовал первую фазу алгоритма ретрансляции push-меток с наивысшей меткой для максимального потока, но я не смог найти никаких ресурсов о том, как реализовать второй этап, то есть преобразовать push-сеть с предварительным потоком в действительную сеть потока.

Answer 1

Если вам действительно нужен максимальный поток (можно извлечь минимальный срез непосредственно из предварительного потока и использовать его для проверки предварительного потока), тогда я знаю два подхода.

Первый подход описан в оригинальной статье Голдберга - Тарьяна, посвященной алгоритму push-relbel. По сути, второй этап реализован практически точно так же, как и первый. Единственное отличие состоит в том, что источник находится на расстоянии n (а не на приемнике на расстоянии 0). Это приводит к маршрутизации эксцессов обратно к источнику.

Я не уверен, где описан второй подход. Я знаю, что это в реализации Голдберга, на которой основана реализация Boost Graph (см. convert_preflow_to_flow). Концептуально, есть три шага.

1. Пока предварительный поток не станет ациклическим, отмените цикл потока, отправив достаточное количество потока в обратном цикле, чтобы удалить одну из дуг из графика потока.

2. Топологически сортируйте узлы потокового графа от самого дна до самого истока.

3. Для каждого узла в топологическом порядке устраните его избыток, уменьшив поток на входящих дугах (что приводит к соответствующему увеличению избытка узлов, которые еще предстоит обработать).

Практически, шаги 1 и 2 включают поиск в глубину. Наивно, можно было бы перезапустить поиск в глубину для обнаружения цикла после того, как каждый цикл обнаружен и отменен, но можно перематывать поиск в глубину только до точки, где он впервые использовал дугу, отмена которой удалялась, экономя время на добраться до этой точки в поиске снова. Топологический порядок можно получить как побочный продукт поиска, сохранив отдельный обход для шага 2.