Моделирование графа Max-Flow в Java - PullRequest
Новая
       8

Моделирование графа Max-Flow в Java

0 голосов
/ 21 июня 2009

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

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

1 Ответ

1 голос
/ 22 июня 2009

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

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

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

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

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

...