4.3 Тестирование программы
Для корректной работы программы на вводимые данные накладываются ограничения. Вес ребер графа должен быть целым числом в переделах от 1 до 65535. Между двумя вершинами графа не может быть более одного ребра. Для поиска максимального потока необходимо указать вершину – исток и вершину – сток. Исток и сток должны быть различными вершинами.
Для тестирования программы в нее был введен граф из аналитической части (рисунок 10).
Рисунок 10 – Окно программы с исходным графом
После нажатия на кнопку «Найти макс. поток» программа произвела расчет максимального потока (рисунок 11).
Рисунок 11 Максимальный поток в графе
Как видно решение аналитическим и программным способом совпадают, значит, программа работает верно.
4.4 Руководство пользователя
Приложение dinic.exe является исполняемым файлом для операционных систем Microsoft Windows XP, Micosoft Windows Vista, Microsoft Windows 7, Microsoft Windows 8. После запуска приложения открывается окно (рисунок 12).
Рисунок 12 – Главное окно программы
в верхней части окна расположена панель инструментов для задания графа (рисунок 13)
Рисунок 13 – Панель инструментов
Инструмент «Переместить вершину» (1) перемещает уже созданную вершину.
Инструмент «Создать вершину» (2) Создает новую вершину. Щелкните по кнопке с красной точкой, а затем на свободном месте формы (рисунок 14). Появится новая вершина.
Рисунок 14 Инструмент «Создать вершину»
Инструмент «Создать ребро» (3) создает ребро между двумя вершинами. Щелкните по кнопке с изображением ребра (3), затем по вершине – началу ребра и по вершине – концу ребра. Появится окно с предложением ввести вес ребра, введите целое число от 1 до 65535, нажмите «Ок». После этого появится окно с вопросом «Ориентированное ребро?» нажмите «Yes» если вы хотите создать ориентированное ребро или «No» в противном случае.
Инструмент «Указать исток» (4) помечает вершину как исток. Щёлкните по кнопке 4, а затем по любой вершине графа. Теперь выбранная вершина является истоком и ее подпись изменилась.
Инструмент «Указать сток» (5) помечает вершину как сток. Щёлкните по кнопке 5, а затем по любой вершине графа. Теперь выбранная вершина будет являться стоком.
Инструмент «Удалить вершину» (6) удаляет выбранную вершину. Щёлкните по кнопке с изображением крестика (6), а затем по любой вершине графа. Вершина и все инцидентные ребра удалятся.
Матрица смежности генерируется автоматически на основе введенного графа, редактировать ее нельзя. В списке ребер отображаются все ребра графа, удалить ребро можно выделив его и нажав на кнопку «Удалить» в нижнем правом углу.
Кнопка «Найти макс. поток» осуществляет поиск в веденном графе максимального потока методом Диница. После того как поток найден выдается окно с величиной максимального потока а также у каждого ребра указывается поток, который по нему проходит.
Меню «Файл» содержит подпункты:
«Сохранить» открывает диалог сохранения графа;
«Открыть» открывает диалог загрузки ранее сохраненного файла с графом;
«Выход» закрывает программу.
Меню «Правка» содержит единственный подпункт «Очистить все», который удаляет весь граф.
Меню «Справка» содержит подпункты: «Инструкция» - открывает окно с подсказками и «О программе» - отображает сведенья о программе.