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

Вид материала

Содержание

1 Обзор и анализ современного состояния задачи
Описание программной реализации
Список использованных источников

Подобный материал:

ВВЕДЕНИЕ

Графы являются существенным элементом математических моделей в самых разнообразных областях науки и практики. Они помогают наглядно представить взаимоотношения между объектами или событиями в сложных системах. Многие алгоритмические задачи дискретной математики могут быть сформулированы как задачи, так или иначе связанные с графами, например задачи, в которых требуется выяснить какие-либо особенности устройства графа, или найти в графе часть, удовлетворяющую некоторым требованиям, или построить граф с заданными свойствами.

Часто возникает необходимость разобраться в сложной конфигурации, в том как она устроена, каковы взаимосвязи между объектами конфигурации. Для удобства и понимая работы, структуры графов была поставлена задача, результатом которой является данный графический модуль. Данный модуль будет актуален в таких средах как:

робототехника, рабочая среда робота; для обучения робота могут использоваться алгоритмы обучения на графах;
в разработке программного обеспечения, используемого для разработки и проверки цифровых схем;
в разработке стандартного компилятора, а точнее «лексического анализатора», т.е тот компонент компилятора, который отвечает за разбивку исходного текста на такие логические единицы, как идентификаторы, ключевые слова и знаки пунктуации;
в разработке программного обеспечения для проверки систем (верификации программ);
в верификации параллельных и распределенных программных систем; система Model Checking;
model checking (проверка работы программ на определенных моделях);
в разработке программного обеспечения сетевого планирования и управления.

Разработка данного модуля была необходима для получения того, что уже разработано на текущий момент для конечных автоматов.

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

1 ОБЗОР И АНАЛИЗ СОВРЕМЕННОГО СОСТОЯНИЯ ЗАДАЧИ

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

Анализ области применения системы

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

1.1.1 Моделирование и верификация программных систем

К одной из таких сфер можно отнести моделирование и верификацию параллельных и распределенных программных систем, под названием Model Checking. Современный этап развития индустрии программных систем характеризуется значительным усложнением процесса их разработки. В то же время, существующие методы контроля качества разрабатываемых систем характеризуются:

неполной;
высокой сложностью;
недостаточной надежностью.

Данная ситуация неизбежно влечет за собой увеличение числа ошибок при разработке систем.

Требования к качеству системы отражены в стандарте International Standard ISO/IEC 9126. Отметим основные из них:

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

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

Верификация состоит из следующих частей:

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

В свою очередь математическая модель системы представляет собой граф:

вершины которого называются состояниями, и изображают ситуации (или классы ситуаций), в которых может находиться система в различные моменты времени [1];
ребра которого могут иметь метки, изображающие действия, которые может исполнять система.

Функционирование системы изображается в данной модели переходами по ребрам графа из одного состояния к другому. Если проходимое ребро имеет ветку, то эта метка изображает действие системы, исполняемое при переходе от состояния в начале ребра [1].

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

Model Checking представляет собой автоматический анализ модели, которая может быть задана:

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

Если модель не удовлетворяет спецификации, то в качестве этого факта Model Checking предъявляет опровергающее вычисление, т.е. последовательность действий модели, на которой нарушается эта спецификация.

1.1.2 Синтез и анализ графов атак

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

Исследования, связанные с построением, анализом и применением графов атак, ведутся приблизительно с 1994 года. В отечественной литературе данной тематике уделяется незначительное внимание, несмотря на то, что в зарубежных публикациях приводятся примеры эффективно работающих систем, в том числе и коммерческих [2].

Неформально, граф атак – это граф, представляющий всевозможные последовательности действий нарушителя для достижения угроз (целей). Такие последовательности действий называются трассами (путями) атак [2].

Примеры графов атак приведены ниже. Можно выделить следующие виды графов:

1) граф атак State enumeration graph (см. рис. 1.1) – в таких графах вершинам соответствуют тройки (s, d, a), где s – источник атаки, d – цель атаки, a – элементарная атака; дуги обозначают переходы из одного состояния в другое;

Рисунок 1.1 – Граф атак State enumeration graph

2) граф атак Сondition-orienteddependency graph (см. рис. 1.2) – вершинам соответствуют результаты атак, а дугам – элементарные атаки, приводящие к таким результатам;

Рисунок 1.2 – Граф атак Сondition-orienteddependency graph

