|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Детализация алгоритма раскраски графа
Разработаем граф-схему алгоритма раскраски графа по описанию, представленному в разделе «Эскизный проект» с учетом определённой выше структуры программы (см. рис.10). В граф-схеме на рис.10 использованы разработанные выше структуры данных, а также следующие дополнительные переменные: S – множество еще не раскрашенных вершин графа; f – текущий цвет; b – признак отсутствия вершин, которые можно раскрасить в цвет f;
i – индекс для перебора вершин.
Рис. 10
Разработка формата файла для хранения графов При записи графа в файл будем сохранять число его вершин и матрицу их смежности. Поскольку обрабатываемые графы неориентированные и матрицы их смежности симметричны относительно главной диагонали, в файле достаточно хранить только верхнюю треугольную часть матрицы. Для уменьшения размера файлов каждое значение матрицы смежности будем кодировать 1 битом, а всю хранимую часть матрицы представим цепочкой бит. Длина цепочки для графа, содержащего n вершин, будет равна
что нетрудно проверить непосредственно по виду матрицы. Поскольку минимальная единица информации файла это байт, указанные биты цепочки будут распределены между байтами, причем номер байта не будет соответствовать номеру вершины в общем случае. Число полных байт, необходимых для хранения матрицы смежности, в таком случае составит
где скобками
На рисунке 11 дано графическое представление хранимой в файле информации (а) и формата файла (б). Алгоритм чтения графа из файла указанного формата будет включать следующие этапы: 1. Чтение числа вершин n и проверка правильности значения. 2. Циклическое побайтовое считывание оставшейся части файла в одномерный массив, содержащий B байт. 3. Извлечение строк верхней треугольной части матрицы смежности вершин графа из указанного одномерного массива путем поразрядной обработки его элементов. 4. Доопределение матрицы смежности вершин путем симметричного отображения верхней треугольной части на нижнюю и обнуления элементов главной диагонали. Алгоритм записи графа в файл будет содержать следующие этапы: 1. Побитовое копирование строк верхней треугольной части матрицы смежности вершин в одномерный массив из B байт. 2. Запись в файл числа вершин графа n. 3. Циклическая перезапись массива с матрицей смежности в хвост файла.
(а)
(б)
РАБОЧИЙ ПРОЕКТ
Выбор удобочитаемых идентификаторов Для улучшения читаемости разрабатываемой программы выполним замену коротких символических обозначений данных, использованных в алгоритме, удобочитаемыми программными идентификаторами, построенными с учетом смысла обозначаемых ими сущностей. Принятый вариант замены представлен в таблице 1. Таблица 1
Общая организация проекта Данный проект состоит из 6-ти модулей: uMain, uData, uHelp, uFiling, uColoring, uInputk.
Описание модулей
Модуль uMain Модуль предназначен для организации редактирования обрабатываемых графов, реализации функции главного меню и координации работы остальных программных модулей. Описание пунктов меню приведено в разделе 5.1.
6.3.1.1 Основные переменные, константы и типы модуля fmMain: TfmMain – основная форма; TUndoItem – тип данных для представления информации о последнем выполненном действии над графом (используется в режимах Отмена и Восстановление); VRadius – радиус окружности вершины графа; AdMatrix: TAdMatrix – матрица смежности вершин текущего графа; VCount: Byte – число вершин текущего графа; VColor: TColoring – текущая раскраска вершин; VCenter: array of TPoint – массив координат центров вершин; UndoItem: array of TUndoItem – информация об отмененной операции; k: Byte – требуемое число цветов; GraphChanged: Boolean – признак измененного и не сохраненного графа.
6.3.1.2 Компоненты модуля Компоненты модуля uMain представлены в таблице 2. Таблица 2
Таблица 2 (продолжение)
6.3.1.3 Процедуры модуля Процедура iFOpenClick – открывает файл при выборе пункта меню «Открыть», производит очистку и переформат таблицы матрицы смежности sgMatrix. Процедура iFSaveClick – сохраняет файл при выборе пункта меню «Сохранить». Процедура btnColoringClick – запускает процесс раскраски графа. Процедура FormActivate – осуществляет инициализацию глобальных и компонентных данных модуля. Процедура btnNewClick – создает новый граф при нажатии на кнопку «Новый граф». Процедура iFNewClick – создает новый граф при выборе пункта меню «Новый». Процедура iFSaveAsClick – сохраняет граф в другом файле при выборе пункта меню «Сохранить как». Процедура iFExitClick – осуществляет выход из программы при выборе пункта меню «Выход». Процедура btnExitClick – осуществляет выход из программы при нажатии на кнопку «Выход». Процедура iEAddVClick – осуществляет добавление вершины, при этом изменяет матрицу смежности, определяет координаты новой вершины и осуществляет перерисовку вершин. Процедура iEDelVClick – открывает форму fmInputk как модальную, осуществляет удаление выбранной вершины, удаление смежных с ней ребер, сброс цветов, перенумерацию и перерисовку оставшихся вершин. Процедура iEUndoClick – осуществляет отмену последнего действия при выборе пункта меню «Отмена». Процедура iERedoClick – осуществляет восстановление последнего отмененного действия при выборе пункта меню «Восстановление». Процедура FillUndoDelVrx – осуществляет заполнение структуры данных для отмены удаления вершины. Процедура iHHelpClick – осуществляет загрузку информации из файла помощи. Процедура iHAboutClick – осуществляет загрузку информации о программе. Процедура FormDeactivate – осуществляет освобождение памяти при закрытии формы. Процедура sgMatrixSelectCell – осуществляет редактирование матрицы смежности вершин графа, сброс цветов и перерисовку вершин. Процедура FormPaint – осуществляет перерисовку текущего графа в области построения, а также отображает границы области построения графа. Процедура FormMouseUp – осуществляет добавление или удаление вершины графа при помощи мыши, при этом изменяет матрицу смежности, определяет координаты новой вершины, осуществляет перерисовку вершин после перенумерации и сброс цветов. Процедура FormMouseDown – осуществляет захват вершины левой кнопкой мыши. Процедура FormMouseMove – осуществляет соединение вершин перетаскиванием, очистку области, где ребро было на предыдущем шаге и прорисовку нового ребра в следующей позиции. Процедура FormCloseQuery – запрос на закрытие формы. Процедура InitForm – осуществляет приведение вида формы к исходному состоянию. Процедура RemoveVertex – осуществляет удаление выбранной вершины, перезапись sgMatrix в матрицу смежности, формирование массива координат центров вершин, смежных с удаляемой, перенумерацию матрицы смежности и сдвиг массива координат центров вершин, а также изменение размеров структур данных и восстановление измененной матрицы смежности. Процедура FillAdMatrix – осуществляет построение матрицы смежности по содержимому sgMatrix. Процедура RepaintVertex – осуществляет перерисовку вершины на форме. Процедура RepaintEdge – осуществляет перерисовку ребра на форме. Процедура RepaintAllVertices – осуществляет перерисовку всех вершин на форме. Процедура InitUndo – инициализирует структуру данных об отмененном действии. Процедура FillUndoDelVrx – осуществляет заполнение структуры данных для отмены удаления вершины. Процедура PrintGraphPath – осуществляет отображение пути к файлу с графом в заголовке.
6.3.1.4 Функции модуля Функция SaveRequest – вызывает запрос на сохранение графа в файле.
Модуль 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 – файл графа.
Модуль uFiling Модуль содержит функции для управления записью графов в файлы и считывание сохраненных графов из файлов.
6.3.3.1 Основные переменные, константы и типы модуля GraphFile: TGraphFile – файл для сохранения графа.
6.3.3.2 Функции модуля DoSaveFile – осуществляет сохранение графа в файле по матрице смежности. DoReadFile – осуществляет чтение графа из файла в матрицу смежности.
Модуль uColoring Модуль объединяет процедуры, функции и переменные, используемые при реализации алгоритма раскраски графа.
6.3.4.1 Основные переменные, константы и типы модуля RealColors: TRealColors – фактические цвета раскраски вершин; VDegree: array of ShortInt – массив относительных локальных степеней; VNumber: array of Byte – отсортированный массив номеров вершин; Uncolored: set of Byte – множество не раскрашенных вершин.
6.3.4.2 Процедуры модуля DoNonminColoring – осуществляет раскраску графа в NewColorCount цветов по найденной минимальной раскраске. InsertionSort – осуществляет сортировку массива локальных степеней методом вставки.
6.3.4.3 Функции модуля DoMinColoring – осуществляет раскраску графа в минимальное число цветов. ResetColoring – осуществляет обнуление массива цветов вершин графа.
Модуль uInputk Модуль содержит определение диалога для ввода количества цветов при раскраске графа, а также номера удаляемой вершины.
6.3.5.1 Основные переменные, константы и типы модуля fmInputk: TfmInputk – форма для ввода числа цветов k.
6.3.5.2 Компоненты модуля Компоненты модуля uInputk представлены в таблице 3. Таблица 3
6.3.5.3 Процедуры модуля Процедура btnSetClick – устанавливает значение k при нажатии на кнопку «Задать». Процедура btnCancelClick – игнорирует ввод k при щелчке по кнопке «Отмена». Процедура ComboBoxChange – осуществляет проверку по числу вершин. Процедура FormActivate – обнуляет поле ввода ComboBox при запуске формы ввода числа цветов.
Модуль uHelp Модуль обеспечивает отображение справочной информации и окна о программе.
6.3.6.1 Основные переменные, константы и типы модуля fmHelp: TfmHelp – форма для файла справки; HelpFileName: string = 'coloring.hlp' – имя файла справки.
6.3.6.2 Компоненты модуля Компоненты модуля uHelp представлены в таблице 4. Таблица 4
6.3.6.3 Процедуры модуля Процедура FormActivate – производит настройку внешнего вида и заполнение окна отображения текстом из файла справки или информацию о программе. Процедура FormDeactivate – восстанавливает стандартный шрифт.
Популярное:
|
Последнее изменение этой страницы: 2016-06-05; Просмотров: 779; Нарушение авторского права страницы
– номер текущей раскрашиваемой вершины; 
бит, 
байт, 
обозначена операция округления в сторону увеличения. Количество значащих (используемых) бит в последнем байте будет вычисляться по формуле: 
бит.
Рис. 11