Разработка приложения для поиска максимально удалённых вершин в графе
Федеральное государственное бюджетное образовательное учреждение высшего
профессионального образования «Сибирская государственная автомобильно-дорожная
академия
Факультет Информационные системы в управлении
Специальность Информационная безопасность
Кафедра Информационная безопасность
Пояснительная записка к курсовой работе
«Разработка приложения для поиска максимально удалённых вершин в графе»
Выполнил: Галкин Кирилл Андреевич
Проверил Толкачёва Елена Викторовна
Омск - 2013
Содержание
Введение
. Теория
графов
.1
Ориентированный граф
.2 Смешанный
граф
.3 Изоморфные
графы
.4 Прочие
связанные определения
.5
Дополнительные характеристики графов
.6 Обобщение
понятия графа
.7 Способы
представления графа в информатике
. Техническая
реализация
.1 Алгоритм
поиска пути
.2 Классы и
диаграмма классов
.3 Методы
класса GraphEdge
.4 Методы
класса GraphNode
.5 Функции
класса Graph
.6 Методы
класса GraphMaxDistanceFinder
.7
Графический интерфейс
Заключение
Список
литературы
Введение
Появление компьютеров стало прорывом для всего человечества. В настоящее
время с помощью них возможно производить расчёты с огромной скоростью. Они
позволяют решать разнообразные задачи, одной из которых является поиск и
составление путей от пункта А в пункт Б. Для таких задач наиболее применима
теория графов.
Целью данной курсовой работы является разработка программного продукта
для поиска максимально удалённых вершин в графе. Программный продукт должен
иметь графический интерфейс и поддерживать любые типы графов.
Приложение разработано с помощью языка программирования Microsoft Visual C#, так как функционал данного языка программирования
позволяет максимально быстро решить задачи такого типа. Выбранный нами язык
программирования работает с библиотекой Microsoft .net framework, которая включает в себя огромное
количество средств для работы с данными такого рода и позволяет значительно
ускорить процесс создания приложения.
В качестве среды разработки, была использована среда Microsoft Visual Studio версии 12, так как данная среда включает в себя
широкий набор инструментов для управления и создания различных компонентов
программного продукта (графический интерфейс, диаграмма классов и т.п.)
1. Теория графов
Граф - это совокупность непустого множества вершин и наборов пар вершин
(связей между вершинами). Объекты представляются как вершины, или узлы графа, а
связи - как дуги, или рёбра. Для разных областей применения виды графов могут
различаться направленностью, ограничениями на количество связей и
дополнительными данными о вершинах или рёбрах. Многие структуры, представляющие
практический интерес в математике и информатике, могут быть представлены
графами. Например, строение "Википедии" можно смоделировать при
помощи ориентированного графа (орграф), в котором вершины - это статьи, а дуги
(ориентированные рёбра) - гиперссылки.
Теория графов не обладает устоявшейся терминологией. В различных статьях
под одними и теми же терминами понимаются разные вещи. Ниже приведены наиболее
часто встречаемые определения.
Граф, или неориентированный граф G - это упорядоченная пара G := (V, E),
для которой выполнены следующие условия:- это непустое множество вершин или
узлов;- это множество пар (в случае неориентированного графа - неупорядоченных)
вершин, называемых рёбрами.(а значит и, E, иначе оно было бы мультимножеством)
обычно считаются конечными множествами. Многие хорошие результаты, полученные
для конечных графов, неверны (или каким-либо образом отличаются) для
бесконечных графов. Это происходит потому, что ряд соображений становится ложным
в случае бесконечных множеств.
Вершины и рёбра графа называются также элементами графа, число вершин в
графе |V| - порядком, число рёбер |E| - размером графа.
Вершины u и v называются концевыми вершинами (или просто концами) ребра
e=\{u,v\}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины
одного и того же ребра называются соседними.
Два ребра называются смежными, если они имеют общую концевую вершину.
Два ребра называются кратными, если множества их концевых вершин
совпадают.
Ребро называется петлёй, если его концы совпадают, то есть e=\{v,v\}.
Степенью degV вершины V называют количество инцидентных ей рёбер (при
этом петли считают дважды).
Вершина называется изолированной, если она не является концом ни для
одного ребра; висячей (или листом), если она является концом ровно одного
ребра.
программный
граф изоморфный интерфейс
1.1 Ориентированный граф
Ориентированный граф (сокращённо орграф) G - это упорядоченная пара G :=
(V, A), для которой выполнены следующие условия:
· V - это непустое множество вершин или узлов,
· A - это множество (упорядоченных) пар различных вершин,
называемых дугами или ориентированными рёбрами.
Дуга - это упорядоченная пара вершин (v, w), где вершину v называют
началом, а w - концом дуги. Можно сказать, что дуга v - w ведёт от вершины v к
вершине w.
1.2 Смешанный граф
Смешанный граф G - это граф, в котором некоторые рёбра могут быть
ориентированными, а некоторые - неориентированными. Записывается упорядоченной
тройкой G := (V, E, A), где V, E и A определены так же, как выше.
Ориентированный и неориентированный графы являются частными случаями
смешанного.
1.3 Изоморфные графы
Граф G называется изоморфным графу H, если существует биекция f из
множества вершин графа G в множество вершин графа H, обладающая следующим
свойством: если в графе G есть ребро из вершины A в вершину B, то в графе H
должно быть ребро из вершины f(A) в вершину f(B) и наоборот - если в графе H
есть ребро из вершины A в вершину B, то в графе G должно быть ребро из вершины
f^{-1}(A) в вершину f^{-1}(B). В случае ориентированного графа эта биекция
также должна сохранять ориентацию ребра. В случае взвешенного графа биекция
также должна сохранять вес ребра.
1.4 Прочие связанные определения
Путём (или цепью) в графе называют конечную последовательность вершин, в
которой каждая вершина (кроме последней) соединена со следующей в
последовательности вершин ребром.
Ориентированным путём в орграфе называют конечную последовательность
вершин v_i (i=1,\ldots,k), для которой все пары (v_i, v_{i+1}) (i=1,... k-1)
являются (ориентированными) рёбрами.
Циклом называют путь, в котором первая и последняя вершины совпадают. При
этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим,
что если вершины u и v являются концами некоторого ребра, то согласно данному
определению, последовательность (u,v,u) является циклом. Чтобы избежать таких
«вырожденных» случаев, вводят следующие понятия. Путь (или цикл) называют
простым, если ребра в нём не повторяются; элементарным, если он простой и
вершины в нём не повторяются. Несложно видеть, что:
· Всякий путь, соединяющий две вершины, содержит элементарный
путь, соединяющий те же две вершины.
· Всякий простой неэлементарный путь содержит элементарный
цикл.
· Всякий простой цикл, проходящий через некоторую вершину (или
ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или
ребро).
· Петля - элементарный цикл.
Бинарное отношение на множестве вершин графа, заданное как «существует
путь из u в v», является отношением эквивалентности и, следовательно, разбивает
это множество на классы эквивалентности, называемые компонентами связности
графа. Если у графа ровно одна компонента связности, то граф связный. На
компоненте связности можно ввести понятие расстояния между вершинами как
минимальную длину пути, соединяющего эти вершины.
Всякий максимальный связный подграф графа G называется связной
компонентой (или просто компонентой) графа G. Слово «максимальный» означает
максимальный относительно включения, то есть не содержащийся в связном подграфе
с большим числом элементов
Ребро графа называется мостом, если его удаление увеличивает число
компонент.
1.5 Дополнительные характеристики графов
Граф называется:
· связным, если для любых вершин u,v есть путь из u в v.
· сильно связным или ориентированно связным, если он
ориентированный, и из любой вершины в любую другую имеется ориентированный
путь.
· деревом, если он связный и не содержит простых циклов.
· полным, если любые его две (различные, если не допускаются
петли) вершины соединены ребром.
· двудольным, если его вершины можно разбить на два
непересекающихся подмножества V_1 и V_2 так, что всякое ребро соединяет вершину
из V_1 с вершиной из V_2.
· k-дольным, если его вершины можно разбить на k
непересекающихся подмножества V_1, V_2, …, V_k так, что не будет рёбер,
соединяющих вершины одного и того же подмножества.
· полным двудольным, если каждая вершина одного подмножества
соединена ребром с каждой вершиной другого подмножества.
· планарным, если граф можно изобразить диаграммой на плоскости
без пересечений рёбер.
· взвешенным, если каждому ребру графа поставлено в
соответствие некоторое число, называемое весом ребра.
· хордальным, если граф не содержит индуцированных циклов с
длиной больше трех.
Также бывает:
· k-раскрашиваемым
· k-хроматическим
.6 Обобщение понятия графа
Простой граф является одномерным симплициальным комплексом.
Более абстрактно, граф можно задать как тройку (V, E, φ), где V и E - некоторые множества
(вершин и рёбер, соотв.), а φ - функция инцидентности (или
инцидентор), сопоставляющая каждому ребру e ϵ E (упорядоченную или
неупорядоченную) пару вершин u и v из V (его концов). Частными случаями этого
понятия являются:
· ориентированные графы (орграфы) - когда φ
(e) всегда является
упорядоченной парой вершин; неориентированные графы - когда φ
(e) всегда является
неупорядоченной парой вершин;
· смешанные графы - в котором встречаются как ориентированные,
так и неориентированные рёбра и петли;
· Эйлеровы графы - граф в котором существует циклический
эйлеров путь (Эйлеров цикл).
· мультиграфы - графы с кратными рёбрами, имеющими своими
концами одну и ту же пару вершин;
· псевдографы - это мультиграфы, допускающие наличие петель;
· простые графы - не имеющие петель и кратных рёбер.
Под данное выше определение не подходят некоторые другие обобщения:
· гиперграф - если ребро может соединять более двух вершин.
· ультраграф - если между элементами x_i и u_j существуют
бинарные отношения инцидентности.
.7 Способы представления графа в информатике
Матрица смежности
Таблица, где как столбцы, так и строки соответствуют вершинам графа. В
каждой ячейке этой матрицы записывается число, определяющее наличие связи от
вершины-строки к вершине-столбцу (либо наоборот). Недостатком являются
требования к памяти, прямо пропорциональные квадрату количества вершин.
· Двумерный массив;
· Матрица с пропусками;
· Неявное задание (при помощи функции).
Матрица инцидентности
Каждая строка соответствует определённой вершине графа, а столбцы
соответствуют связям графа. В ячейку на пересечении i-ой строки с j-м столбцом матрицы
записывается:
· 1, в случае, если связь j «выходит» из вершины i,
· −1, если связь «входит» в вершину,
· 0, во всех остальных случаях (то есть если связь является
петлёй или связь не инцидентна вершине)
Данный способ является самым ёмким (размер пропорционален |E| |V|) для
хранения, но облегчает нахождение циклов в графе.
Список рёбер
Список рёбер - это тип представления графа, подразумевающий, что каждое
ребро представляется двумя числами - номерами вершин этого ребра.
2. Техническая реализация
.1 Алгоритм поиска пути
Для реализации алгоритма поиска наиболее удалённых вершин в графе было
рассмотрено два способа решения данной задачи, и выбран более оптимальных из
представленных ниже.
) Подвесим дерево за какую-нибудь вершину неединичной степени. Тогда
рассмотрим, как будет устроен самый длинный путь - он будет от некоторого листа
подниматься до некоторой вершины, после чего опускаться до другого листа. В нем
есть некоторая самая высокая вершина (будем называть ее «переломной»), и он
распадается на два подпути, каждый из которых идет снизу вверх, и эти пути в
своих под-деревьях являются самыми длинными.
Из вершины, за которую мы довесили дерево, запустим процедуру обхода в
глубину. Пусть эта процедура для каждой вершины возвращает длину самого
длинного пути от этой вершины до некоторого листа (на рисунке около каждой
вершины написано значение, которое вычислить эта процедура). Понятно, что
процедура обхода в глубину это значение может легко вычислять (как максимум из
аналогичных значений для поддеревьев плюс 1). Помимо этого, обход в глубину
будет вычислять длину самого длинного пути, в которой данная вершина является
«переломной» (и запоминать наибольшее найденное значение в некоторой глобальной
переменной). Нужно найти два поддерева с наибольшими длинами наибольших путей,
просуммировать эти длины и добавить к ним 2 (ребра отданной вершины до вершин,
где начинаются эти деревья). На приведенном рисунке «переломной» для самого
длинного пути будет вершина, помеченная звездочкой, а длина самого длинного
пути равна 4 + 5 + 2. Сложность алгоритма равна сложности обхода в глубину и
при хранении графа списком ребер, выходящих из каждой вершины, достигает O(N
+M), а в дереве, как известно, M = N −1, и, тем самым, сложность равна
O(N).
Недостатком этого метода является то, что путь можно вычислить только от
той вершины, за которую подвешен граф. Поэтому для выполнения задания был
рассмотрен и использован второй алгоритм.
) Для начала необходимо запустить процедуру обхода графа в глубину. После
выполнения этого действия мы имеет длину пути от каждой одной вершины до каждой
другой. Затем сравниваем пути между всеми парами вершин между собой и находим
максимально длинный путь между двумя вершинами.
Преимущества алгоритма заключает в скорости работы и универсальность его
работы для разных типов графов. Однако, программа требует сравнительно больше
оперативной памяти, чем при использовании первого алгоритма.
2.2 Классы и диаграмма классов
При разработке программного продукта, были реализованы следующие классы: GraphNode - реализует вершину графа;
· GraphEdge - реализует ребро графа;
· Graph - реализует работу с графом (создание/удаление вершин
и ребер, получение информации о них, графическое отображение графа, его
сохранение в файл и загрузка из файла);
· GraphPathFinder - реализует поиск кратчайшего пути в
графе и графическое отображение графа с найденным путем.
Диаграмма классов:
2.3 Методы класса GraphEdge
. В конструктор класса передаются индексы вершин, связанных данным
ребром:
public GraphEdge(int n1, int n2)
node1 = n1;
node2 = n2;
2. GetLinkedNodes - устанавливает значения переданных
в метод параметров, в соответствии с индексами вершин, связанных данным ребром:
public void GetLinkedNodes(out int n1, out
int n2)
{
n1 = node1;
n2 = node2;
}
2.4 Методы класса GraphNode
. В конструктор класса передаются координаты вершины, по которым данная
вершина будет отображаться на форме, а также, необязательный параметр, отвечающий
за видимость вершины на форме (по умолчанию, вершина будет видимой):
public GraphNode(int _x, int _y, bool
_isValide = true)
{
x = _x;
y = _y;
isValide = _isValide;
}
. Методы GetPostionX и GetPositionY возвращают X и Y
координаты вершины соответственно:
public int GetPositionX()
{
return x;
}int GetPositionY()
{
return y;
}
. Метод IsExists возвращает видимость вершины:
public bool isExists()
{
return isValide;
}
. Метод Remove удаляет вершину (устанавливает
координаты равными -1, а также устанавливает видимость вершины в false):
public void Remove()
{
x = -1;
y = -1;
isValide = false;
}
2.5 Функции класса Graph
. В конструктор класса передаются имена файлов изображений для вершин.
Конструктор инициализирует списки с вершин и ребер, затем вызывается функция LoadResources:
public Graph(string nodeImage, string
nodeOkImage)
{
nodes = new List<GraphNode>();
edges = new List<GraphEdge>();
LoadResources(nodeImage, nodeOkImage);
}
. Метод Clear отвечает за очистку списков ребер и
вершин:
public void Clear()
{
nodes.Clear();
edges.Clear();
}
. Метод Draw отвечает за графическое отображение
графа на переданном в функцию графическом контексте:
public void Draw(ref Graphics g)
{
Pen pen = new Pen(Color.Black, 5);
for (int i = 0; i < edges.Count; i++)
{
Point xFrom, xTo;
int node1, node2;
edges[i].GetLinkedNodes(out node1, out
node2);
xFrom = new
Point(nodes[node1].GetPositionX(), nodes[node1].GetPositionY());
xTo = new Point(nodes[node2].GetPositionX(),
nodes[node2].GetPositionY());
g.DrawLine(pen, xFrom, xTo);
}
for (int i = 0; i < nodes.Count; i++)
{
GraphNode node = nodes[i];
if (node.isExists())
{
bool isOkNode = false;
foreach (GraphEdge edge in edges)
{
int node1, node2;
edge.GetLinkedNodes(out node1, out node2);
if (node1 == i || node2 == i)
{
isOkNode = true;
break;
}
}
if (isOkNode)
g.DrawImage(imgOkNode, node.GetPositionX() -
imageCenter, node.GetPositionY() - imageCenter);
else
g.DrawImage(imgNode, node.GetPositionX() -
imageCenter, node.GetPositionY() - imageCenter);
g.DrawString((i + 1).ToString(), font,
Brushes.Black, node.GetPositionX() - 12, node.GetPositionY() - 12);
}
}
}
4. Метод EdgeAdd связывает
вершины, имеющие указанные индексы (переданные в метод в качестве параметров),
если вершины до этого еще не были связаны:
public int EdgeAdd(int node1, int node2)
{
bool canLink = true;
foreach (GraphEdge edge in edges)
{
int n1, n2;
edge.GetLinkedNodes(out n1, out n2);
if ((n1 == node1 || n1 == node2) &&
(n2 == node1 || n2 == node2))
{
canLink = false;
break;
}
}
if (canLink)
{
edges.Add(new GraphEdge(node1, node2));
return edges.Count - 1;
}
return -1;
}
. Метод EdgeRemove удаляет ребро с заданным индексом:
public bool EdgeRemove(int id)
{
if (edges.Count > id &&
edges.Count > -1)
{
edges.RemoveAt(id);
}
return false;
}
. Метод Load служит для загрузки графа из файла с
заданным именем, передающимся в качестве параметра:
public bool Load(string filename)
{
FileStream fs = new FileStream(filename,
FileMode.Open, FileAccess.Read);
BinaryReader r = new BinaryReader(fs);
string sign = r.ReadString();
if (sign.Equals(signature,
StringComparison.InvariantCulture))
{
Clear();
int nodeCount = r.ReadInt32();
int edgeCount = r.ReadInt32();
for (int i = 0; i < nodeCount; i++)
{
bool isValide = r.ReadBoolean();
NodeAdd(r.ReadInt32(), r.ReadInt32(),
isValide);
}
for (int i = 0; i < edgeCount; i++)
{
EdgeAdd(r.ReadInt32(), r.ReadInt32());
}
r.Close();
return true;
}
r.Close();
return false;
}
. Метод LoadResources загружает изображения вершин из
заданных файлов картинок формата "png":
public void LoadResources(string nodeImage,
string nodeOkImage)
{
imgNode = Image.FromFile(nodeImage);
imgOkNode = Image.FromFile(nodeOkImage);
imageCenter =
(int)Math.Round((float)imgOkNode.Width / 2);
font = new Font("Times New Roman",
14, FontStyle.Bold);
}
. Метод NodeAdd добавляет вершину с указанными
координатами и видимостью в граф:
public int NodeAdd(int x, int y, bool
isValide = true)
{
nodes.Add(new GraphNode(x, y, isValide));
return nodes.Count - 1;
}
. Метод NodeGetID возвращает индекс вершины,
находящейся под курсором мыши, либо -1, если под курсором нет вершин:
public int NodeGetID(int mouseX, int mouseY)
{
for (int i = 0; i < nodes.Count; i++)
{
int nX = nodes[i].GetPositionX() - 16;
int nY = nodes[i].GetPositionY() - 16;
if (mouseX >= nX && mouseX <=
nX + imgOkNode.Width)
if (mouseY >= nY && mouseY <=
nY + imgOkNode.Height)
return i;
}
return -1;
}
. Методы NodeGetX и NodeGetY возвращает x и y
координаты указанной вершины соответственно:
public int NodeGetX(int id)
{
if (id < nodes.Count &&
nodes.Count > -1)
{
return nodes[id].GetPositionX();
}
return -1;
}
public int NodeGetY(int id)
{
if (id < nodes.Count &&
nodes.Count > -1)
{
return nodes[id].GetPositionY();
}
return -1;
}
. Метод NodeRemove удаляет указанную вершину из графа
(также, удаляет все ребра, связанные с вершиной):
public bool NodeRemove(int id)
{
if (nodes.Count > id &&
nodes.Count > -1)
{
List<int> toRemove = new
List<int>();
for (int i = 0; i < edges.Count; i++)
{
int node1, node2;
edges[i].GetLinkedNodes(out node1, out
node2);
if (node1 == id || node2 == id)
toRemove.Add(i);
}
while (toRemove.Count > 0)
{
EdgeRemove(toRemove[0]);
toRemove.RemoveAt(0);
for (int i = 0; i < toRemove.Count; i++)
{
toRemove[i] -= 1;
}
}
nodes[id].Remove();
return true;
}
return false;
}
. Метод NodeSetPosition устанавливает координаты заданной
вершины:
public bool NodeSetPosition(int id, int x,
int y)
{
if (id < nodes.Count &&
nodes.Count > -1)
{
nodes[id].SetPosition(x, y);
return true;
}
return false;
}
10. Метод Save сохраняет граф в файл с заданным именем:
public void Save(string filename)
{
FileStream fs = new FileStream(filename,
FileMode.Create, FileAccess.Write);
BinaryWriter w = new BinaryWriter(fs);
w.Write(signature);
w.Write(nodes.Count);
w.Write(edges.Count);
for (int i = 0; i < nodes.Count; i++)
{
w.Write(nodes[i].isExists());
w.Write(nodes[i].GetPositionX());
w.Write(nodes[i].GetPositionY());
}
for (int i = 0; i < edges.Count; i++)
int node1, node2;
edges[i].GetLinkedNodes(out node1, out
node2);
w.Write(node1);
w.Write(node2);
}
w.Flush();
w.Close();
}
2.6 Методы класса GraphMaxDistanceFinder
. В конструктор класса передается ссылка на граф, в котором необходимо
проводить поиск пути, а также, имя файла, хранящего изображение вершины, которая
входит в найденный путь:
public GraphPathFinder(ref Graph _graph,
string pathNodeImage)
{
graph = _graph;
imgPathNode = Image.FromFile(pathNodeImage);
}
. Метод Draw служит для графического отображения
графа с найденным маршрутом на заданном графическом контексте (Данный метод
используется вместо метода Draw
класса Graph:
public void Draw(ref Graphics g)
{
Pen pen;
Pen normalPen = new Pen(Color.Black, 5);
Pen linkedPen = new Pen(Color.Red, 5);
for (int i = 0; i < graph.edges.Count;
i++)
{
Point xFrom, xTo;
int node1, node2;
graph.edges[i].GetLinkedNodes(out node1, out
node2);
xFrom = new
Point(graph.nodes[node1].GetPositionX(), graph.nodes[node1].GetPositionY());
xTo = new
Point(graph.nodes[node2].GetPositionX(), graph.nodes[node2].GetPositionY());
pen = normalPen;
if (pathNodes.Contains(node1) &&
pathNodes.Contains(node2))
pen = linkedPen;
g.DrawLine(pen, xFrom, xTo);
}
for (int i = 0; i < graph.nodes.Count;
i++)
{
GraphNode node = graph.nodes[i];
if (node.isExists())
{
NODE_TYPE nodeType =
NODE_TYPE.NOT_CONNECTED; //0 - Not connected, 1 - OK node, 2 - Path node
if (!pathNodes.Contains(i))
foreach (GraphEdge edge in graph.edges)
{
int node1, node2;
edge.GetLinkedNodes(out node1, out node2);
if (node1 == i || node2 == i)
{
nodeType = NODE_TYPE.OK;
break;
}
}
else
nodeType = NODE_TYPE.PATH;
switch (nodeType)
{
case NODE_TYPE.NOT_CONNECTED:
g.DrawImage(graph.imgNode,
node.GetPositionX() - graph.imageCenter, node.GetPositionY() -
graph.imageCenter);
break;
case NODE_TYPE.OK:
g.DrawImage(graph.imgOkNode,
node.GetPositionX() - graph.imageCenter, node.GetPositionY() -
graph.imageCenter);
break;
case NODE_TYPE.PATH:
g.DrawImage(imgPathNode, node.GetPositionX()
- graph.imageCenter, node.GetPositionY() - graph.imageCenter);
break;
default:
g.DrawImage(graph.imgNode,
node.GetPositionX() - graph.imageCenter, node.GetPositionY() -
graph.imageCenter);
break;
g.DrawString((i + 1).ToString(), graph.font,
Brushes.Black, node.GetPositionX() - 12, node.GetPositionY() - 12);
3. Метод GraphPathFinder
namespace Graphs
{
public enum NODE_TYPE
{
NOT_CONNECTED = 0,
OK = 1,
PATH = 2,
FOUND = 3,
}
class GraphPathFinder
{
Graph graph;
List<int> pathNodes = new
List<int>();
Image imgPathNode;
public GraphPathFinder(ref Graph _graph,
string pathNodeImage)
{
graph = _graph;
imgPathNode = Image.FromFile(pathNodeImage);
}
public int GetPathLength()
{
return pathNodes.Count;
}
public bool FindPath(int nodeStartID, int
nodeEndID)
{
pathNodes.Clear();
for (int i = 0; i < graph.nodes.Count;
i++)
graph.nodes[i].pfField = -1;
bool isPathFound = false;
List<int> nodesToScan = new
List<int>();
nodesToScan.Add(nodeStartID);
int currentNum = 0;
while (nodesToScan.Count > 0)
{
List<int> tempNodes = new
List<int>();
for (int i = 0; i < nodesToScan.Count; i++)
{
graph.nodes[nodesToScan[i]].pfField =
currentNum;
foreach (GraphEdge edge in graph.edges)
{
int n1, n2;
edge.GetLinkedNodes(out n1, out n2);
if ( n1 == nodesToScan[i] )
{
if (!(tempNodes.IndexOf(n2) > -1))
if (graph.nodes[n2].pfField == -1)
tempNodes.Add(n2);
}
if ( n2 == nodesToScan[i] )
{
if (!(tempNodes.IndexOf(n1) > -1))
if (graph.nodes[n1].pfField == -1)
tempNodes.Add(n1);
}
}
}
nodesToScan = tempNodes;
currentNum++;
}
if (graph.nodes[nodeEndID].pfField != -1)
{
int currPf = graph.nodes[nodeEndID].pfField;
pathNodes.Add(nodeEndID);
while (currPf > 0)
{
currPf--;
foreach (GraphEdge edge in graph.edges)
{
int n1, n2;
edge.GetLinkedNodes(out n1, out n2);
if (n1 == pathNodes[pathNodes.Count - 1])
{
currPf = (int)Math.Min(currPf,
graph.nodes[n2].pfField);
}
if (n2 == pathNodes[pathNodes.Count - 1])
{
currPf = (int)Math.Min(currPf,
graph.nodes[n1].pfField);
}
}
bool isAdded = false;
for (int i = 0; i < graph.nodes.Count;
i++)
{
if (graph.nodes[i].pfField == currPf)
{
if (!isAdded)
{
foreach (GraphEdge edge in graph.edges)
{
int n1, n2;
edge.GetLinkedNodes(out n1, out n2);
if ((n1 == i || n1 ==
pathNodes[pathNodes.Count - 1]) && (n2 == i || n2 ==
pathNodes[pathNodes.Count - 1]))
{
pathNodes.Add(i);
isAdded = true;
break;
}
}
}= true;
}
return isPathFound;
}
public void Draw(ref Graphics g)
{
Pen pen;
Pen normalPen = new Pen(Color.Black, 5);
Pen linkedPen = new Pen(Color.Red, 5);
for (int i = 0; i < graph.edges.Count;
i++)
{
Point xFrom, xTo;
int node1, node2;
graph.edges[i].GetLinkedNodes(out node1, out
node2);
xFrom = new
Point(graph.nodes[node1].GetPositionX(), graph.nodes[node1].GetPositionY());
xTo = new
Point(graph.nodes[node2].GetPositionX(), graph.nodes[node2].GetPositionY());
pen = normalPen;
if (pathNodes.Contains(node1) &&
pathNodes.Contains(node2))
pen = linkedPen;
g.DrawLine(pen, xFrom, xTo);
}
for (int i = 0; i < graph.nodes.Count;
i++)
{
GraphNode node = graph.nodes[i];
if (node.isExists())
{
NODE_TYPE nodeType =
NODE_TYPE.NOT_CONNECTED; //0 - Not connected, 1 - OK node, 2 - Path node
if (!pathNodes.Contains(i))
foreach (GraphEdge edge in graph.edges)
{
int node1, node2;
edge.GetLinkedNodes(out node1, out node2);
if (node1 == i || node2 == i)
{
nodeType = NODE_TYPE.OK;
break;
}
}
else
nodeType = NODE_TYPE.PATH;
//if (nodeType == NODE_TYPE.OK)
// g.DrawImage(graph.imgOkNode,
node.GetPositionX() - graph.imageCenter, node.GetPositionY() -
graph.imageCenter);
//else
// g.DrawImage(graph.imgNode,
node.GetPositionX() - graph.imageCenter, node.GetPositionY() -
graph.imageCenter);
switch (nodeType)
{
case NODE_TYPE.NOT_CONNECTED:
g.DrawImage(graph.imgNode,
node.GetPositionX() - graph.imageCenter, node.GetPositionY() -
graph.imageCenter);
break;
case NODE_TYPE.OK:
g.DrawImage(graph.imgOkNode, node.GetPositionX()
- graph.imageCenter, node.GetPositionY() - graph.imageCenter);
break;
case NODE_TYPE.PATH:
g.DrawImage(imgPathNode, node.GetPositionX()
- graph.imageCenter, node.GetPositionY() - graph.imageCenter);
break;
default:
g.DrawImage(graph.imgNode,
node.GetPositionX() - graph.imageCenter, node.GetPositionY() -
graph.imageCenter);
break;
}
g.DrawString((i + 1).ToString(), graph.font,
Brushes.Black, node.GetPositionX() - 12, node.GetPositionY() - 12);
}
. Метод GraphMaxDistanceFinder ищет кратчайший путь между заданными
вершинами и возвращает true
если путь был найден и false
если путь не существует:
class GraphMaxDistanceFinder
{
struct NodesDistanceEntry
{
public int node1, node2;
public int pathLength;
public NodesDistanceEntry(int n1, int n2,
int length)
{
node1 = n1;
node2 = n2;
pathLength = length;
}
}
Graph graph;
GraphPathFinder pf;
Image imgFoundNode;
List<NodesDistanceEntry> distanceList;
int maxDistanceInd;
int maxDistanceLength;
public GraphMaxDistanceFinder(ref Graph
_graph, string foundNodeImage)
{
graph = _graph;
imgFoundNode =
Image.FromFile(foundNodeImage);
pf = new GraphPathFinder(ref graph,
foundNodeImage);
distanceList = new
List<NodesDistanceEntry>();
maxDistanceInd = -1;
maxDistanceLength = -1;
}
public bool FoundFarestNodes()
{
maxDistanceInd = -1;
maxDistanceLength = -1;
distanceList.Clear();
for (int i = 0; i < graph.nodes.Count -
1; i++)
{
for (int j = i + 1; j <
graph.nodes.Count; j++)
{
if (pf.FindPath(i, j))
{
distanceList.Add(new NodesDistanceEntry(i,
j, pf.GetPathLength()));
}
}
}
if (distanceList.Count == 0)
return false;
for (int i = 0; i < distanceList.Count;
i++)
{
NodesDistanceEntry nde = distanceList[i];
if (maxDistanceLength < nde.pathLength)
{
maxDistanceLength = nde.pathLength;
maxDistanceInd = i;
}
}
return true;
}
public void Draw(ref Graphics g)
{
Pen pen = new Pen(Color.Black, 5);
for (int i = 0; i < graph.edges.Count;
i++)
{
Point xFrom, xTo;
int node1, node2;
graph.edges[i].GetLinkedNodes(out node1, out
node2);
xFrom = new
Point(graph.nodes[node1].GetPositionX(), graph.nodes[node1].GetPositionY());
xTo = new
Point(graph.nodes[node2].GetPositionX(), graph.nodes[node2].GetPositionY());
g.DrawLine(pen, xFrom, xTo);
}
for (int i = 0; i < graph.nodes.Count;
i++)
{
GraphNode node = graph.nodes[i];
if (node.isExists())
{
NODE_TYPE nodeType =
NODE_TYPE.NOT_CONNECTED; //0 - Not connected, 1 - OK node, 2 - Path node
if (maxDistanceInd != -1)
{
if (distanceList[maxDistanceInd].node1 != i
&& distanceList[maxDistanceInd].node2 != i)
foreach (GraphEdge edge in graph.edges)
{
int node1, node2;
edge.GetLinkedNodes(out node1, out node2);
if (node1 == i || node2 == i)
{
nodeType = NODE_TYPE.OK;
break;
}
}
else
nodeType = NODE_TYPE.FOUND;
}
else
{
foreach (GraphEdge edge in graph.edges)
{
int node1, node2;
edge.GetLinkedNodes(out node1, out node2);
if (node1 == i || node2 == i)
{
nodeType = NODE_TYPE.OK;
break;
}
}
}
switch (nodeType)
{
case NODE_TYPE.NOT_CONNECTED:
g.DrawImage(graph.imgNode,
node.GetPositionX() - graph.imageCenter, node.GetPositionY() -
graph.imageCenter);
break;
case NODE_TYPE.OK:
g.DrawImage(graph.imgOkNode,
node.GetPositionX() - graph.imageCenter, node.GetPositionY() -
graph.imageCenter);
break;
case NODE_TYPE.FOUND:
g.DrawImage(imgFoundNode,
node.GetPositionX() - graph.imageCenter, node.GetPositionY() -
graph.imageCenter);
break;
default:
g.DrawImage(graph.imgNode,
node.GetPositionX() - graph.imageCenter, node.GetPositionY() -
graph.imageCenter);
break;
}
g.DrawString((i + 1).ToString(), graph.font,
Brushes.Black, node.GetPositionX() - 12, node.GetPositionY() - 12);
}
}
}
2.7 Графический интерфейс
Для реализации графического интерфейса были использованы стандартные
средства визуального проектирования интерфейса среды разработки Microsoft Visual Studio 2012. Графический интерфейс представляет собой форму
(System.Windows.Forms.Form) на которой расположены строка меню
и командная панель. На командной панели расположены элементы управления RadioButton для выбора режима редактирования
графа и кнопки, необходимые для поиска пути.
· "Вершины" - активирует режим редактирования вершин
(используется по умолчанию). В этом режиме можно добавлять вершины с помощью
левой кнопки мыши, перемещать вершины на графе методом "drag'n'drop" с
помощью зажатой левой кнопки мыши, а также, удалять вершины с помощью правой
кнопки мыши. Координаты вершины при перемещении изменяются в реальном времени.
· "Ребра" - активирует режим редактирования ребер. В
этом режиме можно добавлять ребра путем зажатия левой кнопки мыши на вершине и
отпускания левой кнопки мыши на другой вершине. При перемещении мыши с зажатой
левой кнопкой будет отображаться ребро, начинающееся с той вершины, где была
зажата левая кнопка мыши. Ребро заканчивается в текущих координатах курсора
мыши и отображается серым цветом. Также, в режиме редактировании ребер можно
удалить ребро путем нажатия правой кнопки мыши на одной из вершин, связываемых
нужным ребром. При нажатии правой кнопки мыши появится контекстное меню со
списком ребер. В данном меню нужно выбрать необходимое ребро для удаления.
· "Поиск максимально удалённых вершин" - активирует
режим поиска максимально удалённых друг от друга вершин, при этом становятся
доступны кнопка, отвечающая за поиск пути, расположенная справа.
С помощью команд меню, расположенных в пункте меню "Файл" можно
создать новый граф, сохранить текущий или загрузить граф из файла.
Заключение
Результатом курсовой работы является приложение, позволяющее найти
максимально удалённые вершины в графе. Программный продукт имеет графический
интерфейс и имеет возможность сохранения и загрузки графов. Приложение
реализовано с помощью языка программирования Microsoft Visual C#, с использованием среды разработки Microsoft Visual Studio 2012.
Список литературы
1. Wikipedia/
Википедия. Теория графов
. Джон
Шарп. Microsoft Visual C# 2008 Step by Step (Изучение Microsoft Visual C# 2008 шаг за шагом) / Джон Шарп.
. Джейми
Плендерлейт. Microsoft Visual Studio 2008 Programming (Программирование в Microsoft Visual Studio 2008) / Джейми Плендерлейт, Стив
Бунн.
. Фрэнк
Харари. Теория графов / Фрэнк Харари.