3) граф атак Exploit dependency graph (см. рис. 1.3) – вершины соответствуют результатом атак или элементарным атакам, дуги отображают зависимости между вершинами – условия, необходимые для выполнения атаки и следствие атаки, например, атака RSH возможна, если нарушитель имеет привилегии суперпользователя на хосте 1 и хост 3 доверяет хосту 1. В результате атаки нарушитель получает привилегии пользователя на хосте 3.

Рисунок 1.3 – Граф атак Exploit dependency graph

1.1.3 Применение графов в робототехнике. Планирование действий. Графы планирования

Многие результаты в области искусственного интеллекта достигнуты при решении «задач для робота». Одной из таких простых в постановке и интуитивно понятных задач является задача планирования последовательности действий, или задача построения планов.

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

Граф планирования (см. рис. 1.4) состоит из последовательности уровней, которые соответствуют временным этапам в плане, где уровень 0 представляет собой начальное состояние. Каждый уровень содержит множество литералов и множество действий. Грубо говоря, литералы представляют собой то, что может быть истинным на каждом временном этапе в зависимости от действий, выполненных на предыдущих временных этапах. Также грубо говоря, действиями являются все те действия, которые могут иметь все свои предусловия выполненными на данном временном этапе в зависимости от того, какие из литералов фактически являются истинными. В этих двух определениях применяется выражение «грубо говоря», поскольку в графе планирования регистрируется только ограниченное подмножество возможных отрицательных взаимодействий между действиями; поэтому граф может давать оптимистическую оценку минимального количества временных этапов, требуемых для того, чтобы некоторый литерал стал истинным. Тем не менее, такое количество этапов в графе планирования предоставляет хорошую оценку того, насколько трудно достичь указанного литерала из начального состояния. Еще важнее то, что граф планирования определен таким образом, что может быть сформирован очень эффективно [2].

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

Рисунок 1.4 – Пример графа планирования

1.1.4 Применение графов в проверке программного обеспечения

В настоящее время при программной реализации алгоритмов логического управления технологическими процессами наряду с программируемыми логическими контроллерами все чаще используются компьютеры, предназначенные для работы в производственных условиях. Однако вне зависимости от типа управляющего вычислительного устройства в силу большой важности задач этого класса (например, при управлении ядерными реакторами) необходимо, чтобы Заказчик, Разработчик, Программист, Оператор и Контролер однозначно и полностью понимали друг друга.

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

ОПИСАНИЕ ПРОГРАММНОЙ РЕАЛИЗАЦИИ

2.1 Алгоритм работы программного продукта

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

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

Ввод формулы алгебры языков

Считывание

вводимых данных

- -- -

+

Выполнение основной работы

Работа алгоритмов

1. Алгоритм Рутисхаузера

2. Алгоритм «обратная польская нотация»

Выполнения манипуляций над полученными данными для построение графа полученного результата.
Визуальное представление графа.

Рисунок 2.1 – Общая структура первой части программного продукта

Построение графа

Ввод вершин
Ввод ребер
Ввод петель
Входы и выходы

Визуальное представление графа
Построение матрицы смежности

Рисунок 2.2 – Общая структура второй части программного продукта

2.2 Программная реализация синтаксического анализа формулы алгебры языков и построение графа.

Данная часть программного продукта как было сказано выше, основывается на обработке входящих от пользователя данных, в нашем случае формула алгебры языков (см. рис. 2.3).

Рисунок 2.3 – Ввод формулы алгебры языков

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

Результатом анализа работы алгоритмов является визуальное построение графа. Полученный граф имеет вид нисходящего двоичного дерева.

2.2.1 Реализация алгоритмов первой части программного продукта

Алгоритм Рутисхаузера.

Данный алгоритм является одним из наиболее ранних. Его особенностью является предположение о полной скобочной структуре выражения. Под полной скобочной записью выражения понимается запись, в которой порядок действий задается расстановкой скобок [5]. Неявное старшинство операций при этом не учитывается. Например:(Аv(ВС)).

Обрабатывая выражение с полной скобочной структурой, алгоритм присваивает каждому символу из строки номер уровня по следующему пpавилу:

1) если это откpывающаяся скобка или пеpеменная, то значение увеличивается на 1;

если знак опеpации или закpывающаяся скобка, то уменьшается на 1.

Для выражения ((Аv(ВС)) присваивание значений уровня будет происходить так как представлено на рисунке 2.4.

N симв	1 2 3 4 5 6 7 8 9
Символы строки	( А v ( В С ) )
	1 2 1 2 3 2 3 2 1

Рисунок 2.4 – Представление работы алгоритма Рутисхаузера

Алгоритм складывается из следующих шагов:

1) выполнить расстановку уровней;

