Графическое моделирование Max-Flow на Java

Question

Я пишу Java-программу для спортивных лиг, которая просматривает текущий набор сыгранных игр каждой команды и расписания следующих игр, а затем на основе этого создаю модель потоковой сети.Идея программы состоит в том, чтобы выяснить, какие команды уже выбыли и не имеют шансов на победу или разделение 1 места с какой-либо другой командой.Проанализировав сеть (применив алгоритм Эдмондса Карпа), я узнаю, выбывает ли команда или нет.Теперь я тоже хочу это смоделировать.Я использую JGraphT в качестве библиотеки графов и, вероятно, буду использовать JGraph для визуализации (причина:как только я создаю объекты JGraphT, я могу просто создавать с их помощью экземпляры объектов JGraph и отображать график).Вчера я также узнал о структуре Юнга, кажется, неплохо.

Основная проблема в том, что я никогда не писал симуляции, и именно здесь мне нужна помощь «Hello World».Когда я говорю «симуляция», я имею в виду, что хочу визуально показать каждую часть выполнения алгоритма, и вот пример сценария:Алгоритм должен находить дополняющие пути, поэтому я хочу показать, когда к дополняющему пути добавляется каждое новое ребро.Пользователь сможет воспроизводить и останавливать анимацию.Я также хочу показать изменения потока во всех краях и тому подобное.Пока что у меня есть работающий алгоритм, но я не знаю, как подойти к моделированию.Должен ли я использовать отдельный поток для выполнения моделирования?Должен ли я написать отдельный класс, который будет выполняться как алгоритм, но с записью состояний, даже не зная настоящего алгоритма (потому что я не хочу прерывать работу реального алгоритма).Должен ли я использовать текущий алгоритм и добавить несколько строк между ними для сохранения состояний выполнения в некоторых структурах данных, которые я мог бы использовать позже для отображения моделирования пользователю?Любые идеи могут помочь..

Answer 1

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

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

• Чтобы взаимодействовать с вашим алгоритмом, определите «атомарные шаги», которые вы хотите различать, например.добавление ребра к пути.Затем вы либо расширяете свой алгоритм, чтобы он также работал поэтапно, либо пишете дополнительный класс, который обертывает алгоритм и предоставляет необходимые процедуры для пошагового выполнения.

• Чтобы анимировать текущее состояние вашего алгоритма, вы должны использовать шаблон наблюдателя, где ваш компонент анимации является наблюдателем и получает уведомление от алгоритма при каждом изменении его состояния, например.к пути было добавлено ребро.Вы также можете описать фактическое изменение состояния, передав намекать (например, краевой объект, добавленный к пути);это может облегчить визуализацию разницы между старым и новым состоянием.

Что касается ваших вопросов по теме:алгоритм, вероятно, должен работать в дополнительном потоке (если только он не очень-очень быстрый), и вы также можете поместить анимацию в дополнительный поток (в любом случае это, вероятно, уже предусмотрено JGraph, просто проверьте документацию или используйте их компоненты в соответствии с рекомендациями).Однако вы должны отметить, что анимация почти наверняка влияет на производительность вашего алгоритма во время выполнения, даже если она является запуск в другом потоке (поскольку уведомление все равно должно быть сделано алгоритмом) - поэтому будьте осторожны с анализом производительности и используйте для таких исследований неанимационную версию.