Определение достижимости города в изменяемой системе двусторонних дорог

— 6 ;

— 4;

1. Техническое задание

1.1 Основания для разработки

1.2 Назначение разработки

1.3 Рассмотренные альтернативы

1.4 Стандарты

1.5 Требования пользователя к программному изделию

2. Рабочий проект

2.1 Модули и объекты интерфейса пользователя

2.2 Описание подпрограмм модуля Unit 1

2.3 Описание подпрограмма модуля Unit 2

2.4 Описание подпрограмм модуля Unit 3

2.5 Описание подпрограмм модуля Unit 4

2.6 Тестовые наборы для отладки интерфейса пользователя Заключение Список использованных источников Приложения

Введение

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

Эту проблему целесообразно решать через графы.

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

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

1. Техническое задание

1.1 Основания для разработки

Основанием для разработки программного продукта служит задание по курсовой работе по дисциплине «Программирование на языках высокого уровня» .

1.2 Назначение разработки

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

1.3 Рассмотренные альтернативы

На этапе разработки было предложено 2 среды разработки:

— C++ Builder 6;

— Borland Delphi 7;

При постановке задачи на разработку данного программного изделия была выбрана среда разработки Borland Delphi 7 в силу легкости проектирования пользовательского интерфейса.

1.4 Стандарты

Разработка программной документации и программного изделия должна производиться согласно ГОСТ 19.701−90, ГОСТ 2.304−88. Единая система программной документации.

1.5 Требования пользователя к программному изделию

Входные и выходные данные

Входные данные:

— система дорог и городов, соединенных произвольным образом между собой;

— файл с расширением *.gph, содержащий вносимые пользователем данные.

Выходными данными являются:

— файл с расширением *.gph, в котором сохраняются данные,

— графическое изображение систем дорог и городов, соединенных произвольным образом между собой;

— матрица смежности и матрица достижимости;

Информационная совместимость

Форматы хранения данных должны быть разработаны на основе документов, приведенных 1.5.1 и по своей структуре полностью соответствовать им.

В качестве входных данных программа должна использовать файл формата *.ghp, матрица смежности. Выходными данными должен быть файл формата *.ghp; графическое изображение систем дорог и городов, соединенных произвольным образом между собой.

Программные ограничения, совместимость

Программное изделие должно работать в операционных системах Windows. Для переноса программы не должны требоваться специальные программные и аппаратные средства

Результирующие компоненты изделия

В программное изделие должны входить следующие компоненты:

— хранилище данных (файл с расширением *.gph);

— командный файл для запуска приложения;

— программная документация на изделие.

Носители информации

Программа должна размещаться в виде файла на жестком диске компьютера пользователя.

Требования к надежности

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

Рестарт

В случаях рестарта необходимо запустить на выполнение программу. Данные при рестарте не сохраняются.

Требования к составу и параметрам технических средств

Для работы программного модуля необходимо дисковое пространство не менее 610 Кб, свободная оперативная память в размере не менее 12 Мб, разрешение экрана не менее 1024*768, также микропроцессор 80 486 или выше.

2. Рабочий проект

2.1 Модули и объекты интерфейса пользователя

Пользовательский интерфейс включает в себя следующие компоненты:

— набор кнопок управления;

— набор счетчиков;

— меню программы;

— таблица смежности;

— таблица достижимости;

Листинг программы представлен в приложении А.

Описание внешнего вида формы предоставлено в приложении Г.

2.2 Описание подпрограмм модуля Unit 1

Блок-схемы некоторых главных процедур предоставлены в приложении Б.

Подпрограмма procedure TForm1. Button1Click (Sender: TObject)

Входные данные: указатель на вызывающий объект *Sender.

Выходные данные: нет;

Процесс обработки: флажку reb присваивается значение true, перу присваивается режим перерисовки, xx и yy присваивается значении 0;

Используемые внешние переменные: флажок reb, который позволяет риcовать ребро от одной вершины до другой.

Подпрограмма procedure TForm1. Button2Click (Sender: TObject)

Входные данные: указатель на вызывающий объект *Sender.

Выходные данные: нет;

Процесс обработки: флажку reb присваивается значение false, перу присваивается режим перерисовки, xx и yy присваивается значении -100, флажку ver присваивается значение true ;

Используемые внешние переменные: флажок reb, который позволяет рисовать ребро от одной вершины до другой, если значение true, флажок ver, который позволяет рисовать на форме, если значение true;

Подпрограмма procedure TForm1. Button3Click (Sender: TObject)

Выходные данные: указатель на вызывающий объект *Sender.

Выходные данные: нет;

Процесс обработки: вызывается форма 3, вызывается подпрограмма redrow, которая рисует новые дороги и вызывается подпрограмма Button9. Click, которая перерисовывает всё.

Используемые внешние переменные: нет;

Подпрограмма procedure TForm1.Button4Click(Sender: TObject)

Входные данные: указатель на вызывающий объект *Sender;

Выходные данные: нет;

Процесс обработки: флажку del_ver присваивается значение true;

Используемые внешние переменные: флажок del_ver, который позволяет удалять вершину, если значение true.

Подпрограмма procedure TForm1. Button5Click (Sender: TObject)

Входные данные: запись ver;

Выходные данные: изображение на Image1;

Процесс обработки: города, расположенные на компоненте Image1 выстраиваются по окружности. Подпрограмма redrow перерисовывает изображение.

Используемые внешние переменные: step, которая позволяет выстроить вершины по окружности;

Подпрограмма procedure TForm1. Button6Click (Sender: TObject)

Входные данные: запись ver;

Выходных данных: запись ver;

Процесс обработки: через цикл, каждой вершине присваивается значении 0 и вызывается подпрограмма Button9. Click, которая задает новые координаты x и y каждой вершине через цикл.

Используемые внешние переменные: iсчетчик, ver[i]. x и ver[i]. y — координаты вершин.

Подпрограмма procedure TForm1. Button7Click (Sender: TObject)

Входные данные: файл с расширением *.gph;

Выходные данные: данные матрицы смежности;

Процесс обработки: из файла с расширением *.ghp считываются данные для изображения на компоненте Image1 системы дорог и городов.

Используемые внешние переменные: i, j, kсчетчики, f — имя файла.

Подпрограмма procedure TForm1. Button8Click (Sender: TObject)

Входные данные: данные матрица смежности;

Выходные данные: файл с расширением *.gph и именем f;

Процесс обработки: на диске создается файл с расширением *.gph, в который через цикл записывается содержание матрицы смежности.

Используемые внешние переменные: i, j, k — счетчики, f — имя файла.

Подпрограмма procedure TForm1. Button9Click (Sender: TObject)

Входные данные: запись ver;

Выходные данные: изображение на Image1;

Процесс обработки: устанавливается step, присваивается переменной ns количество городов, если есть города, у которых координаты равны 0 они изменяются на другие, не нулевые, и вызывается подпрограмма перерисовки.