2) выполнить поиск элементов строки с максимальным значением уровня;

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

Пример разбора представлен на рисунке 2.5.

Генерируемые точки	Выражение
	( А v ( В С ) ) 1 2 1 2 3 2 3 2 1
B C -> R	( A v R ) 1 2 1 2 1
A v R - > T	T

Рисунок 2.5 – Пример разбора

Но в нашем случае данный алгоритм будет выполнять задание подсчитывания уровня вложенности. Что нам будет необходимо для корректного визуального отображения графа, который будет результатом работы анализа. Основная же работа синтаксического анализа ложится на алгоритм «обратная польская нотация».

Алгоритм «Обратная польская нотация».

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

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

Например, рассмотрим вычисление выражения ABvR (эквивалентное выражение в инфиксной нотации: ((AvB)R)).

Первый по порядку знак операции – «», поэтому первой выполняется операция над операндами 1 и 2 (они имеют приоритет скобочек). Выражение при этом преобразуется к виду AB v .

Второй знак операции – «». Выполняется операция вычитания над операндами 3 и (1,2).

Вычисление закончено. Результатом является запись такого вида: ABvR.

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

Особенности обратной польской записи следующие.

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

В листинге программного продукта реализация данных алгоритмов вмещена в один метод – PolskaNotation().

private void PolskaNotation()

{

String str = txt_reg_value.Text;

string[,] str_arr = new string[str.Length, 2];

string smb = "v()*";

string tmp;

List stack = new List();

int index = 0;

foreach (string token in Token(str))

{

if (!token.Trim().Equals(""))

{

tmp = token.Trim();

if (smb.IndexOf(tmp) >= 0)

{

if (tmp == ")")

{

art--;

while (stack[stack.Count - 1] != "(")

{

answer.Add(stack[stack.Count - 1]);

key.Add(index.ToString());

stack.RemoveAt(stack.Count - 1);

}

stack.RemoveAt(stack.Count - 1);

}

else

{

if (tmp == "(")

index++;

else

art--;

stack.Add(tmp);

}

}

else

{

index++;

answer.Add(tmp);

key.Add(index.ToString());

}

}

}

if (stack.Count > 0)

{

while (stack.Count > 0)

{

answer.Add(stack[stack.Count - 1]);

art--;

key.Add(index.ToString());

stack.RemoveAt(stack.Count - 1);

}

}

}

2.2.2 Формула как регулярное выражение

Как было сказано выше, что при работе с графами можем опираться на работу с автоматами, так как они имеют тесную связь с графами и в свою очередь для автоматов уже реализованы типичные задачи. Так формулы алгебры языков – это те же регулярные выражения. А при работе с регулярными выражениями вида: (avb), (ab), a*, где а и b – любые регулярные выражения, результатом тоже будет регулярное выражение.

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

Одиночный символ, представляется как вершина графа (см. рис. 2.6).

Рисунок 2.6 – Представление одиночного символа

Объединение двух регулярных выражений a и b, т.е. avb. Если a и b являются началом каких либо ветвей, то нам необходимо правильно их объединить. Первым шагом будет расщепление данного выражение на два мира (см. рис. 2.7).

….

….

Рисунок 2.7 – Объединение двух регулярных выражений

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

2.2.3 Визуальное построение графа

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

Существует достаточно много алгоритмов работы с древовидными структурами, в которых часто встречается понятие обхода (traversing) дерева или «прохода» по дереву. При таком методе исследования дерева каждый узел посещается только один раз, а полный обход задает линейное упорядочивание узлов, что позволяет упростить алгоритм, так как при этом можно использовать понятие «следующий» узел. т.е. узел стоящий после данного при выбранном порядке обхода.

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

Каждый узел посещается до того, как посещены его потомки. Для корня дерева рекурсивно вызывается следующая процедура:

– посетить узел;

– обойти левое поддерево;

– обойти правое поддерево.

Работа данного метода выполняется следующим кодом:

private bool RecursRAzbor(int index_item, int index_start, int level,int parent_num, Point start_point, int yy, int ll)

