Спецификация - Wintari/Practice-Cheshuin-Matrosov-Masalykin GitHub Wiki

Спецификация.

1. Постановка задачи:

Разработать визуализатор с графическим интерфейсом алгоритма нахождения мостов в неориентированном графе(модификацией поиска в глубину) на языке Java.

2. Описание интерфейса программы:

  1. Базовое окно программы представляет собой окно размера 850 x 600 пикселей. Окно содержит область меню с двумя кнопками "File" и "Help", две области отображения: одна для визуального отображения графа, вторая для отображения стека работы алгоритма. Внизу окна расположена область управления, состоящая из двух кнопок "Вперед", "Назад" и поля "Шаг". "Вперед" для перехода на следующий шаг алгоритма. "Назад" для перехода на предыдущий шаг алгоритма. Поле шаг отображает номер текущего шага.

  1. При наведении на кнопку меню "File" всплывает выпадающая меню с кнопками "New", "Load", "Save" и "Close". "New" для ввода графа вручную. "Load" для ввода графа из файла. "Save" для сохранения графа в файл. "Close" для закрытия меню.

  1. При наведении на кнопку меню "Help" всплывает выпадающая меню с кнопками "About program" и "Close". "About program" для открытия справки по программе. "Close" для закрытия меню.

  1. При нажатие на кнопку "New" выпадает всплывающее окно, с графическим редактором для введения графа вручную и две кнопки "ОК" и "ОТМЕНА". "ОК" для подтверждения ввода. "ОТМЕНА" для отмены ввода и закрытия окна редактора.

  1. При нажатии на кнопку "Load" выпадает всплывающее окно с текстовой строкой ввода, предложением пользователю ввести путь до файла и кнопакми "ОК" и "ОТМЕНА". "ОК" для подтверждения ввода. "ОТМЕНА" для отмены ввода и закрытия окна.

  1. При нажатии на кнопку "Save" выпадает всплывающее окно с текстовой строкой ввода, предложением пользователю ввести путь до папки и кнопакми "ОК" и "ОТМЕНА". "ОК" для подтверждения ввода. "ОТМЕНА" для отмены ввода и закрытия окна.

  1. При нажатии на кнопку "About program" выпадает всплывающее окно с виджетом для постраничной навигации со страницами: "Информация о программе", "Руководство пользователя", "Информация о разработчиках". В правой стороне окна находится текстовое поле для вывода информации. В нижней правой части окна находится кнопка "Закрыть" для закрытия окна.

3. Формат данных:

  • Граф создаётся с помощью графического редактора, предоставляемого программой.
  • Созданный граф может быть сохранён в файл с расширением .graph с помощью соответствующего пункта меню программы.
  • Граф может быть загружен с помощью соответствующего пункта меню программы из файла с расширением .graph, созданного в данной программе или ином программном обеспечении, обеспечивающем корректный формат файла.
  • Файл с расширением .graph представляет собой текстовый файл, представляющий собой построчное перечисление списка вершин графа с их координатами, а так же списка рёбер графа.

4. Пояснения к задаче:

  • Визуализатор алгоритма – программа, наглядно демонстрирующая работу алгоритма в пошаговом режиме над заданным набором данных.
  • Граф — множество V вершин и набор Е неупорядоченных (неориентированный граф) и упорядоченных (ориентированный граф) пар вершин.
  • Мост — ребро в теории графов, удаление которого увеличивает число компонент связности.
  • Компонента связности графа G (или просто компонента графа G) — максимальный (по включению) связный подграф графа G.
  • Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.