Используемые внешние переменные: step — шаг, ns — количество городов, i — счетчик, vet[i] - запись вершины с её координатами.

Подпрограмма procedure TForm1. Button10Click (Sender: TObject)

Входные данные: указатель на вызывающий объект *Sender;

Выходные данные: нет;

Процесс обработки: ячейки матрицы смежности обнуляются через счетчик, после чего вызывается подпрограмма перерисовки Button9.Click.

Использование внешних переменных: i — счетчик, n — количество городов.

Подпрограмма procedure TForm1. Button11Click (Sender: TObject)

Входные данные: данные с матрицы смежности, данные с 2-х счетчиков на форме;

Выходные данные: данные матрицы достижимости;

Процесс обработки: через цикл с помощью матрицы смежности создается матрица достижимости, после чего через цикл идет изменение матрицы достижимости по алгоритму Флойда. После этого идёт проверка через условие на достижимость из заданного города, А в заданный город В. Результат выводится на форму в форме текста.

Используемые переменные: i, j, k — счетчики, dost — двумерный динамический массив.

Подпрограмма procedure TForm1. Button12Click (Sender: TObject)

Входные данные: данные с матрицы смежности, данные с матрицы достижимости, данные с счетчика на форме;

Выходные данные: графическое решение и текстовая информация, матрица достижимости.

Процесс обработки: вызывается подпрограмма Matrix, которая составляет матрицу достижимости по матрице смежности. После выполнения подпрограммы Matrix, переменным doroga и vver присваиваются значения, которые показывают количество дорог, которые нужно достроить. Далее выполняется цикл на проверку матрицы достижимости, если матрица содержит во всех ячейках 1, то выводится сообщение «Все города достижимы», после чего начинается цикл, в котором выполняется проверка на добавление новых дорог.

Используемые переменные: i, j, kсчетчики, dost — двумерный динамический массив, dorog, vver — количества дорог, result — флажок на графическое решение.

Подпрограмма function Matrix;

Входные данные: переменная doroga, переменная vver, матрица смежности.

Выходные данные: матрица достижимости, переменные doroga, vver.

Процесс обработки: подпрограмма обрабатывает данные с матрицы смежности, подсчитывает количество нужных дорог.

Используемые внешние переменные: doroga, vver — количество дорог, dost — двумерный динамический массив.

Подпрограмма function findver (x, y, rad:integer):Integer;

Входные данные: x, y, rad;

Выходные данные: findver;

Процесс обработки: подпрограмма находит номер вершины по координатам x и y и радиусу, после чего выдает её номер.

Используемые внешние переменные: x, y — координаты, rad — радиус окружности.

Подпрограмма procedure TForm1. redrow;

Входные данные: количество городов, запись ver;

Выходные данные: изображение на компоненте Image1;

Процесс обработки: подпрограмма перерисовывает изображение на компоненте Image1;

Используемые внешние переменные: i, j — счетчики;

Подпрограмма procedure TForm1. FormCreate (Sender: TObject);

Входные данные: указатель на вызывающий объект *Sender;

Выходные данные: количество городов;

Процесс обработки: переменным pos и n присваивается значение 0;

Используемые внешние переменные: нет;

Подпрограмма procedure TForm1.Image1MouseMove(Sender: TObject; Shift: TShiftState; X,Y: Integer);

Входные данные: координаты xx и yy, флажки ver, reb2;

Выходные данные: изображение на компоненте Image1;

Процесс обработки: выполнение подпрограммы зависит от значений флажков ver и reb2, если они true, то подпрограмма по флажку ver рисует эллипс с координатами х, у на компоненте Image1, а по флажку reb2 подпрограмма рисует ребро (дорогу) до заданного города.

Используемые внешние переменные: нет;

Подпрограмма procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer)

Входные данные: флажки del_ver, reb, reb2, ver; координаты клика x, y;

Выходные данные: изображение на компоненте Image1;

Процесс обработки: выполнение подпрограммы зависит от значений флажков del_ver, reb, reb2, ver.

Если del_ver true, то подпрограмма удаляет вершину, с заданными координатами и значение флажков ver, reb, reb2, del_ver изменяет на false, а также убирает на -1 строчку и столбец в матрице смежности и матрице достижимости, соответствующие данной вершине.

Если флажок reb true, то подпрограмма рисует линию от одной вершины до другой. Если другая вершина указана не указана, то значение reb становится false.

Если reb2 true, то reb false, reb2 false и строится линия от одной вершины до другой и в матрицу смежности в ячейке ставится значение «1», указывающее на ребро между этими городами.

Если ver true, то значение городов увеличивается на +1, запоминаются координаты в структуру ver — запись и в матрице смежности и достижимости добавляется строчка и столбец с соответствующим номером города.

Используемые внешние переменные: xx, yy — координаты с компонента Image1, i, j, k, i2 — счетчики;

Подпрограмма procedure TForm1. N5Click (Sender: TObject)

Входные данные: нет;

Выходные данные: нет;

Процесс обработки: выход из программы;

Используемые внешние переменные: нет;

Подпрограмма procedure TForm1.N2Click(Sender: TObject);

Входные данные: нет;

Выходные данные: нет;

Процесс обработки: вызов подпрограммы Button7. Click;

Используемые внешние переменные: нет;

Подпрограмма procedure TForm1.N3Click(Sender: TObject);

Входные данные: нет;

Выходные данные: нет;

Процесс обработки: вызов подпрограммы Button8. Click;

Используемые внешние переменные: нет;

Подпрограмма procedure TForm1.N4Click(Sender: TObject);

Входные данные: нет;

Выходные данные: нет;

Процесс обработки: создание нового графа;

Используемые внешние переменные: i, j — счетчики ;

Подпрограмма procedure TForm1. StringGrid3KeyPress (Sender: TObject; var Key: Char);

Входные данные: числа;

Выходные данные: нет;

Процесс обработки: подпрограмма запрещает вводить числа на главной диагонали в матрице достижимости, а так же ограничивает ввод чисел, кроме 0 и 1 и использование клавиш, кроме Backspace.

Используемые внешние переменные: нет;

Подпрограмма procedure TForm1.Edit1Change(Sender: TObject)

Входные данные: число городов;

Выходные данные: данные матрицы смежности, изображение на компоненте Image1;

Процесс обработки: создается матрица смежности и матрица достижимости размером [pos*pos], где pos — количество городов, а также заполнение ячеек матрицы смежности и матрицы достижимости значением «0».

Используемые внешние переменные: pos, n — количество городов, i, j-счетчики.

Подпрограмма procedure TForm1.Image1MouseDown (Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer);

Входные данные: координаты места клика левой клавишей мыши X и Y ;

Выходные данные: изображение контекстного меню на компоненте Image1;

Процесс обработки: если нажата не левая клавиша мыши, то показать контекстное меню.