{

bool res = false;

level += level;

yy += 100;

if (YY < yy)

YY = yy;

ll += 1;

int par = parent_num;

int rast = 0;

try

{

rast = (int)panel1.Width / (coun_level[ll] + 1);

}

catch (Exception er)

{ }

int ind = 1;

for (int i = index_start; i < answer.Count; i++)

{

if (key[i].Equals((index_item + 1).ToString()))

{

//--------POINT--------------------------------

if (!diction.ContainsKey(par))

{

point.X = rast;

diction.Add(par, point.X);

}

else

{

point.X = rast + diction[par];

diction[par] = point.X;

}

point.Y = yy;

points.Add(point);

strr.Add(answer[i]);

//----------Create list of lines---------------

lines_s.Add(start_point);

lines_f.Add(point);

//---------------------------------------------

res = true;

RecursRAzbor(index_item + 1, main_index, level, parent_num+1,point,yy,ll);

main_index = i + 1;

ind++;

continue;

}

if (key[i].Equals((index_item - 1).ToString()) || key[i].Equals((index_item).ToString()))

{

break;

} }

if (res)

return true;

else

{ count_last_child++;

return false; } }

2.3 Программная реализация построение графа и матрицы смежности

2.3.1 Ввод графа и построение матрицы смежности

Принцип работы второй части программного продукта заключается в разработке графического потсроителя графов. Для реализации данной задачи мною был использован набор программных средств GDI+, которые совместно с C# реализуют данную проблему [3].

GDI+ (Graphic Device Interface+ – Интерфейс Графических Устройств) – это подсистема Microsoft Windows XP, обеспечивающая вывод графической информации на экраны и принтеры. GDI+ является преемником GDI, интерфейса графических устройств, включаемого в ранние версии Windows. Интерфейс GDI+ изолирует приложение от особенностей конкретного графического оборудования. Такая изоляция позволяет разработчикам создавать аппаратно-независимые приложения. Взаимодействию GDI и C# посвящена эта лекция [4].

GDI+ – это набор программных средств, которые используются в .NET.

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

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

2.3.2 Метод отрисовки «Битовая карта»

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

Для избегания данной проблемы, я использовал технику рисования «Битовая карта как поверхность рисования».

«Битовая карта» – это рисования на невидимых виртуальных поверхностях и в буквальном смысле в оперативной памяти.

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

Демонстрация предварительно нарисованной в памяти картинки происходит при помощи элемента управления типа PictureBox, который благодаря свойству объекта Image обеспечивает быстрое отображение выводимой графической информации.

2.3.3 Разработка элементов для построения графа

Графический элемент графа – вершина графа изображен на рисунке 2.8.

Рисунок 2.8 – Визуальное реализация вершины графа

Для визуального представления данного элемента графа мною был разработан класс Element (см. рис. 2.9), который наследует свойства класса Usercontrol.

Визуальная отрисовка проводилась при помощи GDI, а именно методом DrawEllipse.

Так как данный класс наследует свойства usercontrol, то в данном классе мы можем использовать присущие контролу методы. Сюда можно отнести набор событий:

OnPaintBackground – необходим нам для визуального изменения внешнего вида элемента; данное событие отрабатывается в тот момент когда пользователь выполняет манипуляции над элементом;
ОnMouseUp,OnMouseDown,OnMouseMove – данные события нам необходимы при отработке перемещения пользователем выбранного элемента.

Для удобной работы с кучей элементов на рабочей области, каждому элементу присваивается его индекс, цвет (пожеланию пользователя), подпись, и координаты. В связи с этим были разработаны методы, делающие работу полноценной:

getcolor – получение текущего цвета вершины;
getindex – получение индекса элемента, данный метод необходим, при соединении двух вершин ребром, это в свою очередь дает качественную привязку ребра к вершинам и задет индекс самого ребра;
getposition – необходим для получения текущих координат вершины; этот метод был реализован для задания координат соединяющего ребра, петли, входа или выхода;
gettext – получение подписи вершины.

Ребро графа.

Для визуального представления данного элемента графа мною был разработан класс Line (см. рис. 2.12).

Рисунок 2.9 – Структура класса Element

Визуальная отрисовка проводилась при помощи GDI, а именно методом DrawLine.

Данный класс предоставляет возможность визуального отображения однонаправленного (см. рис. 2.10) и двунаправленного ребра (см. рис. 2.11).

Рисунок 2.10 – Однонаправленное ребро

Рисунок 2.11 – Двунаправленное ребро

Для использования данного элемента, мною были разработаны следующие методы, которые делают работу полноценной:

