Разработка приложения, предназначенного для нахождения раскраски заданного неориентированного графа с использованием метода Зыкова
Разработка и отладка графического приложения со стандартизированным интерфейсом. Переборный и последовательный алгоритмы раскраски неориентированного графа. Описание модулей uMain, uData, uFiling, uColoring, uInputk, uHelp. Тестирование работы приложения.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 11.02.2016 |
| Размер файла | 1,0 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
Введение
1. Постановка задачи
2. Краткие теоретические сведения
2.1 Переборный алгоритм раскраски
2.2 Последовательный алгоритм раскраски
3. Разработка приложения
3.1 Структура
3.2 Описание модулей
3.2.1 Модуль uMain
3.2.2 Модуль uData
3.2.3 Модуль uFiling
3.2.4 Модуль uColoring
3.2.5 Модуль uInputk
3.2.6 Модуль uHelp
3.3 Демонстрация работы программы
3.4 Тестирование приложения
3.5 Руководство пользователя
Заключение
Приложение А
Введение
Задачи на графах являются одними из наиболее трудоемких. Для многих из них не существуют достаточно эффективных алгоритмов решения. Это объясняется комбинаторным характером процесса поиска решений и сложной логикой действий на каждом его шаге. Реализация задач данного класса на ПЭВМ позволяет повысить качество их решения за счет существенного увеличения числа анализируемых вариантов.
С точки зрения эффективности учебного процесса задачи на графах превосходят большинство других видов задач. Это обусловлено, с одной стороны, необходимостью разработки и проверки разветвленных и логически сложных алгоритмов, с другой стороны, потребностью в проектировании комплексных структур данных. Наконец, графовые задачи требуют интенсивного использования языковых и библиотечных средств для программирования графики. Все сказанное, в конечном счете, наилучшим образом способствует развитию логико-алгоритмической культуры обучаемого и приобретению навыков разработки и отладки графических приложений со стандартизированным интерфейсом.
приложение интерфейс граф модуль
1. Постановка задачи
В данной курсовой работе необходимо разработать приложение, предназначенное для нахождения раскраски заданного неориентированного графа с использованием метода Зыкова.
Заданый граф , где V -- множество вершин; E -- множество ребер, и положительное целое число , где -- мощность множества V. Раскрасить вершины графа K красками так, чтобы ни одно его ребро не имело соцветных концов. Если такая раскраска невозможна, выдать на экран соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение его вершин на экране.
Разрабатываемая программа, с точки зрения пользователя, должна обладать следующими свойствами:
· работа в условиях визуального (графического) режима;
· удобство и простота ввода графа (задание с помощью мыши, клавиатуры и меню);
· обеспечение автоматического контроля правильности входной информации, вводимой пользователем (контроль параметров графа, количества цветов);
· возможность сохранения и считывания сохраненных графов из файлов;
· однозначность и наглядность представления результатов вычислений (цветовое выделение раскраски, выдача сообщения при невозможности раскраски).
2. Краткие теоретические сведения
Раскраской вершин графа называется назначение цветов его вершинам. Обычно цвета - это числа 1,2…k. Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения во множестве {1,2…k}. Раскраску можно также рассматривать как разбиение множества вершин , где - множество вершин цвета i. Множества называют цветными классами. Раскраска называется правильной, если каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного графа G в наименьшее число цветов. Это число называется хроматическим числом графа и обозначается .
В правильной раскраске полного графа все вершины должны иметь разные цвета, поэтому . Если в каком-нибудь графе имеется полный подграф с k вершинами, то для раскраски этого подграфа необходимо k цветов. Отсюда следует, что для любого графа выполняется неравенство .
Однако хроматическое число может быть и строго больше кликового числа. Например, для цикла длины 5 , а . Другой пример показан на рис. 1. На нем изображен граф, вершины которого раскрашены в 4 цвета (цвета вершин показаны в скобках). Нетрудно проверить, что трех цветов для правильной раскраски этого графа недостаточно. Следовательно, его хроматическое число равно 4. Очевидно также, что кликовое число этого графа равно 3.
Рисунок 1.
Очевидно, что тогда и только тогда, когда G - пустой граф. Нетрудно охарактеризовать и графы с хроматическим числом 2 (точнее, не больше 2). По определению, это такие графы, у которых множество вершин можно разбить на два независимых множества. Но это совпадает с определением двудольного графа. Поэтому двудольные графы называют еще бихроматическими. Согласно теореме Кенига, граф является бихроматическим тогда и только тогда, когда в нем нет циклов нечетной длины.
Для графов с хроматическим числом 3 такого простого описания мы не знаем. Неизвестны и простые алгоритмы, проверяющие, можно ли данный граф раскрасить в 3 цвета. Более того, задача такой проверки (вообще, задача проверки возможности раскрасить граф в k цветов при любом фиксированном ) является NP-полной.
2.1 Переборный алгоритм раскраски
Данный алгоритм оперирует деревом вариантов, обход которого позволяет найти точное решение (хроматическое число графа). Нахождение точного решения, однако, обеспечивается экспоненциальной временной сложностью алгоритма.
Выберем в данном графе G две несмежные вершины и и построим два новых графа: , получающийся добавлением ребра к графу G, и, получающийся из G слиянием вершин x и y. Операция слияния состоит в удалении вершин x и y и добавлении новой вершины z и ребер, соединяющих ее с каждой вершиной, с которой была смежна хотя бы одна из вершин x, y. На рис. 2 показаны графы и , получающиеся из графа G, изображенного на рис. 1, с помощью этих операций, если в качестве x и y взять вершины a и .
Рисунок 2.
Если в правильной раскраске графа G вершины x и y имеют разные цвета, то она будет правильной и для графа . Если же цвета вершин x и y в раскраске графа G одинаковы, то граф можно раскрасить в то же число цветов: новая вершина z окрашивается в тот цвет, в который окрашены вершины x и y, а все остальные вершины сохраняют те цвета, которые они имели в графе G. И наоборот, раскраска каждого из графов , , очевидно, дает раскраску графа G в то же число цветов. Поэтому , что дает возможность рекурсивного нахождения раскраски графа в минимальное число цветов. Заметим, что граф имеет столько же вершин, сколько исходный граф, но у него больше ребер. Поэтому рекурсия, в конечном счете, приводит к полным графам, для которых задача о раскраске решается тривиально.
2.2 Последовательный алгоритм раскраски
Существует много процедур раскрашивания графов, позволяющих находить хорошие приближения для хроматического числа графа в тех случаях, когда размеры графа слишком велики и получение оптимальной раскраски точными методами затруднительно. Здесь дается краткое описание одной из таких процедур и ряда ее разновидностей.
В этом простейшем из методов вершины вначале располагаются в порядке не возрастания их степеней.
Первая вершина окрашивается в цвет 1; затем список вершин просматривается сверху вниз (по невозрастанию степеней) и в цвет 1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Потом возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т.д., пока не будут окрашены все вершины. Число использованных цветов будет тогда приближенным значением хроматического числа графа.
Простая модификация описанной выше эвристической процедуры состоит в переупорядочивании неокрашенных вершин после окраски каждой очередной вершины: оставшиеся неокрашенные вершины записываются в порядке невозрастания их «относительных» степеней, т.е. степеней в таком графе, который получается из данного после удаления окрашенных вершин (вместе с ребрами, инцидентными удаленным вершинам).
В этой процедуре по умолчанию предполагалось, что если две вершины имеют одинаковые степени, то их взаимное положение в списке случайно. В таких ситуациях уточнение в размещении вершин можно осуществлять с помощью двухшаговых степеней вершин , имеющих одинаковые степени (одинаковые 1-шаговые степени), где определяется как число маршрутов длины 2, исходящих из . Тогда эти вершины можно разместить в соответствии с величинами степеней . Если все-таки найдутся вершины, у которых совпадают и степени , и степени , то можно вычислить трехшаговые степени (определяемые аналогичным способом) и разместить вершины с учетом степеней и т.д. Можно действовать иначе: размещать вершины сразу в соответствии с их степенями или степенями и применять тот же самый последовательный метод раскраски.
3. Разработка приложения
3.1 Структура
Данный проект состоит из 6-ти модулей: uMain, uData, uHelp, uFiling, uColoring, uInputk. Схема взаимодействия модулей представлена на рисунке 3
Рисунок 3 - Схема модулей
3.2 Описание модулей
3.2.1 Модуль uMain
Модуль предназначен для организации редактирования обрабатываемых графов, реализации функции главного меню и координации работы остальных программных модулей.
Основные переменные, константы и типы модуля:
fmMain: TfmMain - основная форма;
TUndoItem - тип данных для представления информации о последнем выполненном действии над графом (используется в режимах Отмена и Восстановление);
VRadius - радиус окружности вершины графа;
AdMatrix: TAdMatrix - матрица смежности вершин текущего графа;
VCount: Byte - число вершин текущего графа;
VColor: TColoring - текущая раскраска вершин;
VCenter: array of TPoint - массив координат центров вершин;
UndoItem: array of TUndoItem - информация об отмененной операции;
k: Byte - требуемое число цветов;
GraphChanged: Boolean - признак измененного и не сохраненного графа.
Процедуры модуля:
Процедура iFOpenClick - открывает файл при выборе пункта меню «Открыть», производит очистку и переформат таблицы матрицы смежности sgMatrix.
Процедура iFSaveClick - сохраняет файл при выборе пункта меню «Сохранить».
Процедура btnColoringClick - запускает процесс раскраски графа.
Процедура FormActivate - осуществляет инициализацию глобальных и компонентных данных модуля.
Процедура btnNewClick - создает новый граф при нажатии на кнопку «Новый граф».
Процедура iFNewClick - создает новый граф при выборе пункта меню «Новый».
Процедура iFSaveAsClick - сохраняет граф в другом файле при выборе пункта меню «Сохранить как».
Процедура iFExitClick - осуществляет выход из программы при выборе пункта меню «Выход».
Процедура btnExitClick - осуществляет выход из программы при нажатии на кнопку «Выход».
Процедура iEAddVClick - осуществляет добавление вершины, при этом изменяет матрицу смежности, определяет координаты новой вершины и осуществляет перерисовку вершин.
Процедура iEDelVClick - открывает форму fmInputk как модальную, осуществляет удаление выбранной вершины, удаление смежных с ней ребер, сброс цветов, перенумерацию и перерисовку оставшихся вершин.
Процедура iEUndoClick - осуществляет отмену последнего действия при выборе пункта меню «Отмена».
Процедура iERedoClick - осуществляет восстановление последнего отмененного действия при выборе пункта меню «Восстановление».
Процедура FillUndoDelVrx - осуществляет заполнение структуры данных для отмены удаления вершины.
Процедура iHAboutClick - осуществляет загрузку информации о программе.
Процедура FormDeactivate - осуществляет освобождение памяти при закрытии формы.
Процедура sgMatrixSelectCell - осуществляет редактирование матрицы смежности вершин графа, сброс цветов и перерисовку вершин.
Процедура FormPaint - осуществляет перерисовку текущего графа в области построения, а также отображает границы области построения графа.
Процедура FormMouseUp - осуществляет добавление или удаление вершины графа при помощи мыши, при этом изменяет матрицу смежности, определяет координаты новой вершины, осуществляет перерисовку вершин после перенумерации и сброс цветов.
Процедура FormMouseDown - осуществляет захват вершины левой кнопкой мыши.
Процедура FormMouseMove - осуществляет соединение вершин перетаскиванием, очистку области, где ребро было на предыдущем шаге и прорисовку нового ребра в следующей позиции.
Процедура FormCloseQuery - запрос на закрытие формы.
Процедура InitForm - осуществляет приведение вида формы к исходному состоянию.
Процедура RemoveVertex - осуществляет удаление выбранной вершины, перезапись sgMatrix в матрицу смежности, формирование массива координат центров вершин, смежных с удаляемой, перенумерацию матрицы смежности и сдвиг массива координат центров вершин, а также изменение размеров структур данных и восстановление измененной матрицы смежности.
Процедура FillAdMatrix - осуществляет построение матрицы смежности по содержимому sgMatrix.
Процедура RepaintVertex - осуществляет перерисовку вершины на форме.
Процедура RepaintEdge - осуществляет перерисовку ребра на форме.
Процедура RepaintAllVertices - осуществляет перерисовку всех вершин на форме.
Процедура InitUndo - инициализирует структуру данных об отмененном действии.
Процедура FillUndoDelVrx - осуществляет заполнение структуры данных для отмены удаления вершины.
Процедура PrintGraphPath - осуществляет отображение пути к файлу с графом в заголовке.
Функции модуля:
Функция SaveRequest - вызывает запрос на сохранение графа в файле.
3.2.2 Модуль uData
Модуль служит для объединения общеиспользуемых констант и типов:
MaxVCount - максимальное число вершин графа;
TAdMatrix = array of array of Byte - матрицасмежностиграфа;
TColoring = array of ShortInt - вектор цветов вершин;
TRealColors = array[0..MaxVCount-1] of TColor - системные имена цветов;
TVertices = array of TPoint - координаты центров вершин;
TGraphFile = file of Byte - файл графа.
3.2.3 Модуль uFiling
Модуль содержит функции для управления записью графов в файлы и считывание сохраненных графов из файлов.
Основные переменные, константы и типы модуля
GraphFile: TGraphFile - файл для сохранения графа.
Функции модуля
DoSaveFile - осуществляет сохранение графа в файле по матрице смежности.
DoReadFile - осуществляет чтение графа из файла в матрицу смежности.
3.2.4 Модуль uColoring
Модуль объединяет процедуры, функции и переменные, используемые при реализации алгоритма раскраски графа.
Основные переменные, константы и типы модуля
RealColors: TRealColors - фактические цвета раскраски вершин;
VDegree: array of ShortInt - массив относительных локальных степеней;
VNumber: array of Byte - отсортированный массив номеров вершин;
Uncolored: set of Byte - множество не раскрашенных вершин.
Процедуры модуля
DoNonminColoring - осуществляет раскраску графа в NewColorCount цветов по найденной минимальной раскраске.
InsertionSort - осуществляет сортировку массива локальных степеней методом вставки.
Функции модуля
DoMinColoring - осуществляет раскраску графа в минимальное число цветов.
ResetColoring - осуществляет обнуление массива цветов вершин графа.
3.2.5 Модуль uInputk
Модуль содержит определение диалога для ввода количества цветов при раскраске графа, а также номера удаляемой вершины.
Основные переменные, константы и типы модуля
fmInputk: TfmInputk - форма для ввода числа цветов k.
Процедуры модуля
Процедура btnSetClick - устанавливает значение k при нажатии на кнопку «Задать».
Процедура btnCancelClick - игнорирует ввод k при щелчке по кнопке «Отмена».
Процедура ComboBoxChange - осуществляет проверку по числу вершин.
Процедура FormActivate - обнуляет поле ввода ComboBox при запуске формы ввода числа цветов.
3.2.6 Модуль uHelp
Модуль обеспечивает отображение окна о программе.
Основные переменные, константы и типы модуля:
fmHelp: TfmHelp - форма для окна о программе;
Процедуры модуля:
Процедура FormActivate - производит настройку внешнего вида и заполнение окна отображения текстом из файла справки или информацию о программе.
Процедура FormDeactivate - восстанавливает стандартный шрифт.
3.3 Демонстрация работы программы
Для запуска программы необходимо запустить файл Сoloring.exe. После запуска, появляется главное окно программы (рис. 4)
Рисунок 4 - Главное окно приложения
Так же это окно отобразится после нажатия на кнопку «Новый граф» и при переходе «Файл-Новый».
Рисование вершин графа производится нажатием левой кнопки мыши по окну либо «Редактирование-Добавить вершину»(рис 5, рис 6).
Рисунок 5 - Рисование вершин
Рисунок 6- Добавление вершины
Рёбра рисуются с помощью перетаскиванием мыши от одной вершины к другой (рис. 7)
Рисунок 7 - Рисование рёбер
Для того что бы раскрасить граф, необходимо в главном окне программы нажать на кнопку «Раскраска», после чего появится диалоговое окно, предлагающее пользователю выбрать необходимое количество цветов для раскраски (рис. 8)
Рисунок 8 - Выбор количества цветов для раскраски графа
После нажатия на кнопку «Задать» в окне выбора количества цветов, нарисованный граф раскрасится (рис. 9)
Рисунок 9 - Раскраска графа
В приложении реализовано сохранение графа в файл, для этого необходимо пройти «Файл-Сохранить» почле чего отобразится окно для сохранения (рис. 10)
Рисунок 10- Сохранение графа в файл
Есть возможность все сохранённые графы открыть, для этого необходимо пройти «Файл-Открыть» (рис 11)
Рисунок 11 - Открытие графа
Удаление вершин в графе возможно 2-мя способами:
1) повторное нажатие левой клавишей мыши на вершину (рис 12)
Рисунок 12 - Удаление вершины
2) пройти «Редактирование-Удалить вершину»,затем выбрать вершину для удаления(рис 13)
Рисунок 13 - Выбор вершины для удаления
Максимальное число вершин графа в данной версии программы ограничивается значением 50, число ребер произвольно. Если же пользователь хочет нарисовать больше 50 вершин, то появится сообщение об ошибке (рис 14)
Рисунок 14 - Окно ошибки числа вершин
Окно программы с запросом на сохранение изменений в графе при нажатии одной из кнопок - «Новый граф», «Выход», «Открыть»(рис 15)
Рисунок 15 - Окно с запросом на сохранение изменений в графе
3.4 Тестирование приложения
В ходе тестирования программы осуществлялся ввод графов с различным числом вершин и ребер, проверялась возможность их раскраски в заданное число цветов, при этом устанавливалось число цветов равное хроматическому числу графа (рис.16), а также большее (рис. 17) или меньшее значение (рис. 18). Выполнялась проверка работы программы при предельном значении числа вершин графа (рис. 14), а также при минимально возможном (0) и максимально возможном (полный граф) числе ребер.
Рисунок 16 - Число цветов равное хроматическому числу графа
Рисунок 17 - Число цветов больше хроматического числа графа
Рисунок 18 - Число цветов меньше хроматического числа графа
3.5 Руководство пользователя
Разрабатываемая программа предназначена для нахождения раскраски заданного неориентированного графа ограниченным числом цветов с использованием метода Зыкова.
Входными данными программы являются неориентированный граф, число вершин которого не превышает заданного ограничения, число цветов, которыми необходимо раскрасить данный граф.
К выходным данным относятся вариант раскраски графа заданным числом цветов, хроматическое число графа, сообщения о невозможности нахождения раскраски.
Управление программой реализуется через меню и клавиши-акселераторы. Ряд функций (добавление / удаление вершины, добавление / удаление ребра) реализуется с помощью мыши.
Пункт Файл объединяет действия с файлами, содержащими графы, а также выход из программы. Подпункт Новый обеспечивает очистку области построения и матрицу смежности графа с закрытием текущего файла. Подпункт Открыть активирует диалоговое окно открытия файла и реализует загрузку графа из выбранного файла в область построения и матрицу смежности. Подпункт Сохранить позволяет сохранить внесенные изменения в текущий граф (при первом сохранении выводится окно запроса имени файла).. Подпункт Выход служит для завершения программы (при наличии измененного и не сохраненного графа выводится окно запроса на сохранение файла).
Пункт Редактирование включает действия, обеспечивающие построение графа. Подпункт Добавить вершину позволяет ввести в граф новую вершину с проверкой ограничения на максимальное число вершин. Номер новой вершине присваивается автоматически. Размещение вершин в области построения выполняется в случайных позициях с исключением наложения вершин друг на друга. Добавить вершину можно непосредственно мышью, щелкнув левой кнопкой на пустом месте области построения. Подпункт Удалить вершину служит для удаления выделенной вершины из текущего графа. Выделение вершины выполняется щелчком левой кнопки мыши по ее изображению. Оставшиеся вершины автоматически перенумеровываются. Выполнение каждого из названных подпунктов приводит к изменению размера или содержимого матрицы смежности. Подпункт Отмена позволяет отменить последнее действие по редактированию графа. Подпункт Восстановление обеспечивает противоположное действие. Отменить и восстановить можно только удаление вершины или ребра.
Заключение
В данном курсовом проекте было разработано приложение, позволяющее раскрашивать неориентированные графы. Для раскраски был выбран метод Зыкова.
В результате выполнения данного курсового проекта были получены знания для работы с графами, а также знания, позволяющие раскрашивать неориентированные графы. На основе полученных знаний было создано приложение, позволяющее реализовать выбранный метод раскраски. Приложение отвечает всем поставленным требованиям.
Список используемых источников
1. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Издательство «Мир», 1978. - 432 с.
2. Фаронов В.В. Delphi. Программирование на языке высокого уровня: Учебник для вузов - СПб.: Питер, 2007. - 640 с.: ил.
3. Белова Т.М., Старков Ф.А. Программирование в Delphi: Учебное пособие - Курск. гос.-техн. ун-т. Курск, 2002. - 134 с.
Приложение А
Исходный код приложения
unit uMain;
uses Math, uColoring, uInputk, uFiling, uHelp;
type
TUndoItem = record
VNo: Byte; // Номервершины
VPoint: TPoint; // Координаты центра вершины
end;
const
VRadius = 11; // Радиус окружности вершины
var AdMatrix: TAdMatrix; // Матрица смежности вершин текущего графа
VCount: Byte; // Число вершин текущего графа
VColor: TColoring; // Текущая раскраска вершин
VCenter: array of TPoint; // Массив координат центров вершин
UndoItem: array of TUndoItem; // Информация об отмененной операции
k: Byte; // Требуемое число цветов
GraphChanged: Boolean; // Признак измененного и не сохраненного графа
// Выбор пункта меню для создания нового графа
procedure TfmMain.iFNewClick(Sender: TObject);
begin
btnNewClick(Sender);
end;
// Запрос на сохранение графа в файле
function TfmMain.SaveRequest: Boolean;
begin
result:=False;
if GraphChanged then
begin
if MessageDlg('Текущийграфбылизменен. Сохранить?',
mtWarning, [mbYes, mbNo], 0) = mrYes then
begin
StatusBar.SimpleText:='Сохранениеграфа...';
iFSave.Click;
result:=True;
StatusBar.SimpleText:='Готово';
end;
end;
end;
// Нажатие кнопки для создания нового графа
procedure TfmMain.btnNewClick(Sender: TObject);
begin
if VCount > 0 then SaveRequest;
InitForm;
InitUndo;
MainMenu.Items[0].Items[0].Enabled:=False; // Новый
btnNew.Enabled:=False;
btnColoring.Enabled:=False;
GraphChanged:=False;
SaveDialog.FileName:='';
OpenDialog.FileName:='';
MainMenu.Items[0].Items[2].Enabled:=False; // Сохранить
MainMenu.Items[1].Items[3].Enabled:=True; // Добавитьвершину
MainMenu.Items[1].Items[4].Enabled:=False; // Удалитьвершину
end;
// Выбор пункта меню для открытия файла
procedure TfmMain.iFOpenClick(Sender: TObject);
var i,j,l: Byte;
Overlap: Boolean;
x,y: Integer;
begin
StatusBar.SimpleText:='Открытиефайла';
if VCount > 0 then SaveRequest;
if OpenDialog.Execute then
begin
InitUndo;
if not DoReadFile(OpenDialog.FileName,VCount,AdMatrix) then
MessageDlg('Ошибка при открытии или чтении файла!', mtError, [mbOk], 0)
else
begin
StatusBar.SimpleText:='Готово';
// Очисткаипереформаттаблицы sgMatrix
sgMatrix.Visible:=True;
for i:=0 to sgMatrix.RowCount - 1 do sgMatrix.Rows[i].Clear;
sgMatrix.RowCount:=VCount+1;
sgMatrix.ColCount:=VCount+1;
sgMatrix.FixedRows:=1;
sgMatrix.FixedCols:=1;
for i:=1 to sgMatrix.RowCount - 1 do sgMatrix.Cells[0,i]:=IntToStr(i);
for j:=1 to sgMatrix.ColCount - 1 do sgMatrix.Cells[j,0]:=IntToStr(j);
// Отображение матрицы смежности на sgMatrix
for i:=1 to VCount do
for j:=1 to VCount do
begin
if AdMatrix[i-1,j-1] > 0 then sgMatrix.Cells[j,i]:='1'
else sgMatrix.Cells[j,i]:='';
end;
// Задание координат центров вершин графа случайным образом
SetLength(VCenter,VCount);
l:=0;
repeat
repeat
Overlap:=False;
x:=round(RandG(PaintAreaWidth div 2, PaintAreaWidth div 6));
y:=round(RandG(PaintAreaHeight div 2, PaintAreaHeight div 6));
// Проверка выхода координат за пределы области построения
if (x < VRadius+PaintAreaXMin) or (y < VRadius+PaintAreaYMin) or
(x > PaintAreaWidth - (VRadius + 5)) or
(y > PaintAreaHeight - (VRadius + 5)) then
begin
Overlap:=True; // За пределами - нужны новые координаты
continue
end;
if l = 0 then continue;
for i:=0 to l - 1 do // Проверка наложения на предыдущие вершины
if (abs(VCenter[i].X - x) <= VRadius + 3) and
(abs(VCenter[i].Y - y) <= VRadius + 3) then
begin
Overlap:=True; // Накладываются - нужны новые координаты
Break
end;
until not Overlap;
VCenter[l].X:=x; // Задание координат
VCenter[l].Y:=y;
inc(l);
until l = VCount;
// Обнулениецветов
SetLength(VColor,VCount);
for i:=0 to VCount - 1 do VColor[i]:=-1;
SaveDialog.FileName:=OpenDialog.FileName;
PrintGraphPath;
MainMenu.Items[0].Items[0].Enabled:=True; // Новый
btnNew.Enabled:=True;
btnColoring.Enabled:=True;
GraphChanged:=False;
MainMenu.Items[0].Items[2].Enabled:=False; // Сохранить
MainMenu.Items[1].Items[3].Enabled:=True; // Добавитьвершину
MainMenu.Items[1].Items[4].Enabled:=True; // Удалитьвершину
self.repaint;
end;
end;
end;
// Выбор пункта меню для сохранения файла
procedure TfmMain.iFSaveClick(Sender: TObject);
begin
StatusBar.SimpleText:='Сохранениевфайл';
if (SaveDialog.FileName <> '') or SaveDialog.Execute then
begin
InitUndo;
FillAdMatrix(AdMatrix);
if not DoSaveFile(SaveDialog.FileName,AdMatrix) then
MessageDlg('Ошибка при сохранении файла!', mtError, [mbOk], 0)
else
begin
StatusBar.SimpleText:='Готово';
GraphChanged:=False;
MainMenu.Items[0].Items[2].Enabled:=False; // Сохранить
end;
end;
end;
// Отображение пути к файлу с графом в заголовке
procedure TfmMain.PrintGraphPath;
var Path: string;
PathWidth,HeaderWidth: Integer;
i: Word;
begin
Path:=''; i:=Length(SaveDialog.FileName);
self.Font:=stGraph.Font;
PathWidth:=self.Canvas.TextWidth(Path);
HeaderWidth:=self.Canvas.TextWidth('Исходныйграф +++: ');
while PathWidth < PaintAreaWidth - HeaderWidth do
begin // Отсечениеначальныхсимволовполногоименифайла
Path:=' ' + Path;
Path[1]:=SaveDialog.FileName[i];
PathWidth:=self.Canvas.TextWidth(Path);
dec(i);
if i = 0 then Break;
end;
if i > 0 then stGraph.Caption:='Исходныйграф: ...' + Path
else stGraph.Caption:='Исходныйграф: ' + Path;
end;
// Выбор пункта меню для выхода из программы
procedure TfmMain.iFExitClick(Sender: TObject);
begin
btnExitClick(Sender);
end;
procedure TfmMain.btnExitClick(Sender: TObject);
begin
if VCount > 0 then SaveRequest;
Application.Terminate;
end;
// Выбор пункта меню для добавления вершины
procedure TfmMain.iEAddVClick(Sender: TObject);
var x,y: Integer;
i: Byte;
Overlap,Colored: bool;
begin
if VCount >= MaxVCount then
begin
MessageDlg('Число вершин графа не должно превышать ' +
IntToStr(MaxVCount) + '!', mtWarning, [mbOk], 0);
Exit
end; // Добавление вершины
InitUndo;
inc(VCount);
SetLength(VCenter,VCount);
SetLength(VColor,VCount);
SetLength(AdMatrix,VCount,VCount);
Colored:=ResetColoring(VCount,VColor); // Сбросцветов
sgMatrix.Visible:=True; // Изменение матрицы смежности
sgMatrix.RowCount:=VCount+1;
sgMatrix.Rows[VCount].Clear;
sgMatrix.ColCount:=VCount+1;
sgMatrix.Cols[VCount].Clear;
sgMatrix.FixedCols:=1;
sgMatrix.FixedRows:=1;
sgMatrix.Cells[VCount,0]:=IntToStr(VCount);
sgMatrix.Cells[0,VCount]:=IntToStr(VCount);
repeat // Определение координат новой вершины
Overlap:=False;
x:=round(RandG(PaintAreaWidth div 2, PaintAreaWidth div 6));
y:=round(RandG(PaintAreaHeight div 2, PaintAreaHeight div 6));
// Проверка выхода координат за пределы области построения
if (x < VRadius + PaintAreaXMin) or (y < VRadius + PaintAreaYMin) or
(x > PaintAreaWidth - (VRadius + 5)) or
(y > PaintAreaHeight - (VRadius + 5)) then
begin
Overlap:=True; // За пределами - нужны новые координаты
continue
end;
for i:=0 to VCount-2 do // Проверканаложениявершин
if (abs(VCenter[i].X - x) <= VRadius + 3) and
(abs(VCenter[i].Y - y) <= VRadius + 3) then
begin
Overlap:=True; // Накладываются - нужны новые координаты
Break
end;
until not Overlap;
VCenter[VCount-1].X:=x; // Заданиекоординат
VCenter[VCount-1].Y:=y;
if Colored then RepaintAllVertices // Перерисовкавершин
else RepaintVertex(x,y);
MainMenu.Items[0].Items[0].Enabled:=True; // Новый
btnNew.Enabled:=True;
btnColoring.Enabled:=True;
MainMenu.Items[0].Items[2].Enabled:=True; // Сохранить
MainMenu.Items[1].Items[4].Enabled:=True; // Удалитьвершину
GraphChanged:=True; // Граф следует сохранить
end;
// Выбор пункта меню для удаления вершины
procedure TfmMain.iEDelVClick(Sender: TObject);
var i,j,VNo: Byte;
x,y: Integer;
RemVrx: TVertices;
begin
StatusBar.SimpleText:='Удалениевершины';
fmInputk.Caption:='Выбор вершины для удаления';
fmInputk.StaticText.Caption:='Выберите удаляемую вершину из списка:';
fmInputk.btnSet.Caption:='Удалить';
fmInputk.ComboBox.Items.Clear;
for i:=1 to VCount do
fmInputk.ComboBox.Items.Add(IntToStr(i));
fmInputk.Tag:=VCount;
if fmInputk.ShowModal = mrOk then
begin
VNo:=StrToInt(fmInputk.ComboBox.Text);
x:=VCenter[VNo-1].X; // Удаление вершины
y:=VCenter[VNo-1].Y;
ResetColoring(VCount,VColor); // Сбросцветов
FillUndoDelVrx(VNo); // Сохранение информации для отмены удаления
MainMenu.Items[1].Items[0].Enabled:=True; // Undo
MainMenu.Items[1].Items[1].Enabled:=False; // Redo
RemoveVertex(VNo,VCount,RemVrx);
if RemVrx <> Nil then
for j:=0 to High(RemVrx) do // Перерисовка удаленных ребер
RepaintEdge(x,y,RemVrx[j].X,RemVrx[j].Y);
RepaintVertex(x,y); // Перерисовка удаленной вершины
//if RemVrx <> Nil then
RepaintAllVertices; // Перерисовка вершин после перенумерации
RemVrx:=Nil;
StatusBar.SimpleText:='Готово';
if VCount = 0 then
begin // Все вершины были удалены
MainMenu.Items[0].Items[0].Enabled:=False; // Новый
btnNew.Enabled:=False;
btnColoring.Enabled:=False;
MainMenu.Items[0].Items[2].Enabled:=False; // Сохранить
MainMenu.Items[1].Items[4].Enabled:=False; // Удалитьвершину
end
else
begin
GraphChanged:=True; // Графнадосохранить
MainMenu.Items[0].Items[2].Enabled:=True; // Сохранить
end;
end;
end;
// Выбор пункта меню для отмены последнего действия
procedure TfmMain.iEUndoClick(Sender: TObject);
var i,j: Byte;
begin
MainMenu.Items[1].Items[0].Enabled:=False; // Undo
MainMenu.Items[1].Items[1].Enabled:=True; // Redo
if UndoItem[0].VPoint.X = -1 then
begin // Отменаудаленияребра
sgMatrix.Cells[UndoItem[0].VNo,UndoItem[1].VNo]:='1';
sgMatrix.Cells[UndoItem[1].VNo,UndoItem[0].VNo]:='1';
sgMatrix.Update; // Прорисовкавосстановленногоребра
RepaintEdge(VCenter[UndoItem[0].VNo-1].X,VCenter[UndoItem[0].VNo-1].Y,
VCenter[UndoItem[1].VNo-1].X,VCenter[UndoItem[1].VNo-1].Y);
end
else
begin // Отмена удаления вершины вместе со смежными ребрами
inc(VCount);
SetLength(VCenter,VCount); // Восстановление массива координат вершин
if VCount > 1 then
for i:=VCount - 1 downto UndoItem[0].VNo do VCenter[i]:=VCenter[i-1];
VCenter[UndoItem[0].VNo-1]:=UndoItem[0].VPoint;
SetLength(AdMatrix,VCount,VCount); // Изменениематрицысмежности
if VCount > 1 then
begin
for j:=VCount - 1 downto UndoItem[0].VNo do // Вставкастолбца
for i:=0 to VCount - 1 do
AdMatrix[i,j]:=AdMatrix[i,j-1];
for i:=0 to VCount - 1 do AdMatrix[i,UndoItem[0].VNo-1]:=0;
for i:=VCount - 1 downto UndoItem[0].VNo do // Вставкастроки
for j:=0 to VCount - 1 do
AdMatrix[i,j]:=AdMatrix[i-1,j];
for j:=0 to VCount - 1 do AdMatrix[UndoItem[0].VNo-1,j]:=0;
for i:=1 to High(UndoItem) do
begin // Восстановлениесвязейудаленнойвершины
AdMatrix[UndoItem[0].VNo-1,UndoItem[i].VNo-1]:=1;
AdMatrix[UndoItem[i].VNo-1,UndoItem[0].VNo-1]:=1;
end;
end;
sgMatrix.Visible:=True; // Изменение матрицы смежности на форме
sgMatrix.RowCount:=VCount+1;
sgMatrix.ColCount:=VCount+1;
sgMatrix.FixedCols:=1;
sgMatrix.FixedRows:=1;
for i:=1 to VCount do sgMatrix.Cells[0,i]:=IntToStr(i);
for j:=1 to VCount do sgMatrix.Cells[j,0]:=IntToStr(j);
for i:=1 to VCount - 1 do
for j:=i+1 to VCount do
if AdMatrix[i-1,j-1] > 0 then
begin
sgMatrix.Cells[i,j]:='1';
sgMatrix.Cells[j,i]:='1';
end
else
begin
sgMatrix.Cells[i,j]:='';
sgMatrix.Cells[j,i]:='';
end;
SetLength(VColor,VCount);
MainMenu.Items[0].Items[0].Enabled:=True; // Новый
btnNew.Enabled:=True;
btnColoring.Enabled:=True;
sgMatrix.Update;
self.Repaint;
end;
end;
// Выбор пункта меню для выполнения отмененного действия
procedure TfmMain.iERedoClick(Sender: TObject);
var x,y,j: Integer;
RemVrx: TVertices;
begin
MainMenu.Items[1].Items[0].Enabled:=True; // Undo
MainMenu.Items[1].Items[1].Enabled:=False; // Redo
if UndoItem[0].VPoint.X = -1 then
begin // Повторноеудалениеребра
sgMatrix.Cells[UndoItem[0].VNo,UndoItem[1].VNo]:='';
sgMatrix.Cells[UndoItem[1].VNo,UndoItem[0].VNo]:='';
sgMatrix.Update; // Прорисовкаудаленногоребра
RepaintEdge(VCenter[UndoItem[0].VNo-1].X,VCenter[UndoItem[0].VNo-1].Y,
VCenter[UndoItem[1].VNo-1].X,VCenter[UndoItem[1].VNo-1].Y);
end
else
begin // Повторное удаление вершины со смежными ребрами
x:=VCenter[UndoItem[0].VNo-1].X;
y:=VCenter[UndoItem[0].VNo-1].Y;
MainMenu.Items[1].Items[0].Enabled:=True; // Undo
MainMenu.Items[1].Items[1].Enabled:=False; // Redo
RemoveVertex(UndoItem[0].VNo,VCount,RemVrx);
if RemVrx <> Nil then
for j:=0 to High(RemVrx) do // Перерисовкаудаленныхребер
RepaintEdge(x,y,RemVrx[j].X,RemVrx[j].Y);
RepaintVertex(x,y); // Перерисовка удаленной вершины
if RemVrx <> Nil then
RepaintAllVertices; // Перерисовка вершин после перенумерации
RemVrx:=Nil;
if VCount = 0 then
begin // Все вершины были повторно удалены
MainMenu.Items[0].Items[0].Enabled:=False; // Новый
btnNew.Enabled:=False;
btnColoring.Enabled:=False;
MainMenu.Items[0].Items[2].Enabled:=False; // Сохранить
MainMenu.Items[1].Items[3].Enabled:=True; // Добавитьвершину
MainMenu.Items[1].Items[4].Enabled:=False; // Удалитьвершину
end
else
begin
GraphChanged:=True; // Графнадосохранить
MainMenu.Items[0].Items[2].Enabled:=True; // Сохранить
end;
end;
end;
// Заполнение структуры данных для отмены удаления вершины
procedure TfmMain.FillUndoDelVrx(DelVNo: Cardinal);
var VDeg: Word;
i,p: Byte;
begin
VDeg:=0; // Вычисление локальной степени удаляемой вершины
for i:=1 to VCount do
if sgMatrix.Cells[i,DelVNo] <> '' then inc(VDeg);
SetLength(UndoItem,VDeg+1);
p:=0; // Заполнение структуры для отмены удаления
UndoItem[p].VNo:=DelVNo;
UndoItem[p].VPoint:=VCenter[DelVNo-1];
for i:=1 to VCount do
if sgMatrix.Cells[i,DelVNo] <> '' then
begin
inc(p);
UndoItem[p].VNo:=i; // Сохранение данных о смежной вершине
UndoItem[p].VPoint:=VCenter[i-1];
end;
end;
// Опрограмме
procedure TfmMain.iHAboutClick(Sender: TObject);
begin
fmHelp.Tag:=2;
self.WindowState:=wsMinimized;
fmHelp.ShowModal;
self.WindowState:=wsNormal;
end;
// Запускпроцессараскраскиграфа
procedure TfmMain.btnColoringClick(Sender: TObject);
var ColorCount,i: Byte;
begin
StatusBar.SimpleText:='Раскраска...';
FillAdMatrix(AdMatrix);
fmInputk.Caption:='Выборчислацветов';
fmInputk.StaticText.Caption:='Выберите нужное число цветов из списка:';
fmInputk.btnSet.Caption:='Задать';
fmInputk.ComboBox.Items.Clear;
for i:=1 to VCount do
fmInputk.ComboBox.Items.Add(IntToStr(i));
fmInputk.Tag:=VCount;
if fmInputk.ShowModal = mrOk then
begin
InitUndo;
k:=StrToInt(fmInputk.ComboBox.Text);
// Минимальная раскраска (определение хроматического числа графа)
ColorCount:=DoMinColoring(AdMatrix,VCount,VColor);
if k < ColorCount then
MessageDlg('Раскраскавершинтекущегографа ' + IntToStr(k) +
' цветом(ами) невозможна!' + #13 + 'Необходимо не менее ' +
IntToStr(ColorCount) + ' цветов.', mtWarning, [mbOk], 0)
else // Неминимальнаяраскраска k цветами
DoNonminColoring(VCount,VColor,ColorCount,k);
RepaintAllVertices; // Перерисовкавершин
end;
StatusBar.SimpleText:='Готово';
end;
// Построение матрицы смежности по содержимому sgMatrix
procedure TfmMain.FillAdMatrix(A: TAdMatrix);
var i,j: Byte;
begin
for i:=1 to sgMatrix.RowCount-1 do
for j:=1 to sgMatrix.ColCount-1 do
A[i-1,j-1]:=StrToIntDef(sgMatrix.Cells[j,i],0);
end;
// Перерисовка текущего графа в области построения
procedure TfmMain.FormPaint(Sender: TObject);
var i,j: Byte;
VNo: String[3];
VNoWidth,VNoHeight: Word;
begin
Canvas.Pen.Color:=clBlack;
Canvas.Pen.Width:=1;
// Отображение границ области построения графа
Canvas.Brush.Color:=clBtnFace;
Canvas.Brush.Style:=bsSolid;
Canvas.Rectangle(PaintAreaXMin,PaintAreaYMin,
PaintAreaXMin + PaintAreaWidth,PaintAreaYMin + PaintAreaHeight);
Canvas.Pen.Color:=clBlack;
Canvas.Pen.Width:=1;
if MouseIsHeld and not RepaintOldEdge then
begin
// Прорисовка нового ребра, создаваемого перетаскиванием
Canvas.MoveTo(DrawnEdge.src.X,DrawnEdge.src.Y);
Canvas.LineTo(DrawnEdge.dst.X,DrawnEdge.dst.Y);
end;
// Прорисовкареберграфа
Canvas.Pen.Width:=2;
for i:=1 to VCount - 1 do
for j:=i+1 to VCount do
if sgMatrix.Cells[j,i] <> '' then
begin
Canvas.MoveTo(VCenter[i-1].X,VCenter[i-1].Y);
Canvas.LineTo(VCenter[j-1].X,VCenter[j-1].Y);
end;
// Прорисовка вершин графа с учетом назначенных цветов
Canvas.Pen.Color:=clBlack;
Canvas.Pen.Width:=1;
Canvas.Brush.Style:=bsSolid;
for i:=1 to VCount do
begin // Окружность i-йвершины
Canvas.Ellipse(VCenter[i-1].X - VRadius,VCenter[i-1].Y - VRadius,
VCenter[i-1].X + VRadius,VCenter[i-1].Y + VRadius);
if VColor[i-1] <= 0 then Canvas.Brush.Color:=clWhite
else Canvas.Brush.Color:=RealColors[VColor[i-1]-1];
Canvas.FloodFill( // Закраскаокружности
VCenter[i-1].X,VCenter[i-1].Y,Canvas.Pen.Color,fsBorder);
VNo:=IntToStr(i); // Вывод номера вершины
VNoWidth:=Canvas.TextWidth(VNo);
VNoHeight:=Canvas.TextHeight(VNo);
Canvas.TextOut(
VCenter[i-1].X - VNoWidth div 2,VCenter[i-1].Y - VNoHeight div 2,VNo);
end;
end;
// Редактирование матрицы смежности вершин графа
procedure TfmMain.sgMatrixSelectCell(Sender: TObject; ACol, ARow: Integer;
var CanSelect: Boolean);
var Colored: Boolean;
begin
CanSelect:=True;
if ACol = ARow then Exit;
InitUndo;
if sgMatrix.Cells[ACol,ARow] = '' then
begin // Добавлениеребра
sgMatrix.Cells[ACol,ARow]:='1';
sgMatrix.Cells[ARow,ACol]:='1';
end
else
begin // Удалениеребра
sgMatrix.Cells[ACol,ARow]:='';
sgMatrix.Cells[ARow,ACol]:='';
UndoItem[0].VNo:=ARow; // Заполнение структуры для отмены удаления
UndoItem[1].VNo:=ACol;
UndoItem[0].VPoint.X:=-1; // Признак одного удаленного ребра
MainMenu.Items[1].Items[0].Enabled:=True; // Undo
MainMenu.Items[1].Items[1].Enabled:=False; // Redo
end;
RepaintEdge(VCenter[ARow-1].X,VCenter[ARow-1].Y,
VCenter[ACol-1].X,VCenter[ACol-1].Y);
Colored:=ResetColoring(VCount,VColor); // Сбросцветов
if Colored then RepaintAllVertices; // Перерисовкавершин
GraphChanged:=True; // Графнужносохранить
MainMenu.Items[0].Items[2].Enabled:=True; // Сохранить
end;
// Добавление или удаление вершины графа мышью
procedure TfmMain.FormMouseUp(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
var i,j: Byte;
RemVrx: TVertices;
Colored,AddVrx: Boolean;
x0,y0: Integer;
begin
if (Button = mbLeft) and (Shift = []) then
begin
if (X < VRadius + PaintAreaXMin) or (Y < VRadius + PaintAreaYMin) or
(X > PaintAreaWidth - (VRadius + 5)) or
(Y > PaintAreaHeight - (VRadius + 5)) then
begin // За пределами области построения графа
Beep;
MouseIsHeld:=false; // Левая клавиша отпущена
MouseHeldVNo:=0;
Repaint;
Exit
end;
if MouseIsHeld then AddVrx:=False else AddVrx:=True;
i:=1;
while i <= VCount do // Проверка наложения вершин
begin
if (abs(VCenter[i-1].X - X) <= VRadius) and
(abs(VCenter[i-1].Y - Y) <= VRadius) then
begin
Colored:=ResetColoring(VCount,VColor); // Сбросцветов
if MouseHeldVNo = i then
begin // Удалениевершинысномером i
MouseHeldVNo:=0;
MouseIsHeld:=false;
x0:=VCenter[i-1].X;
y0:=VCenter[i-1].Y;
FillUndoDelVrx(i); // Сохранение информации для отмены удаления
MainMenu.Items[1].Items[0].Enabled:=True; // Undo
MainMenu.Items[1].Items[1].Enabled:=False; // Redo
RemoveVertex(i,VCount,RemVrx);
if RemVrx <> Nil then
for j:=0 to High(RemVrx) do // Перерисовка удаленных ребер
RepaintEdge(x,y,RemVrx[j].X,RemVrx[j].Y);
RepaintVertex(x0,y0); // Перерисовка удаленной вершины
RepaintAllVertices; // Перерисовка вершин после перенумерации
RemVrx:=Nil;
if VCount = 0 then
begin
sgMatrix.Visible:=False;
sgMatrix.RowCount:=1;
sgMatrix.ColCount:=1;
MainMenu.Items[0].Items[0].Enabled:=False; // Новый
btnNew.Enabled:=False;
btnColoring.Enabled:=False;
MainMenu.Items[0].Items[2].Enabled:=False; // Сохранить
MainMenu.Items[1].Items[4].Enabled:=False; // Удалитьвершину
end
else
begin
GraphChanged:=True; // Графнужносохранить
MainMenu.Items[0].Items[2].Enabled:=True; // Сохранить
end;
end
else
begin // Добавлениеребрамеждувершинами i и MouseHeldVNo
if sgMatrix.Cells[MouseHeldVNo,i] = '' then
begin
InitUndo;
sgMatrix.Cells[MouseHeldVNo,i]:='1';// Добавлениеребравматрицу
sgMatrix.Cells[i,MouseHeldVNo]:='1';
RepaintEdge(VCenter[i-1].X,VCenter[i-1].Y, // Прорисовкаребра
VCenter[MouseHeldVNo-1].X,VCenter[MouseHeldVNo-1].Y);
if Colored then RepaintAllVertices; // Перерисовкавершин
end;
MouseHeldVNo:=0;
MouseIsHeld:=false;
GraphChanged:=True; // Графнужносохранить
MainMenu.Items[0].Items[2].Enabled:=True; // Сохранить
end;
Exit
end;
inc(i);
end;
if VCount >= MaxVCount then
begin
MessageDlg('Число вершин графа не должно превышать ' +
IntToStr(MaxVCount) + '!', mtWarning, [mbOk], 0);
Exit
end;
if not AddVrx then
begin // Удерживалась клавиша мыши - вершину не добавляем
MouseIsHeld:=False;
MouseHeldVNo:=0;
RepaintEdge(DrawnEdge.src.X,DrawnEdge.src.Y, // Прорисовкаобласти
DrawnEdge.dst.X,DrawnEdge.dst.Y);
Exit;
end;
InitUndo;
inc(VCount); // Добавлениевершины
SetLength(VCenter,VCount);
SetLength(VColor,VCount);
SetLength(AdMatrix,VCount,VCount);
Colored:=ResetColoring(VCount,VColor); // Сбросцветов
sgMatrix.Visible:=True; // Изменение матрицы смежности
sgMatrix.RowCount:=VCount+1;
sgMatrix.Rows[VCount].Clear;
sgMatrix.ColCount:=VCount+1;
sgMatrix.Cols[VCount].Clear;
sgMatrix.FixedCols:=1;
sgMatrix.FixedRows:=1;
sgMatrix.Cells[VCount,0]:=IntToStr(VCount);
sgMatrix.Cells[0,VCount]:=IntToStr(VCount);
VCenter[VCount-1].X:=X; // Заданиекоординат
VCenter[VCount-1].Y:=Y;
if Colored then RepaintAllVertices // Перерисовкавершин
else RepaintVertex(X,Y);
MainMenu.Items[0].Items[0].Enabled:=True; // Новый
btnNew.Enabled:=True;
btnColoring.Enabled:=True;
GraphChanged:=True; // Граф нужно сохранить
MainMenu.Items[0].Items[2].Enabled:=True; // Сохранить
MainMenu.Items[1].Items[4].Enabled:=True; // Удалитьвершину
end;
end;
// Захватвершинылевойкнопкоймыши
procedure TfmMain.FormMouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
var i: Byte;
begin
if (Button = mbLeft) and (Shift = [ssLeft]) then
begin
i:=1;
while i <= VCount do // Проверканажатиянавершине
begin
if (abs(VCenter[i-1].X - X) <= VRadius) and
(abs(VCenter[i-1].Y - Y) <= VRadius) then
begin
MouseIsHeld:=true;
MouseHeldVNo:=i; // Номервыбраннойвершины
Exit
end;
inc(i)
end;
end;
end;
// Соединениевершинперетаскиванием
procedure TfmMain.FormMouseMove(Sender: TObject; Shift: TShiftState; X,Y: Integer);
var Rect: TRect;
begin
if MouseIsHeld then
begin
if (X < PaintAreaXMin) or (Y < PaintAreaYMin) or
(X > PaintAreaWidth) or (Y > PaintAreaHeight) then
// За пределами области построения графа
Exit;
// Очистка области, где ребро было на предыдущем шаге
Rect.Left:=min(DrawnEdge.src.X,DrawnEdge.dst.X)-3;
Rect.Right:=max(DrawnEdge.src.X,DrawnEdge.dst.X)+3;
Rect.Top:=min(DrawnEdge.src.Y,DrawnEdge.dst.Y)-3;
Rect.Bottom:=max(DrawnEdge.src.Y,DrawnEdge.dst.Y)+3;
RepaintOldEdge:=True;
InvalidateRect(Handle,@Rect,true);
Update;
DrawnEdge.src.X:=X; // Прорисовка нового ребра в следующей позиции
DrawnEdge.src.Y:=Y;
DrawnEdge.dst.X:=VCenter[MouseHeldVNo-1].X;
DrawnEdge.dst.Y:=VCenter[MouseHeldVNo-1].Y;
Rect.Left:=min(DrawnEdge.src.X,DrawnEdge.dst.X)-3;
Rect.Right:=max(DrawnEdge.src.X,DrawnEdge.dst.X)+3;
Rect.Top:=min(DrawnEdge.src.Y,DrawnEdge.dst.Y)-3;
Rect.Bottom:=max(DrawnEdge.src.Y,DrawnEdge.dst.Y)+3;
RepaintOldEdge:=False;
InvalidateRect(Handle,@Rect,true);
Update;
end;
end;
// Удалениевыбраннойвершины
procedure TfmMain.RemoveVertex(VNo: Cardinal; var VCount: byte; var RemVrx: TVertices);
var i,j,RemVCount: Byte;
begin
if VCount = 0 then Exit;
FillAdMatrix(AdMatrix); // Перезапись sgMatrix вматрицусмежности
RemVCount:=0; // Формирование массива координат центров
for i:=1 to VCount do // вершин, смежных с удаляемой
if AdMatrix[VNo-1,i-1] > 0 then
begin
inc(RemVCount);
Setlength(RemVrx,RemVCount);
RemVrx[RemVCount-1].X:=VCenter[i-1].X;
RemVrx[RemVCount-1].Y:=VCenter[i-1].Y;
end;
for i:=VNo to VCount - 1 do // Перенумерацияматрицысмежности
begin // и сдвиг массива координат центров вершин
VCenter[i-1]:=VCenter[i];
sgMatrix.Cells[i,0]:=IntToStr(i);
sgMatrix.Cells[0,i]:=IntToStr(i);
end;
j:=VNo-1; // Удаление столбца VNo
while j < VCount - 1 do
begin
for i:=0 to VCount - 1 do AdMatrix[i,j]:=AdMatrix[i,j+1];
inc(j)
end;
i:=VNo-1; // Удаление строки VNo
while i < VCount - 1 do
begin
for j:=0 to VCount - 1 do AdMatrix[i,j]:=AdMatrix[i+1,j];
inc(i)
end;
dec(VCount); // Изменение размеров структур данных
SetLength(VCenter,VCount);
SetLength(VColor,VCount);
SetLength(AdMatrix,VCount,VCount);
if VCount = 0 then begin
Exit
end;
sgMatrix.RowCount:=VCount+1; // Вершины еще остались
sgMatrix.ColCount:=VCount+1;
for i:=1 to VCount do // Восстановление измененной матрицы смежности
for j:=1 to VCount do
if AdMatrix[i-1,j-1]>0 then
begin
sgMatrix.Cells[i,j]:='1';
sgMatrix.Cells[j,i]:='1';
end
else
begin
sgMatrix.Cells[i,j]:='';
sgMatrix.Cells[j,i]:='';
end;
end;
// Перерисовкавершинынаформе
procedure TfmMain.RepaintVertex(x,y: Integer; ForceUpdate: Boolean);
var Rect: TRect;
begin
Rect.Left:=x-VRadius;
Rect.Right:=x+VRadius;
Rect.Top:=y-VRadius;
Rect.Bottom:=y+VRadius;
InvalidateRect(Handle,@Rect,true);
if ForceUpdate then Update;
end;
// Перерисовка всех вершин на форме
procedure TfmMain.RepaintAllVertices;
var i: Byte;
begin
if VCount = 0 then Exit;
for i:=0 to VCount - 1 do
RepaintVertex(VCenter[i].X,VCenter[i].Y,false);
Update;
end;
// Перерисовка ребра на форме
procedure TfmMain.RepaintEdge(x1,y1,x2,y2: Integer);
var Rect: TRect;
begin
Rect.Left:=min(x1,x2)-2;
Rect.Right:=max(x1,x2)+2;
Rect.Top:=min(y1,y2)-2;
Rect.Bottom:=max(y1,y2)+2;
InvalidateRect(Handle,@Rect,true);
Update;
end;
// Приведение вида формы к исходному состоянию
procedure TfmMain.InitForm(Repaint: Boolean);
begin
VCount:=0;
sgMatrix.Visible:=False;
sgMatrix.RowCount:=1;
sgMatrix.ColCount:=1;
stGraph.Caption:='Исходный граф: ';
if Repaint then fmMain.Repaint;
end;
// Инициализация глобальных и компонентных данных модуля
procedure TfmMain.FormActivate(Sender: TObject);
begin
Randomize;
PaintAreaXMin:=stGraph.Left;
PaintAreaYMin:=stGraph.Top + stGraph.Height;
PaintAreaWidth:=sgMatrix.Left - PaintAreaXMin;
PaintAreaHeight:=StatusBar.Top - PaintAreaYMin;
MouseIsHeld:=False;
MouseHeldVNo:=0;
RepaintOldEdge:=False;
GraphChanged:=False;
MainMenu.Items[0].Items[0].Enabled:=False; // Новый
MainMenu.Items[0].Items[2].Enabled:=False; // Сохранить
MainMenu.Items[1].Items[4].Enabled:=False; // Удалитьвершину
btnNew.Enabled:=False;
btnColoring.Enabled:=False;
StatusBar.SimpleText:='Готово';
end;
// Завершающиедействия
procedure TfmMain.FormDeactivate(Sender: TObject);
begin
AdMatrix:=Nil;
VCenter:=Nil;
VColor:=Nil;
UndoItem:=Nil;
end;
// Запросназакрытиеформы
procedure TfmMain.FormCloseQuery(Sender: TObject; var CanClose: Boolean);
begin
btnExitClick(Sender);
CanClose:=True;
end;
// Инициализация структуры данных об отмененном действии
procedure TfmMain.InitUndo;
begin
SetLength(UndoItem,2);
UndoItem[0].VNo:=0;
UndoItem[1].VNo:=0; // Блокировкапунктовменю
MainMenu.Items[1].Items[0].Enabled:=False; // Undo
MainMenu.Items[1].Items[1].Enabled:=False; // Redo
end;
procedure TfmMain.FormCreate(Sender: TObject);
begin
VCount:=0;
sgMatrix.Visible:=False;
sgMatrix.RowCount:=1;
sgMatrix.ColCount:=1;
end;
end.
unit uColoring;
implementation
uses uInputk;
var VDegree: array of ShortInt; // Массивотносительныхлокальныхстепеней
VNumber: array of Byte; // Отсортированный массив номеров вершин
Uncolored: set of Byte; // Множество не раскрашенных вершин
// Процедура сортировки массива локальных степеней методом вставки
procedure InsertionSort(var A: array of ShortInt;
var V: array of Byte; size: SmallInt);
var i1, i2, i2sav: SmallInt;
tmpA: ShortInt;
tmpV: Byte;
begin
i2 := 1; // номерсортируемогоэлемента
while i2 < size do // перебор всех элементов до крайнего справа
begin
i1 := i2 - 1; // номер элемента левой части
i2sav := i2; // запоминаем начало неотсортированной части
while i1 >= 0 do // пока не дошли до левой границы
begin
if A[i1] < A[i2] then // нужнаперестановка
begin
tmpA := A[i1]; // перестановка
A[i1] := A[i2];
A[i2] := tmpA;
tmpV := V[i1];
V[i1] := V[i2];
V[i2] := tmpV
end else break; // местодляэлементанашли
dec(i1); // идемвлево
dec(i2);
end;
i2 := i2sav + 1; // на следующий элемент
end;
end;
// Раскраска графа в минимальное число цветов
function DoMinColoring(const AdMatrix: TAdMatrix;
VCount: Cardinal; VColor: TColoring): Word;
var i,j: Byte; // Индексы для перебора вершин
CurColor: ShortInt; // Текущий цвет
VCur: Byte; // Номер текущей раскрашиваемой вершины
Colorable: Boolean; // Признак отсутствия вершин, которые
// можно раскрасить в цвет CurColor
label ColFound;
begin
result:=0;
SetLength(VDegree,VCount);
SetLength(VNumber,VCount);
Uncolored:=[]; // Считаем все вершины нераскрашенными
for i:=1 to VCount do
begin
include(Uncolored,i);
VColor[i-1]:=-1;
end;
CurColor:=1; // Начинаем с первого цвета
repeat // Цикл раскраски
for i:=1 to VCount do // Расчет относительных локальных степеней
begin
VNumber[i-1]:=i;
if VColor[i-1] < 0 then
begin
VDegree[i-1]:=0;
for j:=1 to VCount do
if VColor[j-1] < 0 then
VDegree[i-1]:=VDegree[i-1] + AdMatrix[i-1,j-1];
end
else VDegree[i-1]:=-1;
end;
// Сортировка относительных локальных степеней по неубыванию
InsertionSort(VDegree,VNumber,VCount);
Colorable:=True; // Поискираскраскаочереднойвершины
VCur:=1;
while VCur <= VCount do
begin
if VDegree[VCur-1] < 0 then break;
i:=1;
while i <= VCount do
begin
if VColor[i-1] = CurColor then
if AdMatrix[i-1,VNumber[VCur-1]-1] > 0 then
begin
inc(VCur);
break;
end;
inc(i);
end;
if i > VCount then goto ColFound;
end;
Colorable:=False; // Вершин для раскраски цветом CurColor больше нет
...Подобные документы
Разработка граф-схемы алгоритма раскраски на языке Object Pascal. Формат файла для хранения графов. Выбор удобочитаемых идентификаторов. Переменные, константы, типы, компоненты, процедуры и функции модулей uMain, uInputk, uFiling, uColoring, uHelp.
курсовая работа [1,3 M], добавлен 22.11.2013Этапы нахождения хроматического числа произвольного графа. Анализ примеров раскраски графа. Характеристика трудоемкости алгоритма раскраски вершин графа Мейниеля. Особенности графов, удовлетворяющих структуру графов Мейниеля, основные классы графов.
курсовая работа [1,1 M], добавлен 26.06.2012Математические графы, области их применения. Способы раскраски вершин и ребер графов, задачи на их применение. Разработка алгоритма, работающего на основе операций с матрицей смежности. Описание логической структуры программы. Пример зарисовки графа.
курсовая работа [145,5 K], добавлен 27.01.2013Создание многоуровневого приложения с Web-интерфейсом выставления оценки фильму и просмотра оценок других пользователей. Клиентская часть приложения. Разработка многопользовательского веб-приложения на ASP.NET MVC 3 с разграничением доступа к данным.
курсовая работа [949,7 K], добавлен 22.02.2015Характеристика объекта автоматизации. Создание многоуровневой архитектуры приложения, отладка метода безошибочной идентификации пользователей системы. Разработка нестандартного метода преобразования объектов базы данных в объекты классов приложения.
курсовая работа [395,4 K], добавлен 28.04.2015Разработка клиент-серверного приложения, позволяющего взаимодействовать друг с другом с использованием доступа к базам данных. Проектирование связи сервера с базой данных с помощью технологии ODBC. Разработка интерфейса программы, ее тестирование.
курсовая работа [352,0 K], добавлен 24.08.2016Возможности среды программирования delphi при разработке приложения с визуальным интерфейсом. Отладка программных модулей с использованием специализированных программных средств. Тестирование программного обеспечения. Оптимизация программного кода.
курсовая работа [974,0 K], добавлен 21.12.2016Основные инструменты построения Web-приложения. Язык сценариев PHP. Системный анализ предметной области базы данных. Коды SQL запросов на создание таблиц. Разработка Web-приложения. Описание функциональности модулей. Система управления содержимым статей.
курсовая работа [4,8 M], добавлен 28.04.2014Изучение возможностей среды программирования delphi при разработке приложения с визуальным интерфейсом. Отладка программных модулей с использованием специализированных средств. Способы работы с динамическими массивами. Оптимизация программного кода.
курсовая работа [1,0 M], добавлен 23.12.2016Способы построения остовного дерева (алгоритма поиска в глубину и поиска в ширину). Вид неориентированного графа. Понятие и алгоритмы нахождения минимальных остовных деревьев. Последовательность построения дерева графов по алгоритмам Крускала и Прима.
презентация [22,8 K], добавлен 16.09.2013Автоматизация системы снятия показаний счетчиков энергии. Разработка базы данных и клиентского приложения для структур жилищно-коммунального хозяйства, занимающихся составлением квитанций. Описание предметной области. Тестирование клиентского приложения.
курсовая работа [953,3 K], добавлен 01.09.2016Описание технологии asp.net. Страницы веб-приложения, тестирование системы. Описание функциональной, динамической модели системы. Диаграммы вариантов использования, последовательности, база данных приложения. Реализация программы, интерфейс, тестирование.
курсовая работа [3,2 M], добавлен 30.01.2013Возможности среды программирования delphi при разработке приложения с визуальным интерфейсом. Разработка спецификации программного обеспечения и на ее основе кода программного продукта. Отладка программы "трассировкой", ее тестирование и оптимизация.
курсовая работа [501,4 K], добавлен 07.12.2016Анализ предметной области. Диаграмма классов. Проектирование программного продукта "Часы". Тестирование и отладка, руководство программиста. Описание работы приложения. Руководство оператора, модель жизненного цикла. Файл Times.cs, Arrow.cs, Form1.cs.
курсовая работа [1,7 M], добавлен 20.04.2015Разработка программного приложения по автоматизированному учету поступающего довольствия. Описание среды программирования. Тестирование и отладка приложения. Анализ результатов решения. Инструкция пользователю. Требования к техническому обеспечению.
дипломная работа [946,0 K], добавлен 18.07.2014Разработка Web-приложения для ООО "Научно-производственная фирма по применению информационных технологий в электрических сетях". Техническое задание, проектирование процессов, создание базы данных, разработка дизайна, тестирование и отладка сайта.
дипломная работа [3,8 M], добавлен 24.06.2011Общая схема работы приложения Android. Разработка обучающего приложения для операционной системы Android, назначение которого - развитие речи посредством произнесения скороговорок. Описание компонентов разработанного приложения, его тестирование.
дипломная работа [1,2 M], добавлен 04.02.2016Фильтрация шумов изображения. Алгоритмы его бинаризации и поворота. Формирование информативных признаков для распознавания нот. Схема программного обеспечения. Описание классов, функций, методов, реализованных в программе. Тестирование приложения.
курсовая работа [2,0 M], добавлен 17.12.2013Структура базы данных web-приложения предприятия ООО "Седово"; автоматизация процесса передачи документов. Разработка технического задания, проектирование БД, функциональное назначение web-приложений, тестирование, отладка и размещение в сети Internet.
дипломная работа [5,3 M], добавлен 24.06.2011Создание, изучение и разработка приложение на Android. Среда разработки приложения DelphiXE5. Установка и настройка среды программирования. Этапы разработки приложения. Инструменты для упрощения конструирования графического интерфейса пользователя.
курсовая работа [1,6 M], добавлен 19.04.2017