Используемые внешние переменные: нет;

Подпрограмма procedure TForm1.N7Click(Sender: TObject);

Входные данные: нет;

Выходные данные: нет;

Процесс обработки: вызов подпрограммы Button2. Click;

Используемые внешние переменные: нет;

Подпрограмма procedure TForm1.N8Click(Sender: TObject);

Входные данные: нет;

Выходные данные: нет;

Процесс обработки: вызов подпрограммы Button1. Click;

Используемые внешние переменные: нет;

Подпрограмма procedure TForm1.N9Click(Sender: TObject);

Входные данные: нет;

Выходные данные: нет;

Процесс обработки: вызов подпрограммы Button4. Click;

Используемые внешние переменные: нет;

Подпрограмма procedure TForm1.StringGrid3KeyUp(Sender: TObject; var Key: Word; Shift: TShiftState);

Входные данные: данные с матрицы смежности;

Входные данные; изображение на компоненте Image1;

Процесс обработки: подпрограмма вызывает подпрограмму redrow.

Используемые внешние переменные: нет;

Подпрограмма procedure TForm1.vvChange(Sender: TObject);

Входные данные: данные с счетчика vv. Value;

Входные данные: нет;

Процесс обработки: подпрограмма делает ограничение на ввод в счетчик vv. Value значение больше значения количества городов.

Используемые внешние переменные: pos — количество городов.

Подпрограмма procedure TForm1. IsvChange (Sender: TObject);

Входные данные: данные с счетчика Isv. Value;

Входные данные: нет;

Процесс обработки: подпрограмма делает ограничение на ввод в счетчик Isv. Value значение больше значения количества городов.

Используемые внешние переменные: pos — количество городов.

Подпрограмма procedure TForm1. IzverChange (Sender: TObject);

Входные данные: данные с счетчика Izver. Value;

Входные данные: нет;

Процесс обработки: подпрограмма делает ограничение на ввод в счетчик Izver. Value значение больше значения количества городов.

Используемые внешние переменные: pos — количество городов.

Подпрограмма procedure TForm1. N6Click (Sender: TObject);

Входные данные: нет;

Выходные данные: нет;

Процесс обработки: вызов формы 2;

Используемые внешние переменные: нет;

Подпрограмма procedure redrow_result_true;

Входные данные: количество городов, запись ver;

Выходные данные: изображение на компоненте Image1;

Процесс обработки: аналогичен подпрограмме redrow за исключением выделения ответа другим цветом. В данном случае зеленым, который показывает достижимость всех городов из заданного города А.

Используемые внешние переменные: i, j — счетчики.

Подпрограмма procedure redrow_result_false;

Входные данные: количество городов, запись ver;

Выходные данные: изображение на компоненте Image1;

Процесс обработки: аналогичен подпрограмме redrow за исключением выделения ответа другим цветом. В данном случае синим, который показывает не достижимость некоторых городов из заданного города А.

Используемые внешние переменные: i, j — счетчики.

Подпрограмма procedure TForm1. StringGrid3Set (Sender: TObject; ACol, ARow: Integer; const Value: String);

Входные данные: нет;

Выходные данные: нет;

Процесс обработки: подпрограмма выполняет заполнение матрицы смежности симметрично относительно главной диагонали.

Используемые внешние переменные: нет;

Подпрограмма procedure Dostizhimost(izver:integer);

Входные данные: номер города;

Выходные данные: текстовое сообщение о достижимости или не достижимости до всех городов из заданного города А;

Процесс обработки: подпрограмма строит матрицу достижимости по матрице смежности, делает проверку на достижимость до всех городов из заданного города, А через цикл и выводит сообщение с соответствующим результатом.

Используемые внешние переменные: dost — двумерный динамический массив, или матрица достижимости; i, j, k — счетчики.

2.3 Описание подпрограмма модуля Unit 2

Подпрограмма procedure TForm2. Label1Click (Sender: TObject)

Входных данных: нет;

Выходных данных: нет;

Процесс обработки: подпрограмма выполняет закрытие формы 2 по клику на содержимое формы;

Используемые внешние переменные: нет;

2.4 Описание подпрограмм модуля Unit 3

Подпрограмма procedure TForm3. Button1Click (Sender: TObject);

Входные данные: нет;

Выходные данные: нет;

Процесс обработки: закрытие формы;

Используемые внешние переменные: нет;

2.5 Описание подпрограмм модуля Unit 4

Подпрограмма procedure TForm4. Button1Click (Sender: TObject)

Входные данные: нет;

Выходные данные: нет;

Процесс обработки: подпрограмма выполняет закрытие заставочной формы при нажатии на клавишу «ОК».

Используемые внешние переменные: нет.

2.6 Тестовые наборы для отладки интерфейса пользователя

Для отладки интерфейса разработаны следующие тестовые наборы:

1. Случай использования: запуск программы.

Предусловие: открыта заставочная форма.

Тестовый случай: нажатие пользователем на кнопку «ОК»;

Ожидаемый результат: закрытие заставочной формы, появление окна главной формы. (Приложение В, рисунок 1)

2. Случай использования: добавление нового города на компонент Image1.

Предусловие: открыта главная форма;

Тестовый случай: нажатие пользователем на кнопку «Разместить город 1» и нажатие левой клавишей мыши на область компонента Image1;

Ожидаемый результат: на компоненте Image1 появится эллипс с номером города в центре желтого цвета. (Приложение Г, рисунок 2)

3. Случай использования: добавление дороги между городами;

Предусловие: открыта головная форма, имеются 2 города, не соединенных между собой дорогой.

Тестовый случай: нажатие пользователем на кнопку «Добавить дорогу» на главной форме или же в контекстном меню, после последующее нажатие на город 1 и город 2.

Ожидаемый результат: на компоненте Image1 между двумя городами появится линия, на концах который расположено по 4 красных маленьких эллипса разного диаметра. (Приложение Г, рисунок 3)

4. Случай использования: удаление города.

Предусловие: открыта головная форма, имеется хотя бы 2 города на компоненте Image1.

Тестовый случай: нажатие пользователем на кнопку «Удалить город» на главной форме или же через контекстное меню.

Ожидаемый результат: на компоненте Image1 исчезнет изображение города, на который было произведено нажатие левой клавишей мыши, также уменьшение матрицы смежности и достижимости на -1 строку и столбец и удаление дорог, если они были от этого города. (Приложение Г, рисунок 4)

5. Случай использования: просмотр задания;

Предусловие: открыта главная форма;

Тестовый случай: нажатие пользователем на кнопку «Задание»;

Ожидаемый результат: появление формы, с содержанием задания, которое выполняет данная программа. (Приложение Г, рисунок 5)

6. Случай использования: проверка на достижимость из заданного города, А в заданный город В;

Предусловие: задана система дорог и координат, указан начальный и конечный город проверки.

