Разработка программы нахождения всех полных подграфов (клик) данного графа (стр. 1 из 4)
Курсовая работа
По предмету
"Программирование на языке высокого уровня"
Тема: "Разработка программы нахождения всех полных подграфов (клик) данного графа"
Содержание
Введение
1. Описание алгоритма нахождения клик
2. Разработка структуры программы
2.1 Постановка задачи
2.2 Структура программы
2.3 Описание классов
2.3.1 Класс vertexmatrix
2.3.2 Класс graph
2.3.3 Класс from1
2.3.4 Классtoolwindow
2.3.5 Класс MatrixWindow
2.3.6 Класс cliqueswindow
3. Реализация на C#
3.1 Реализация алгоритма Брона-Кербоша
3.2 Использование нестандартных компонентов
3.3 Реализация алгоритма удаления ребра графа мышью
3.4 Тестирование реализации алгоритма Брон-Кербоша
3.5 Системные требования
Заключение
Список использованной литературы и источников
Приложение
Клика – полный подграф неориентированного графа. Другими словами, клика графа есть подмножество его вершин, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством.
Подграф графа — граф, содержащий некое подмножество вершин данного графа и некое подмножествоинцидентных им рёбер.
Граф – совокупность непустого множества вершин и множества пар вершин.
Неориентированный граф – упорядоченная пара G: = (V,E), для которой выполнены следующие условия:
V это непустое множество вершин или узлов
E это множество пар (в случае неориентированного графа неупорядоченных) вершин, называемых ребрами.
К примеру, для графа на рисунке 1 кликами будут являться следующие множества вершин: {1,2,3},{4,2,5},{2,3,5},{3,5,6}. Порядок следования вершин значения не имеет.
Рисунок 1 – неориентированный граф из шести вершин.
1. Описание алгоритма нахождения клик
В качестве алгоритма поиска клик был выбран алгоритм Брона-Кербоша ("Algorithm 457: Finding All Cliques of an Undirected Graph".), заявленный как один из самых быстрых алгоритмов поиска клик (Cazals, F.; Karande, C. (2008),"A note on the problem of reporting maximal cliques"). Алгоритм разработан голландскими математиками Броном и Кербошем (Bron and Kerbosh) в 1973 году.
Алгоритм использует тот факт, что всякая клика в графе является его максимальным по включениюполным подграфом. Начиная с одиночной вершины (образующей полный подграф), алгоритм на каждом шаге пытается увеличить уже построенный полный подграф, добавляя в него вершины из множества кандидатов. Высокая скорость обеспечиваетсяотсечениемпри переборе вариантов, которые заведомо не приведут к построению клики, для чего используется дополнительное множество, в которое помещаются вершины, которые уже были использованы для увеличения полного подграфа.
На листинге 1.1 приведена реализация алгоритма псевдокодом. M – текущее независимое множество, K – множество кандидатов (вершин, способных образовать клику. На начальном этапе это множество содержит все вершины графа), P – множество отсеянных вершин, которые не могут более добавляться в M, v – просматриваемая вершина, G(i) – множество вершин, смежных с i.
Листинг 1.1 – реализация алгоритма Брона-Кербоша псевдокодом
while K != 0 or M != 0:
if K != 0:
v = K.first
push M, K, P, v
M = M + {v}
K = K – G(v) – {v}
P = P – G(v)
else:
if P == 0:
print M
pop v, P, K, M
K = K – {v}
P = P + {v}
2. Разработка структуры программы
2.1 Постановка задачи
Задачей программы ставится нахождение всех полных подграфов (клик) данного неориентированного графа. Помимо этого программа должна обладать следующими возможностями:
– Создание и редактирование неориентированного графа.
– Загрузка и сохранение графа в файл, как в виде матрицы смежности, так и в собственном формате файла программы.
– Обеспечивать интерактивность графа (граф можно создавать/изменять при помощи мыши, изменения в графе сразу же отображаются на экране).
– Обладать средствами экспорта изображения графа в графические файлы формата png и bmp (формат jpg мало подходит для этих целей, так как на однородном фоне хорошо заметны артефакты конверсии изображения).
– Предоставлять средства просмотра найденных в графе клик, а также экспорта их в графические файлы или сохранения в матричном или графовом формате.
– Обладать средствами генерации отчета о найденных кликах.
– Предоставлять возможность распечатать созданный граф.
2.2 Структура программы
Программа состоит из главного окна приложения, в котором осуществляется создание и редактирование графа, окна свойств графа, отображающего его матрицу смежности и параметры и окна поиска и отображения клик.
Для реализации операций над графом и его матрицей смежности было создано два класса: Graph и VertexMatrix, реализующие все операции применимые к графу в данном приложении.
2.3 Описание классов
2.3.1 Класс VertexMatrix
Конструкторы класса
VertexMatrix(int dimension) - создает заполненную нулями матрицу смежности порядка dimension.
Также класс имеет статический метод-конструктор для создания матрицы из текстового файла:
static VertexMatrix FromTextFile(string filename) - создает матрицу вершин графа из текстового файла с именем, указанным в filename.
Формат файла: квадратная матрица, состоящая из нулей и единиц, например:
011
101
110
Примечание: в большинстве кодировок символы цифр сохраняют свои коды, поэтому проблемы с загрузкой матрицы из текстового файла маловероятны.
Public методы
byte Get(int column, int row) - возвращает значение ячейки матрицы в столбце column строки row. В случае если значения column или row превышают порядок матрицы, генерируется исключение IndexOutOfRangeException.
void Set(int column, int row, byte value) - Установить значение ячейки матрицы в столбце column строки row равным value. В случае если значения column или row превышают порядок матрицы, генерируется исключение IndexOutOfRangeException.
void AddVertex() - добавляет к матрице новую строку и столбец, тем самым, расширяя порядок матрицы. Новая строка и столбец заполняются нулями.
void DeleteVertex(int index) - удаляет из матрицы строку и столбец с индексом index, тем самым, понижая ее порядок. Строки и столбцы с индексами index+1, если таковы имеются, занимают место удаленных.
void SaveToTextFile(string filename) - создает текстовый файл с матрицей. Формат файла был описан выше.
Private методы
void AddRow() - добавляет строку к матрице.
void AddColumn() - добавляет столбец к матрице.
Свойства
int Dimension - возвращает порядок матрицы. Это свойство только для чтения.
Private свойства
List<List<byte>> mat - сама матрица.
List<byte> row - используется для добавления строк к матрице.
int rlength - длина строки матрицы.
int clength - длина столбца матрицы.
int mat_dimension - порядок матрицы.
2.3.2 Класс Graph
Конструкторы класса
Graph(VertexMatrix matrix) - cоздает граф из матрицы смежности matrix.
Graph(VertexMatrix mat, int radius) – cоздает граф размером radius из матрицы смежности mat.
По умолчанию вершины графа располагаются по окружности радиуса Radius. Первая вершина графа располагается в направлении девяти часов.
Public методы
int AddVertex(PointF coords) - добавляет к графу вершину с координатами coords, при этом порядок матрицы графа увеличивается на единицу. Возвращает индекс добавленной вершины.
void DeleteVertex(int index) - удаляет из графа вершину с индексом index. При этом из матрицы графа также удаляется соответствующие вершине строка и столбец.
int GetVertexIndexFromPoint(PointF p) - возвращает индекс вершины графа, которой принадлежит точка с координатами p. В случае если такой вершины не найдено, возвращает -1.
int[] GetVerticesFromNodePoint(PointF node) – возвращает массив размерностью 2, в которых находятся индексы вершин графа, ребру которых (если такое существует) принадлежит точка с координатами node. Если таких вершин не найдено или они не соединены ребром, функция возвращает null.
void SetVertexCoordinats(int index, PointF coord) - устанавливает координаты вершины с индексом index равными coord.
void ArrangeByCircle()
void ArrangeByCircle(int radius) - располагает вершины графа по окружности радиусом Radius.
Image DrawVerticesToImage(int[] indexes) - рисует вершины с индексами indexes графа в объект класса Image. Размеры области рисования вычисляются из нахождения вершин с координатами максимально и минимально удаленными от осей X и Y.
Возвращает объект класса Image, в котором было произведено рисование.
void Draw(Graphics g) - рисует граф в области g.
void SaveToFile(string filename) - сохраняет граф в бинарный файл. Описание формата представлено в таблице 2.3.1.
Таблица 2.1 - Формат файла .g
| Смещение (байт) DEC | Размер (байт) | Содержимое |
| 0 | 2 | Сигнатура файла .g: 0x0A0D |
| 2 | 2 | Версия файла ( 0 ) |
| 4 | 2 | Число вершин в графе (порядок матрицы смежности). |
| 6 | Число вершин графа в квадрате | Матрица смежности графа. Хранится построчно |
| sizeof(float)*2 * число вершин в графе | Координаты вершин графа. Хранятся построчно:x1y1x2y2…xnyn |
static Graph FromFile(string filename) - создает граф из файла графа.
List<List<int>> FindAllCliques() - возвращает список списков вершин графа, образующих клики.
Private методы
PointPlace pointClassify(PointF point, PointF origin, PointF dest) - возвращает перечисление PointPlace, указывающую в каком положении относительно отрезка, начинающегося в точке origin и оканчивающемуся в точке dest находится точка.
Перечисление PointPlace:
enum PointPlace : int
{
LEFT = 0,
RIGHT = 1,
BEYOND = 3,
BEHIND = 4,
BETWEEN = 5,
ORIGIN = 6,
DESTINATION = 7,
}
bool pointInTriangle(PointF p, PointF a, PointF b, PointF c) - возвращает true, если точка p принадлежит треугольнику с координатами вершин a, b, c. В противном случае возвращает false.
void SubtractSet(List<int> set, int vert) - удаляет вершину c индексом vert из списка set.
void SubtractSet(List<int> set1, List<int> set2) - удаляет из списка set1 элементы, содержащиеся в set2 (если таковые присутствуют).
List<int> G(int vert) - возвращает список вершин, не смежных с вершиной с индексом vert.
Свойства
int Radius - возвращает размер графа.
int VertexRadius - возвращает радиус вершины.