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

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

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

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

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

и что мне нужно пересчитать, так это максимальный поток от источника 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) на каждом этапе?

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

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

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

Любая помощь будет оценена. Благодарю.

Источник

2 ответа

Решение

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

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

Источник

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

Источник
Другие вопросы по тегам