Тестовый случай: нажатие пользователем на клавишу «Проверить достижимость»;

Ожидаемый результат: вывод сообщения на главную форму о достижимости или не достижимости из указанного города, А в указанный город В. (Приложение Г, рисунок 6)

7. Случай использования: достижимости до всех городов из заданного города А.

Предусловие: задана система дорог и городов, заданный город А.

Тестовый случай: нажатие пользователя на кнопку «Проверить достижимость»;

Ожидаемый результат: вывод результата на главную форму в виде графического решения с цветом дорог:

— если дороги зеленые — все города достижимы из города А;

— если дороги желтые — не все города достижимы из города А; (Приложение Г, рисунок 7(а, б))

8. Случай использования: задание определенного количества городов через счетчик.

Предусловие: на компоненте Image1 имеется хотя бы 1 город.

Тестовый случай: увеличение или уменьшение счетчика количества городов.

Ожидаемый результат: на компоненте Image1 появится заданное количество город. (Приложение Г, рисунок 8)

9. Случай использования: загрузка графа из файла.

Предусловие: имеется файл формата *.gph с данными матрицы смежности.

Тестовый случай: нажатие пользователя на кнопку «Загрузить файл графа с файла» и указание файла через проводник.

Ожидаемый результат: заполнение матрицы смежности по данным из файла и графическое отображение городов на компоненте Image1. (Приложение Г, рисунок 9)

10. Случай использования: сохранения текущего графа в файл.

Предусловие: имеется система дорог и городов.

Тестовый случай: нажатие пользователя на кнопку «Сохранить текущий граф в файл», указание места сохранения через проводник и имя файла.

Ожидаемый результат: на диске появится файл с именем, который задал пользователь и форматом *.gph, содержащий данные матрицы смежности. (Приложение Г, рисунок 10)

11. Случай использования: удаление всех дорог;

Предусловие: имеется система дорог и городов.

Тестовый случай: нажатие пользователя на кнопку «Удалить все дороги»;

Ожидаемый результат: в имеющейся системе дорог и городов будут удалены все дороги. (Приложение Г, рисунок 11)

Заключение

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

Список использованных источников

1. Круз Р. Л. Структуры данных и проектирование программ / Р. Л. Круз; пер. с англ. — М.: БИНОМ. Лаборатория знаний, 2008 — 765 с.: ил. — (Программисту).

2. Кузнецов А. В., Сакович В. А., Холод Н. И. Высшая математика. Математическое программирование. — Минск: Высшая школа, 2010 г.- С. 792.

3. Оре О. Теория Графов. — М.: Наука, 2010 г.

4. Белов. Теория Графов. — М.: Наука, 2011 г.

5. Нефедов В. Н., Осипова В. А. Курс дискретной математики. — М.: МАИ, 2010 г.

Приложение А

Листинг программы

дорога город достижимость интерфейс

unit Unit1; // модуль формы 1 «Проверка достижимости из города, А до всех других дорог в изменяемой системе дорог»

interface

uses // стандартные модули

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids, ExtCtrls, ComCtrls, Menus, ExtDlgs, Spin, XPMan;

type

TForm1 = class (TForm) // типы объектов графического интерфейса и процедуры модуля

Image1: TImage;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N5: TMenuItem;

OpenDialog1: TOpenDialog;

SaveDialog1: TSaveDialog;

N4: TMenuItem;

PopupMenu1: TPopupMenu;

N7: TMenuItem;

N8: TMenuItem;

N9: TMenuItem;

GroupBox1: TGroupBox;

PageControl1: TPageControl;

TabSheet3: TTabSheet;

Button10: TButton;

Button9: TButton;

Button5: TButton;

Button6: TButton;

GroupBox2: TGroupBox;

Button2: TButton;

Button1: TButton;

Button4: TButton;

XPManifest1: TXPManifest;

GroupBox3: TGroupBox;

Label2: TLabel;

Label3: TLabel;

vv: TSpinEdit;

Label4: TLabel;

isv: TSpinEdit;

Button11: TButton;

N6: TMenuItem;

Label5: TLabel;

TabSheet1: TTabSheet;

StringGrid1: TStringGrid;

Button3: TButton;

Button12: TButton;

Izver: TSpinEdit;

Label6: TLabel;

TabSheet2: TTabSheet;

Label1: TLabel;

StringGrid3: TStringGrid;

Edit1: TSpinEdit;

Button7: TButton;

Button8: TButton;

procedure FormCreate (Sender: TObject);

procedure Button2Click (Sender: TObject);

procedure Image1MouseMove (Sender: TObject; Shift: TShiftState; X,

Y: Integer);