DrawOneWay – метод выполняющий отрисовку однонаправленного ребра;
DrawTwoWay – метод выполняющий отрисовку двунаправленного ребра;
DrawStrelki –данный метод выполняет отрисовку стрелок, которые показывают направление ребра;
getElementStart, getElementEnd – для визуального представления ребер, в конструктор данного класса, передаются ссылки на классы елементов «вершины», между которыми происходит соединения. Если необходимо провести удаление вершины, то методом перебора мы выполняем проверку принадлежности ребра вершине. При возвращении результата, что ребро относится к данной вершине, происходит его удаление;
getIndex – метод возвращающий текущий индекс ребра. Индекс ребра формируется слиянием индексов вершин графа, между которыми проведено ребро соединения.

Рисунок 2.12 – Структура класса Line

Петля графа.

Для визуального представления данного элемента графа мною был разработан класс Petla (см. рис. 2.14).

Визуальная отрисовка проводилась при помощи GDI, а именно методом DrawBezier.

Данный класс предоставляет возможность визуального отображения петли в вершине графа(см. рис. 2.13).

Рисунок 2.13 – Элемент графа петля

Для использования данного элемента, мною были разработаны следующие методы, которые делают работу полноценной:

Draw – метод выполняющий отрисовку петли;
getIndex – метод возвращающий текущий индекс петли; индекс ребра равен индексу вершины к которой относится петля.

Рисунок 2.14 – Структура класса Petla

Входы и выходы графа.

Для визуального представления данного элемента графа мною был разработан класс InOutLine (см. рис. 2.15).

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

Рисунок 2.15 – Структура класса inOutLine

Для использования данного элемента, мною были разработаны следующие методы, которые делают работу полноценной:

Draw – метод выполняющий отрисовку данных элементов;
getIndex – метод возвращающий текущий индекс входа или выхода; индекс входа или выхода равен индексу вершины к которой относятся данный элементы.

Рисунок 2.16 – Входы и выходы

2.3.4 Реализация построения матрицы смежности

Построение матрицы смежности предсталенно классом DataGrid (см. рис. 2.17). Данный класс выполняет обработку стандартного визуального компонента (имитация матрицы смежности) DatagridView.

Построение матрицы смежности (см. рис 2.18) происходит относительно общему построению графа. При добавлении вершины графа происходит отработка метода Add() класса DataGrid. Результатом работы является визуальное добавление колонки и строки в визуальный компонент Datagridview.

В данный метод передается два параметра: ссылка на текущий элемент datagridview и ссылка на класс текущей вершины.

Для работы с данным элементом были разработаны следующие методы.

Add – происходит добавление строки и столбца в «матрицу». Так как мы работаем со стандартным элементом datagfridview, то добавление строки и столбца будет осуществляться созданием экземпляра класса DataGridViewRow, который описывает строку. Строка в свою очередь будет добавлена в список строк класса Datagriview, на который мы имеем ссылку. Колонка добавляется таким же принципом, но без создания екземплряра класса, происходит добавление в список колонок параметров от класса выбранной вершины Ellement.
СlearCell – очистка выбранной ячейки.
DeleteWrite – данный метод необходим для удаления строки и столбца. Данное удаление связано с удалением какого либо элемета графа, от которого зависит структура матрицы смежности.
InsertIntoCell – данный метод необходим для записи данных в матрицу смежности, в тот момент когда происходит добавление петли в графе.

Рисунок 2.17 – Структура класса Datagrid

Рисунок 2.18 – Визуальное представление матрицы смежности

ВЫВОДЫ

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение / Евстигнеев В.А. – СПб. : БХВ-Петербург, 2003. – 1104 с.
Зыков А.А. Основы теории графов / Зыков А.А. – М. : Наука, 1987. – 384 c.
Джеффри Рихтер. CLR via C#. Программирование на платформе Microsoft NET Framework 2.0 на языке C#. Мастер-класс / Джеффри Рихтер: [пер. с англ.]. – М. : Русская Редакция , 2007. – 656 с.
Шилдт Герберт. Полный справочник по С# / Шилдт Герберт: [пер. с англ.]. – М. : Вильямс, 2004. – 752 с.
Мозговой М.В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход / Мозговой М.В. – СПб. : Наука и техника, 2006. – 320 с.
Джон Хопкрофт. Введение в теорию автоматов, языков и вычислений, / Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман: [пер. с англ.]. – [2-е изд.] – М. : Вильямс, 2002. – 528 с.

Blog

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

Содержание

ВВЕДЕНИЕ