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

Question

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

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

Эволюция это либо:

• добавление ребра
• увеличение емкости ребра

и мне нужно пересчитать максимальный поток от источника S к узлу назначения края, который был изменен на этом шаге. Например:

                     S                            S  
                     |                            |
                     5                            5
                     |                            |
                     V                            V
                     A---3--->B                   A---5--->B
    adding edge      |        |     increasing    |        |
      B-->D          2        1      A-->B of     2        1
                     |        |     two units     |        |
                     V        V                   V        V
                     C---3--->D                   C---3--->D

                      OUTPUT: 3                    OUTPUT: 5  
                    (maxflow S-D)                (maxflow S-B)

Учитывая очень специфическую природу эволюции в моем графике, какой алгоритм / библиотека будет более быстродействующим? Я имею в виду, учитывая тот факт, что на каждом шаге график почти идентичен предыдущему шагу (за исключением одного ребра), существует ли алгоритм, который может эффективно повторно использовать промежуточные результаты своих предыдущих вычислений?

Я знаю, что тот факт, что пункт назначения каждый раз отличается, делает проблему немного сложнее .... есть идеи о том, как я могу быть лучше, чем O (VE ^ 2) на каждом шаге?

А что, если я тоже рассмотрю эту возможную эволюцию?

• удаление узла (и всех входящих / исходящих ребер в / из этого узла)

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

Любая помощь будет оценена. Спасибо.

Answer 1

Единственная статья, которую я могу найти в общем случае этой проблемы, - это Инкрементальный алгоритм для задачи о максимальном потоке , автор Кумар и Гупта. Он стоит за платным доступом, но основная идея довольно проста. Когда мы увеличим мощность дуги uv , дважды пройдем по графику, чтобы найти все вершины w , которые лежат на пути от s до t на графике с дугами с положительной остаточной емкостью и уф . (Пройдите назад от u и вперед от v .) Начиная с ранее вычисленного потока, запустите Голдберг-Тарьян по этим вершинам.

Чтобы добавить дугу, сначала добавьте ее с нулевой емкостью, а затем увеличьте ее. Кумар-Гупта также рассмотрел вопрос об уменьшении пропускной способности / удалении дуг. Это сложнее; они выталкивают поток из t обратно в v , затем удаляют v , затем снова подталкивают поток вперед.

Answer 2

Есть ли у вас библиотеки, с которыми вы уже работаете?На вашем месте я бы, по крайней мере, нашел бы один, реализующий сетевой симплекс .