procedure Image1MouseUp (Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure redrow;

procedure Button1Click (Sender: TObject);

procedure Button9Click (Sender: TObject);

procedure Button5Click (Sender: TObject);

procedure Button4Click (Sender: TObject);

procedure Button10Click (Sender: TObject);

procedure N5Click (Sender: TObject);

procedure N2Click (Sender: TObject);

procedure N3Click (Sender: TObject);

procedure N4Click (Sender: TObject);

procedure StringGrid3KeyPress (Sender: TObject; var Key: Char);

procedure Edit1Change (Sender: TObject);

procedure Image1MouseDown (Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure N7Click (Sender: TObject);

procedure N8Click (Sender: TObject);

procedure N9Click (Sender: TObject);

procedure Button6Click (Sender: TObject);

procedure Button7Click (Sender: TObject);

procedure Button8Click (Sender: TObject);

procedure N10Click (Sender: TObject);

procedure Button11Click (Sender: TObject);

procedure StringGrid3KeyUp (Sender: TObject; var Key: Word;

Shift: TShiftState);

procedure vvChange (Sender: TObject);

procedure isvChange (Sender: TObject);

procedure N6Click (Sender: TObject);

procedure StringGrid3Set (Sender: TObject; ACol,

ARow: Integer; const Value: String);

procedure Button3Click (Sender: TObject);

procedure Button12Click (Sender: TObject);

procedure IzverChange (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

vv = record

x, y: Integer;

num:Integer;

end;

var

Form1: TForm1;

pos, pos2: Integer;

n, xx, yy, xb, yb, ugol, doroga, vver, i, j, k: Integer;

ver, reb, reb2, del_ver, result: Boolean;

vers:array[1.100] of vv;

dost :array of array of integer;

implementation

uses Math, Unit2, Unit3, Unit4;

{$R *.dfm}

function findver (x, y, rad:integer):Integer; // находит вершину в графе на которую указали сейчас.

var i: Integer;

begin

findver:=0;

for i:=1 to pos do begin

if (x>vers[i]. x-rad) and (xvers[i]. y-rad) and (y

findver:=i;

end;

end;

procedure Matrix; //алгоритм Флойда.

begin

SetLength (dost, pos, pos);

for i:=1 to pos do

for j:=1 to pos do

if Form1. StringGrid3.Cells[j, i]<>'0' then

dost[i-1,j-1]: =1 else dost[i-1,j-1]: =0;

for i:=1 to pos do

for j:=1 to pos do

if dost[j-1,i-1]=0 then doroga:=doroga+1;

for k:=0 to pos-1 do // ищем можно ли сократить путь через третью вершину К

for i:=0 to pos-1 do

for j:=0 to pos-1 do

dost[i, j]: = dost[i, j] or (dost[i, k] and dost[k, j]) ;

for i:=1 to pos do

for j:=1 to pos do

begin

if dost[j-1,i-1]=0 then vver:=vver+1;

Form1.StringGrid1.Cells[j, i]: =inttostr (dost[i-1,j-1]);

end;

end;

procedure TForm1. redrow; // перерисовка изображения графа на картинке

var i, j: Integer; // вспомогательные переменные

begin

if pos =0 then exit;

n:=stringgrid3.ColCount-1;

Image1.Canvas.Pen.Mode := pmCopy;

Image1.Canvas.Brush.Color := clWhite;

Image1.Canvas.Rectangle (0,0,Image1.Width, Image1. Height); // очистка канваса без мигания

Image1.Canvas.Pen.Width:=1;

for i:=1 to n do // рисуем дуги

for j:=1 to n do

if strtoint (StringGrid3.Cells[i, j])>0 then

begin

Image1.Canvas.MoveTo (vers[i]. x, vers[i].y);

Image1.Canvas.lineTo (vers[j].x, vers[j].y);

/// красная точка направления

Image1.Canvas.pen.Color := clRed;

Image1.Canvas.Brush.Color := clRed;

Image1.Canvas.ellipse (round (vers[j]. x+(vers[i].xvers[j]. x)*0.9)-4,round (vers[j].y+(vers[i].yvers[j]. y)*0.9)-4,

round (vers[j].x+(vers[i].xvers[j]. x)*0.9)+4,round (vers[j].y+(vers[i].yvers[j]. y)*0.9)+4);

Image1.Canvas.ellipse (round (vers[j].x+(vers[i].xvers[j]. x)*0.93)-3,round (vers[j].y+(vers[i].yvers[j]. y)*0.93)-3,

round (vers[j].x+(vers[i].xvers[j]. x)*0.93)+3,round (vers[j].y+(vers[i].yvers[j]. y)*0.93)+3);

Image1.Canvas.ellipse (round (vers[j].x+(vers[i].xvers[j]. x)*0.95)-2,round (vers[j].y+(vers[i].yvers[j]. y)*0.95)-2,

round (vers[j].x+(vers[i].xvers[j]. x)*0.95)+2,round (vers[j].y+(vers[i].yvers[j]. y)*0.95)+2);

Image1.Canvas.ellipse (round (vers[j].x+(vers[i].xvers[j]. x)*0.97)-1,round (vers[].y+(vers[i].yvers[j]. y)*0.97)-1,

round (vers[j].x+(vers[i].xvers[j]. x)*0.97)+1,round (vers[j].y+(vers[i].yvers[j]. y)*0.97)+1);

Image1.Canvas.Pen.Color := clBlack;

Image1.Canvas.Brush.Color := clWhite;

Image1.Canvas.pen.Style:= psSolid ;

end;

for i:=1 to n do

begin // вершины — кружки с номером вершины

Image1.Canvas.Brush.Color:=RGB (234,228,36);

Image1.Canvas.Ellipse (vers[i]. x-10,vers[i].y-10,vers[i].x+10,vers[i].y+10);

Image1.Canvas.TextOut (vers[i].x-3,vers[i].y-6,inttostr (i));

end;

end;

procedure TForm1. FormCreate (Sender: TObject);

begin

pos:=0;

n:=0;

result:=false;

end;

procedure TForm1. Button2Click (Sender: TObject);

begin

reb:=false;

xx:=-100;

yy:=-100;

Image1.Canvas.Pen.Mode := pmNotXor;

ver:= True;

end;

procedure TForm1. Image1MouseMove (Sender: TObject; Shift: TShiftState; X,

Y: Integer);

begin

if ver then

begin

Image1.Canvas.Ellipse (xx-10,yy-10,xx+10,yy+10);

xx:=x;

yy:=y;

Image1.Canvas.Ellipse (x-10,y-10,x+10,y+10);

end;

if reb2 then

begin

Image1.Canvas.MoveTo (xb, yb);

Image1.Canvas.LineTo (xx, yy);

xx:=x;

yy:=y;

Image1.Canvas.MoveTo (xb, yb);

Image1.Canvas.LineTo (x, y);

end

else

begin

xb:=x;

yb:=y;

end;

end;

procedure TForm1. Image1MouseUp (Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

var j, k, i, i2, xx, yy: integer;

begin

If del_ver then

begin // удаление вершины

//найти удаляемую вершину

k:=findver (x, y,10); //удалить все ребра которые входят и выходят их этой вершины

ver:= false;

reb := false;

reb2:=false;

del_ver:=false;

if k=0 then exit;

for i:=1 to StringGrid3. ColCount-1 do

if i>=k then vers[i]: =vers[i+1];

// будем копировать на единицу назад столбцы, если они стоят правее удаляемой вершины

for i:=1 to StringGrid3. RowCount-1 do

for j:=1 to StringGrid3. RowCount-1 do

if j>=k then StringGrid3. Cells[i, j]: =StringGrid3.cells[i, j+1];

for j:=1 to StringGrid3. RowCount-1 do

for i:=1 to StringGrid3. RowCount-1 do

if i>=k then StringGrid3. Cells[i, j]: =StringGrid3.cells[i+1,j];

pos:=pos-1;

edit1.Value:=edit1.Value-1;

StringGrid3.cells[0,0]:='*';

redrow;

Image1.Canvas.Pen.Mode := pmCopy;

Button2.Caption:= 'Разместить город '+IntToStr (pos+1);

end;

If ver then

begin

inc (pos);

vers[pos]. x:=x;

vers[pos].y:=y;

xx:=-100;yy:=-100;

vers[pos].num:=pos;

ver:=False;

Button2.Caption:= 'Разместить город '+IntToStr (pos+1);

If pos>1 then

begin

StringGrid3.ColCount:=StringGrid3.ColCount+1;

StringGrid3.RowCount:=StringGrid3.RowCount+1;

Edit1.Value :=pos;

end;

for i:=1 to edit1. value+1 do

begin // рисуем новые номера вершин после изм. количества вершин

StringGrid3.Cells[i, 0]: = inttostr (i);

StringGrid3.Cells[0,i]: = inttostr (i);

end;

for i:=1 to edit1. value do

begin

for i2:=1 to edit1. value do

begin

if StringGrid3. Cells[i2,i]='' then

StringGrid3.cells[i2,i]: ='0';

end;

end;

redrow;// перерисуем что получилось после добавления вершины

end;

if reb2 then begin

try

reb:=false;

reb2:=false;

xx:=0;

yy:=0;

i:=findver (x, y,10);

If i <>0 then

begin // если указали все верно из одного кружка вершины в другой, то добавим в матрицу смежности запись

StringGrid3.Cells[findver (x, y,10), findver (xb, yb, 10)]: ='1';

StringGrid3.Cells[findver (xb, yb, 10), findver (x, y,10)]:='1'

end;

StringGrid3.cells[0,0]:='*';

redrow;

except;

redrow;

end;

end;

if reb then

begin

try

xb:=x;

yb:=y;

xx:=x;

yy:=y;

reb2:=True;

Image1.Canvas.MoveTo (0,0);

Image1.Canvas.LineTo (x, y);

i:=findver (x, y,10);

If i <>0 then

begin

inc (n);

StringGrid3.Cells[pos2,0]: =inttostr (i);

i:=findver (x, y,10); // найти к какой вершине мы сейчас добавляем ребро

end;

except;

reb:=false; // неудачная попытка добавить ребро

end;

end;

end;

procedure TForm1. Button1Click (Sender: TObject);

begin

xx:=0;

yy:=0;

Image1.Canvas.Pen.Mode := pmNotXor;

reb:=true;

end;

procedure TForm1. Button9Click (Sender: TObject);

var ns, ms, x, y, i, j: Integer;

step:real;

begin

step:= 4*3.14/ edit1. value;

ns:=(edit1.value);

for i:=1 to edit1. value do

if ((vers[i]. x=0) or (vers[i]. y=0)) then

begin

while ((findver (x, y,20)>0) or (x<50) or ((y+50)>image1.Height) or (y<50) or ((x+50)>image1.Width)) do

begin

ns:=image1.Width-random (image1.Width*2);

ms:=image1.Height-random (image1.Height*2);

x:=ns+ 300+ trunc (cos (i*step+ms+ugol/100)*100);

y:=ms+ 150+ trunc (sin (i*step+ns+ugol/100)*100);

end;

vers[i]. x:=x; vers[i]. y:=y;

end;

redrow;

end;

procedure TForm1. Button5Click (Sender: TObject);

var x, y: Integer;

i:Integer;

step:real;

begin

step:=2*3.14/ edit1. value;

for i:=1 to edit1. value do

begin

vers[i]. x:= 300+ trunc (cos (i*step+ugol/100)*100);

vers[i]. y:= 150+ trunc (sin (i*step+ugol/100)*100);

end;

redrow;

end;

procedure TForm1. Button4Click (Sender: TObject);

begin

del_ver:=true;

end;

procedure TForm1. Button10Click (Sender: TObject);

var i, j: Integer;

begin

// очистка грида

n:=edit1.Value;

pos:=edit1.Value;

for i:=1 to n do

for j:=1 to n do

StringGrid3.cells[j, i]: ='0';

Button9.Click;

end;

procedure TForm1. N5Click (Sender: TObject);

begin

Halt (0);

end;

procedure TForm1. N2Click (Sender: TObject);

begin

button7.Click; // вызов открытия из меню

end;

procedure TForm1. N3Click (Sender: TObject);

begin

button8.click; // вызов сохранения их меню

end;

procedure TForm1. N4Click (Sender: TObject); // новый граф

var i, j: integer;

begin

Button10.click; // вначале очистка грида

edit1.Value:=1; // убираем лишние строки и столбцы

label5.Caption:=' ';

Button9.click; // обновляем картинку

Button2.Caption:= 'Разместить город '+IntToStr (pos+1);

for i:=0 to pos-1 do

for j:=0 to pos-1 do

begin

StringGrid1.Cells[i, j]: ='0';

StringGrid3.Cells[i, j]:='0';

end;

end;

procedure TForm1. StringGrid3KeyPress (Sender: TObject; var Key: Char);

begin

if (Sender as TStringGrid).col=(Sender as TStringGrid).row // нельзя ставить на главное диагонали

then key := Chr (0);

case Key of

#8,'1','0':; // цифры и клавиша

else key := Chr (0); // остальные символы запрещены

end;

end;

procedure TForm1. Edit1Change (Sender: TObject);

var i, j: integer;

begin

try

StringGrid3.ColCount:=edit1.Value+1;// при изменении спинбокса нужно перерисовать матрицу

StringGrid3.RowCount:=edit1.Value+1;

StringGrid1.ColCount:=edit1.Value+1;// при изменении спинбокса нужно перерисовать матрицу

StringGrid1.RowCount:=edit1.Value+1;

n:=edit1.Value;

pos:=edit1.Value;

// надписи о номерах

for i:=1 to n+1 do

begin

StringGrid3.Cells[i, 0]: = inttostr (i);

StringGrid3.Cells[0,i]: = inttostr (i);

end;

for i:=1 to n+1 do

begin

StringGrid1.Cells[i, 0]: = inttostr (i);

StringGrid1.Cells[0,i]: = inttostr (i);

end;

for i:=1 to n do

for j:=1 to n do

begin

if StringGrid3. Cells[j, i]='' then

StringGrid3.cells[j, i]: ='0';

end;

for i:=1 to n do

for j:=1 to n do

begin

if StringGrid1. Cells[j, i]='' then

StringGrid1.cells[j, i]: ='0';

end;

button9.Click; // обновить картинку

Button2.Caption:= 'Разместить город '+IntToStr (pos+1);

except;

end;

end;

procedure TForm1. Image1MouseDown (Sender: TObject; Button: TMouseButton; // по нажатию на имаже

Shift: TShiftState; X, Y: Integer);

begin

if button <>mbLeft then // если нажали левой кнопкой

PopupMenu1.Popup (Mouse.CursorPos.X, Mouse.CursorPos.y); // показать контекстное меню

end;

procedure TForm1. N7Click (Sender: TObject);

begin

Button2.Click ;

end;

procedure TForm1. N8Click (Sender: TObject);

begin

Button1.Click ;

end;

procedure TForm1. N9Click (Sender: TObject);

begin

Button4.Click;

end;

procedure TForm1. Button6Click (Sender: TObject);

var i: integer;

begin

for i:=1 to edit1. value do

begin

vers[i]. x:=0; vers[i]. y:=0;

end;

Button9.Click ;

end;

procedure TForm1. Button7Click (Sender: TObject);

var

f: TextFile;

iTmp, i, k: Integer;

strTemp: String;

begin

if (not OpenDialog1. Execute ()) then exit;

AssignFile (f, OpenDialog1. FileName);

Reset (f);

with StringGrid3 do

begin

Readln (f, iTmp);

ColCount := iTmp;

Readln (f, iTmp);

RowCount := iTmp;

edit1.Value:=ColCount-1;

for i := 0 to ColCount — 1 do

for k := 0 to RowCount — 1 do

begin

Readln (f, strTemp);

Cells[i, k] := strTemp;

end;

Label5.Caption:='';

end;

CloseFile (f);

if StringGrid3. ColCount>10 then button6. Click else button5. Click;// обновим изображение

Button2.Caption:= 'Разместить город '+IntToStr (pos+1);

end;

procedure TForm1. Button8Click (Sender: TObject);

var

f: TextFile;

i, k: Integer;

begin

if (not SaveDialog1. Execute ()) then exit; // проверяем открылся ли диалог загрузки

AssignFile (f, SaveDialog1. FileName);

Rewrite (f);

with StringGrid3 do

begin

Writeln (f, ColCount);

Writeln (f, RowCount);

for i := 0 to ColCount — 1 do

for k := 0 to RowCount — 1 do

Writeln (F, Cells[i, k]);

end;

CloseFile (F);

end;

procedure TForm1. N10Click (Sender: TObject);

begin

button11.Click; // вызов решения гамильтонова цикла

end;

procedure TForm1. Button11Click (Sender: TObject);

var i, j, k: integer;

dost :array of array of integer;

begin

if pos<2 then exit;

SetLength (dost, pos, pos);

for i:=1 to pos do

for j:=1 to pos do

if StringGrid3. Cells[j, i]<>'0' then

dost[i-1,j-1]: =1 else dost[i-1,j-1]: =0;

for k:=0 to pos-1 do // ищем можно ли сократить путь через третью вершину К

for i:=0 to pos-1 do

for j:=0 to pos-1 do

dost[i, j]: = dost[i, j] or (dost[i, k] and dost[k, j]) ;

if dost[ isv. Value-1, vv. Value-1]=0 then

label5.Caption:='Город НЕ достижим'

else

begin

label5.Caption:='Город достижим';

for i:=1 to pos do

for j:=1 to pos do

StringGrid1.Cells[j, i]: =inttostr (dost[i-1,j-1]);

end;

end;

procedure TForm1. StringGrid3KeyUp (Sender: TObject; var Key: Word;

Shift: TShiftState);

begin

redrow;

end;

procedure TForm1. vvChange (Sender: TObject);

begin

if vv. Value>pos then vv. Value:=pos;

end;

procedure TForm1. isvChange (Sender: TObject);

begin

if isv. Value>pos then isv. Value:=pos;

end;

procedure TForm1. IzverChange (Sender: TObject);

begin

if izver. Value>pos then izver. Value:=pos;

end;

procedure TForm1. N6Click (Sender: TObject);

begin

form2.show;

end;

procedure redrow_result_true;

var i, j: integer;

begin

if pos =0 then exit;

n:=form1.stringgrid3.ColCount-1;

form1.Image1.Canvas.Pen.Mode := pmCopy;

form1.Image1.Canvas.Brush.Color := clWhite;

form1.Image1.Canvas.Rectangle (0,0,form1.Image1.Width, form1. Image1.Height); // очистка канваса без мигания

form1.Image1.Canvas.Pen.Width:=3;

form1.Image1.Canvas.Pen.Color := clGreen;

for i:=1 to n do // рисуем ребра

for j:=1 to n do

if strtoint (form1.StringGrid3.Cells[i, j])>0 then

begin

form1.Image1.Canvas.MoveTo (vers[i]. x, vers[i].y);

form1.Image1.Canvas.lineTo (vers[j].x, vers[j].y);

/// красная точка направления

form1.Image1.Canvas.pen.Color := clRed;

form1.Image1.Canvas.Brush.Color := clRed;

form1.Image1.Canvas.ellipse (round (vers[j]. x+(vers[i].xvers[j]. x)*0.9)-4,round (vers[j].y+(vers[i].yvers[j]. y)*0.9)-4,

round (vers[j].x+(vers[i].x-vers[j].x)*0.9)+4,round (vers[j].y+(vers[i].yvers[j]. y)*0.9)+4);

form1.Image1.Canvas.ellipse (round (vers[j].x+(vers[i].xvers[j]. x)*0.93)-3,round (vers[j].y+(vers[i].yvers[j]. y)*0.93)-3,

round (vers[j].x+(vers[i].xvers[j]. x)*0.93)+3,round (vers[j].y+(vers[i].yvers[j]. y)*0.93)+3);

form1.Image1.Canvas.ellipse (round (vers[j].x+(vers[i].xvers[j]. x)*0.95)-2,round (vers[j].y+(vers[i].yvers[j]. y)*0.95)-2,

round (vers[j].x+(vers[i].xvers[j]. x)*0.95)+2,round (vers[j].y+(vers[i].yvers[j]. y)*0.95)+2);

form1.Image1.Canvas.ellipse (round (vers[j].x+(vers[i].xvers[j]. x)*0.97)-1,round (vers[j].y+(vers[i].yvers[j]. y)*0.97)-1,

round (vers[j].x+(vers[i].xvers[j]. x)*0.97)+1,round (vers[j].y+(vers[i].yvers[j]. y)*0.97)+1);

form1.Image1.Canvas.Pen.Width:=3;

form1.Image1.Canvas.Pen.Color := clGreen;

form1.Image1.Canvas.Brush.Color := clWhite;

form1.Image1.Canvas.pen.Style:= psSolid ;

end;

form1.Image1.Canvas.Pen.Width:=1;

form1.Image1.Canvas.Pen.Color := clBlack;

for i:=1 to n do

begin // вершины — кружки с номером вершины

Form1.Image1.Canvas.Brush.Color:=RGB (234,228,36);

Form1.Image1.Canvas.Ellipse (vers[i]. x-10,vers[i].y-10,vers[i].x+10,vers[i].y+10);

Form1.Image1.Canvas.TextOut (vers[i].x-3,vers[i].y-6,inttostr (i));

end;

end;

procedure redrow_result_false;

var i, j: integer;

begin

if pos =0 then exit;

n:=form1.stringgrid3.ColCount-1;

form1.Image1.Canvas.Pen.Mode := pmCopy;

form1.Image1.Canvas.Brush.Color := clWhite;

form1.Image1.Canvas.Rectangle (0,0,form1.Image1.Width, form1. Image1.Height); // очистка канваса без мигания

form1.Image1.Canvas.Pen.Width:=3;

form1.Image1.Canvas.Pen.Color := clYellow;

for i:=1 to n do // рисуем ребра

for j:=1 to n do

if strtoint (form1.StringGrid3.Cells[i, j])>0 then

begin

form1.Image1.Canvas.MoveTo (vers[i]. x, vers[i].y);

form1.Image1.Canvas.lineTo (vers[j].x, vers[j].y);

/// красная точка направления

form1.Image1.Canvas.pen.Color := clRed;

form1.Image1.Canvas.Brush.Color := clRed;

form1.Image1.Canvas.ellipse (round (vers[j]. x+(vers[i].xvers[j]. x)*0.9)-4,round (vers[j].y+(vers[i].yvers[j]. y)*0.9)-4,

round (vers[j].x+(vers[i].x-vers[j].x)*0.9)+4,round (vers[j].y+(vers[i].yvers[j]. y)*0.9)+4);

form1.Image1.Canvas.ellipse (round (vers[j].x+(vers[i].xvers[j]. x)*0.93)-3,round (vers[j].y+(vers[i].yvers[j]. y)*0.93)-3,

round (vers[j].x+(vers[i].xvers[j]. x)*0.93)+3,round (vers[j].y+(vers[i].yvers[j]. y)*0.93)+3);

form1.Image1.Canvas.ellipse (round (vers[j].x+(vers[i].xvers[j]. x)*0.95)-2,round (vers[j].y+(vers[i].yvers[j]. y)*0.95)-2,

round (vers[j].x+(vers[i].xvers[j]. x)*0.95)+2,round (vers[j].y+(vers[i].yvers[j]. y)*0.95)+2);

form1.Image1.Canvas.ellipse (round (vers[j].x+(vers[i].xvers[j]. x)*0.97)-1,round (vers[j].y+(vers[i].yvers[j]. y)*0.97)-1,

round (vers[j].x+(vers[i].xvers[j]. x)*0.97)+1,round (vers[j].y+(vers[i].yvers[j]. y)*0.97)+1);

form1.Image1.Canvas.Pen.Width:=3;

form1.Image1.Canvas.Pen.Color := clYellow;

form1.Image1.Canvas.Brush.Color := clWhite;

form1.Image1.Canvas.pen.Style:= psSolid ;

end;

form1.Image1.Canvas.Pen.Width:=1;

form1.Image1.Canvas.Pen.Color := clBlack;

for i:=1 to n do

begin // вершины — кружки с номером вершины

Form1.Image1.Canvas.Brush.Color:=RGB (234,228,36);

Form1.Image1.Canvas.Ellipse (vers[i]. x-10,vers[i].y-10,vers[i].x+10,vers[i].y+10);

Form1.Image1.Canvas.TextOut (vers[i].x-3,vers[i].y-6,inttostr (i));

end;

end;

procedure TForm1. StringGrid3Set (Sender: TObject; ACol,

ARow: Integer; const Value: String);

begin

TStringGrid (Sender).Cells[ARow, ACol] := Value;

end;

procedure TForm1. Button3Click (Sender: TObject);

begin

Form3.Show;

redrow;

Button9.Click;

end;

procedure Dostizhimost (izver:integer);

begin

izver:=izver;

doroga:=0;

vver:=0;

if pos<2 then exit;

Matrix;

for i:=1 to pos do

if dost[izver-1,i-1]<>0 then

begin

result:=true;

Form1.Label5.Caption:='Все города достижимы';

end;

doroga:=Round ((doroga-pos)/(5*pos));

vver:=Round (vver/pos);

if (doroga<=3) and ((vver<5) or (vver=6) or (vver=10)) then

begin

for i:=1 to pos do

begin

for j:=1 to pos+1 do

if dost[izver-1,j-1]=0 then

begin

Form1.StringGrid3.Cells[izver, j]: ='1';

Form1.StringGrid3.Cells[j, izver]:='1';

Form1.Label5.Caption:='Все города достижимы';

result:=true;

Matrix;

end;

for j:=1 to pos do

if dost[izver-1,j-1]=0 then

begin

Form1.StringGrid3.Cells[izver, j]: ='1';

Form1.StringGrid3.Cells[j, izver]:='1';

Form1.Label5.Caption:='Все города достижимы';

Matrix;

end;

end;

end

else begin

result:=false;

Form1.Label5.Caption:='Не все города достижимы';

end;

end;

procedure TForm1. Button12Click (Sender: TObject);

var i, j: integer;

begin

Dostizhimost (Form1.izver.Value);

if result then redrow_result_true else redrow_result_false;

end;

end.

unit Unit2; // модуль формы 2 «О программе»

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

type

TForm2 = class (TForm)

Label1: TLabel;

procedure Label1Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form2: TForm2;

implementation

{$R *.dfm}

procedure TForm2. Label1Click (Sender: TObject);

begin

Close;

end;

end.

unit Unit3; // модуль формы 3 «Задание»

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, unit1;

type

TForm3 = class (TForm)

Button1: TButton;

Label1: TLabel;

procedure Button1Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form3: TForm3;

implementation

{$R *.dfm}

procedure TForm3. Button1Click (Sender: TObject);

begin

Close;

end;

end.

unit Unit4; // модуль формы 4 «Заставочная форма»

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ExtCtrls, StdCtrls;

type

TForm4 = class (TForm)

Timer1: TTimer;

Button1: TButton;

Label1: TLabel;

Image1: TImage;

procedure Button1Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form4: TForm4;

implementation

{$R *.dfm}

procedure TForm4. Button1Click (Sender: TObject);

begin

Form4.Timer1.Enabled:=false;

close;

end;

end.

Приложение Б

Блок-схемы основных подпрограмм.

1. Достижимость до всех городов (подпрограмма procedure Dostizhimost (izver:integer))

— 6 ;

— 4;

— 6 ;

— 4;

— 6 ;

— 4;

2. Построение матрицы достижимости по матрице смежности (подпрограмма Matrix)

— 6 ;

— 4;

— 6 ;

— 4;

Приложение В

Описание внешнего вида пользовательского интерфейса

На рисунке представлена главная форма программы.

Компоненты главной формы:

— Image1;

— Buttons;

— SpinEdit;

— StringGrid;

— GroupBox;

— PageControl;

— MainMenu;

— PopupMenu

— Label;

На рисунке 1 отмечено 4 области:

1. Визуальный редактор, который состоит из 4-х кнопок: «Разместить город», «Добавить дорогу», «Удалить город», «Задание»; каждой из которых привязана своя подпрограмма.

2. Решение, которое состоит из 3-х счетчиков: а) — пункт А, б) пункт В, в) — пункт В; 2-х кнопок: «Проверить достижимость», «Достижимость до всех городов»; и поля для рисования системы дорог и городов.

3. Меню программы, которое содержит в себе 2 подменю :

· Файл:

· О программе:

4. Граф, который содержит в себе:

· Матрицу смежности:

· Матрицу достижимости:

· Управление графом:

· 2 кнопки: «Загрузить граф из файла», «Сохранить текущий граф в файл»;

· Счетчик городов.

Приложение Г

Тестовый случай 1

Рисунок 1

Тестовый случай 2:

Рисунок 2

Тестовый случай 3

Рисунок 3

Тестовый случай 4

Рисунок 4

Тестовый случай 5

Рисунок 5

Тестовый случай 6

Рисунок 6

Тестовый случай 7

Рисунок 7 (а) Рисунок 7 (б)

Тестовый случай 8