Задача о максимальном потоке

[matanga]

Доброго времени суток!
Сейчас я занимаюсь работой, в которой мне стало нужно реализовать алгоритм Форда-Фалкерсона для отыскания максимального потока в графе. Я его реализовал, но начальство сказало, что нужно обязательно проверить его (и не только на маленьких графах, но и на больших тоже). Не подскажете ли вы, может функция для решения такой задачи есть в каком нибудь математическом пакете? Или может у кого то есть написанная программа, которой точно можно доверять?

[juna]

В свое время использовал следующую программу
http://www.ecsocman.edu.ru/db/msg/324869.html

В матпакетах, по-моему, Maple тоже как-то работу с графами поддерживает, но задать большой граф вручную, вводя матрицу смежности - перебор.

[matanga]

жаль, но в предложенном вами пакете матрицу смежности тоже нельзя загрузить....только вручную задавать... что очень не удобно...

[juna]

А по-моему вполне можно. Для тестирования Вам в любом случае придется согласовывать форматы представления данных тестовой и тестируемой программы. Посмотрите примеры с программой - поддерживает расширения .xls, next (что-то похожее на XML).
Правда утверждать точно сейчас я не берусь, поскольку нет Windows под рукой, а wine с этой программой криво работает.

Есть и другие пакеты работы с графами, вот, например, http://common-lisp.net/project/cl-graph/
Кстати посмотрите в интернет-ресурсы на данном форуме, там тоже что-то есть.

[Zealint]

Я большой специалист по задаче о максимальном потоке и автор соответствующей книги.
Во-первых, в системе Maple есть функция MaxFlow (в пакете networks или GraphTheory). Во-вторых, если ваша программа написана на C/C++ я могу проверить её в своей системе на тысяче более-менее приличных тестов (до тысячи вершин в графе). Если Ваша задача - часть большого проекта и Вам нужна глубокая проверка кода, можем договориться отдельно. Пишите в ЛС.

[juna]

Кстати, в версии Maxima 5.20.1 есть пакет по работе с графами (graphs - все основные алгоритмы, включая поиск максимального потока, визуализацию). Задавать графы можно простым текстовым файлом в синтаксисе maxima с расширением mac. Если кому интересно, могу рассказать подробнее.