Xreferat.com » Рефераты по информатике и программированию » Разработка программы нахождения всех полных подграфов (клик) данного графа

Разработка программы нахождения всех полных подграфов (клик) данного графа

Курсовая работа

По предмету

"Программирование на языке высокого уровня"

Тема: "Разработка программы нахождения всех полных подграфов (клик) данного графа"


Содержание


Введение

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 - возвращает радиус вершины.

Private свойства

VertexMatrix gmatrix - матрица вершин графа.

List<PointF> vertices - список координат вершин графа.

Font font - шрифт, используемый для номеров вершины графа. Используется шрифт Verdana высотой 9 пунктов.

int graph_rad - ширина графа. По умолчанию равна 60.

int vertex_rad - радиус вершины графа. По умолчанию равен 10.

bool ellipse - определяет, располагать ли вершины графа по окружности радиусом graph_rad.


2.3.3 Класс From1

Конструктор

Form1() - cоздает экземпляр класса Form1.

Public методы

Класс не имеет public методов.

Private методы

IDockContent GetContentFromPersistString(string persistString) - метод, необходимый для подготовки компонента DockPanel к работе и обеспечивает возможность размещения в ней докингого окна класса MatrixWindow.

Параметр persistString – имя класса докингого окна.

void Form1_Load(object sender, EventArgs e) - обработчик события Load окна.

void saveDocument(bool saveAs) - отображает меню "Сохранить", предоставляющее возможность сохранить граф в файл. Если граф создан не из файла, пользователю предоставляется возможность самостоятельно выбрать имя, тип и путь к сохраняемому файлу посредством стандартного диалога сохранения файла Windows. В случае, если параметр saveAs равен true, будет вызвано стандартное окно "Сохранить как" Windows.

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

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

void UNDOAction() - отменяет последнее совершенное пользователем редактирование графа.

void REDOAction() - отменяет отмену последнего совершенного пользователем редактирования графа.

void AddToUNDO(Graph graph) - добавляет граф graph в стек отмены.

void dockPanel_Paint(object sender, PaintEventArgs e) - событие Paint объекта класса dockPanel.

void DoToolAction(AppTool t, PointF coords) - выполняет действие, предписанное инструментом t с начальными координатами coоrds.

void dockPanel_MouseDown(object sender, MouseEventArgs e) - обработчик события MouseDown объекта класса dockPanel.

Используется для получения координат мыши и вызова метода DoToolAction.

void dockPanel_MouseMove(object sender, MouseEventArgs e) - обработчик события MouseMove объекта класса. Используется для получения координат мыши инструментами "Курсор" и "Добавление ребер".

void dockPanel_MouseUp(object sender, MouseEventArgs e) - обработчик события MouseUp объекта класса DockPanel. Используется для уведомления инструмента "Добавление ребра" о том, что действие закончилось.

void toolStripButtonCursor_CheckStateChanged(object sender, EventArgs e) - изменяет выбранный инструмент на инструмент "Курсор".

void toolStripButtonAddVertex_CheckStateChanged(object sender, EventArgs e) - изменяет выбранный инструмент на инструмент "Добавление вершин".

void toolStripButtonDelVertex_CheckStateChanged(object sender, EventArgs e) - изменяет выбранный инструмент на инструмент "Удаление вершины".

void toolStripButtonAddNode_CheckStateChanged(object sender, EventArgs e) - изменяет выбранный инструмент на инструмент "Добавление ребер".

void toolStripButtonDelNode_CheckStateChanged(object sender, EventArgs e) - изменяет выбранный инструмент на инструмент "Удаление ребер".

void toolStripButtonUndo_Click(object sender, EventArgs e) - обработчик клика по кнопке "Отменить" панели инструментов. Нажатие этой кнопке приведет к откату состояния графа на предыдущее.

void toolStripButtonRedo_Click(object sender, EventArgs e) - обработчик клика по кнопке "Повторить" панели инструментов. Нажатие этой кнопки приведет к отмену отмены изменений в графе.

void PropertiesWindowToolStripMenuItem_CheckStateChanged(object sender, EventArgs e) - обработчик клика по пункту меню Вид -> Окно свойств. Скрывает или показывает окно "Свойства графа".

void ViewToolStripMenuItem_DropDownOpening(object sender, EventArgs e) - обработчик события DropDownOpening панели меню Вид - > Окно свойств. В случае если окно свойств видимо обработчик отмечает элемент меню.

void расположитьВершиныПоОкружностиToolStripMenuItem_Click(object sender, EventArgs e) - обработчик клика по элементу меню Граф - > Расположить вершины по окружности. Вызов этого меню приведет к расположению графа по радиусу окружности равному свойству Radius графа.

void SaveToolStripMenuItem_Click(object sender, EventArgs e) - обработчик клика по пункту меню Файл - > Сохранить. Этот же обработчик имеет кнопка "Сохранить" на панели инструментов.

void OpenToolStripMenuItem_Click(object sender, EventArgs e) - обработчик клика по пункту меню Файл - > Открыть. Этот же обработчик имеет кнопка "Открыть" панели инструментов.

void NewToolStripMenuItem_Click(object sender, EventArgs e) - обработчик клика по пункту меню Файл - > Новый. Этот же обработчик имеет кнопка "Новый" на панели инструментов.

void printToolStripMenuItem_Click(object sender, EventArgs e) - обработчик клика по пункту меню Файл - > Печать. Этот же обработчик имеет кнопка "Печать" на панели инструментов.

void pageToolStripMenuItem_Click(object sender, EventArgs e) - обработчик клика по пункту меню Файл - > Предварительный просмотр. Этот же обработчик имеет кнопка "Предварительный просмотр" на панели инструментов. Открывает окно предварительного просмотра документа перед печатью.

DialogResult userWantsToSaveChanges() - выводит окно с предложением сохранить изменения в документе. Варианты ответа "Да", "Нет", "Отмена". Возвращает структуру DialogResult, содержащую вариант выбранного ответа.

bool closeApp() - функция вызывается при закрытии приложения. Вызывает вышеописанную функцию и, в случае утвердительного ответа, возвращает true. В остальных случаях возвращает false.

void ExitToolStripMenuItem_Click(object sender, EventArgs e) - обработчик клика по пункту меню Файл - > Выход. Вызывает закрытие приложения.

Private свойства

delegate IDockContent DeserializeDockContent ddc - необходим для подготовке контрола dockPanel к работе.

MatrixWindow matrixWindow - окно "Граф".

AppTool currTool - перечисление, определяющее текущий выбранный инструмент.

bool mouseDown - определяет, нажата ли левая кнопка мыши. Используется для работы с инструментами "Курсор" и "Добавить ребро".

int selVertexIndex- индекс выбранной вершины, с которой работает инструмент.

int selVertexIndex2 - индекс второй выбранной вершины, с которой работает инструмент "Добавить ребро".

Point nodePointStart - координата первой выбранной вершины, с которой работает инструмент "Добавить ребро".

Point nodePointEnd - координата второй вершины, с которой работает инструмент "Добавить ребро".

bool documentModified - определяет, были ли произведены изменения в графе. Следует отметить, что если изменения имели быть, но были отменены, документ считается не модифицированным.

string openedDocumentPath - путь к файлу графа или матрице (если граф был создан из файла, else – "").

Stack<Graph> stackUNDO - стек отмены. В него помещается экземпляр графа, перед тем как произвести в нем изменения.

Stack<Graph> stackREDO - стек повтора. В него перемещаются элементы из предыдущего стека при произведении пользователем отмены совершенного им действия.

Следует отметить, что вместо двух стеков может использоваться список элементов типа Graph, что сэкономит ресурсы.

Константы класса

const string GRAPH_OPENSAVE_DIALOG_FILTER = "Граф (*.g)|*.g|Матрица (*.txt)|*.txt" - константа, определяющая свойство Filter у стандартных диалогов открытия/сохранения файла.

const string PROGRAM_NAME = "Cliques" - заголовок окна.


2.3.4 Класс ToolWindow

Данный класс не содержит никаких пользовательских свойств или методов


2.3.5 Класс MatrixWindow

Конструкторы класса

MatrixWindow() - cоздает экземпляр объекта класса MatrixWindow.

Public методы

VertexMatrix GetMatrixFromDataGrid() - возвращает содержащуюся в окне матрицу.

void FillDataGrid(VertexMatrix mat) - заполняет окно матрицей mat.

void SetDefValues() - устанавливает в окне значения "Размер графа", "Размер вершин" и "Число вершин" равными по умолчанию, это 60, 10 и 0 соответственно. Граф в главном окне при этом не меняется.

void BlockGraphProp(bool block) - устанавливает возможность изменять свойства графа в окне. При block = true изменять свойства нельзя, else можно.

Private методы

void dataGridView1_ColumnAdded(object sender, DataGridViewColumnEventArgs e) - обработчик события ColumnAdded контрола, содержащего матрицу графа. Добавляет к новосозданной колонке ее порядковый номер.

void ClearDataGrid() - очищает контрол, отображающий матрицу графа. Граф при этом не изменяется.

void dataGridView1_RowsAdded(object sender, DataGridViewRowsAddedEventArgs e)- обработчик события RowsAdded контрола, отображающего матрицу графа. Нумерует новосозданные ячейки.

void dataGridView1_CellMouseDown(object sender, DataGridViewCellMouseEventArgs e) - обработчик события CellMouseDown контрола, отображающего матрицу графа. Меняет значение в кликнутой ячейке на противоположное. Значения на главной диагонали матрицы изменению не подвергаются.

Public свойства

Класс не имеет public свойств.

Private свойства

Класс не имеет private свойств.


2.3.6 Класс CliquesWindow

Конструкторы класса

CliquesWindow() - cоздает экземпляр класса CliquesWindow.

Public методы

Класс не имеет public методов.

Private методы

void CliquesWindow_Load(object sender, EventArgs e) - обработчик события Load формы. Если public свойство graph не равно null вызывает процедуру поиска клик. В противном случае выводит на экран уведомление об отсутствии в графе клик.

void FindAllCliques(Graph g) - находит все клики в графе g.

Image ScaleImage(Image source, int width, int height) - изменяет масштаб изображения source на width и height. Возвращает полученное изображение.

ShowCliqueMatrix(int[] c) - отображает матрицу вершин c клики.

void SaveClique(int index) - отображает диалог сохранения клики с индексом index в файл.

void CreateReport(string filename) - создает файлы отчета обо всех найденных в графе кликах.

Public свойства

Graph graph - граф, в котором будет производиться поиск клик.

Private свойства

List<List<int>> cliques - список вершин найденных клик.

ImageList imgList - сюда заносятся изображения найденных клик.

Константы класса

int VIEW_IMAGE_WIDTH = 150 - ширина изображения клики.

int VIEW_IMAGE_HEIGHT = 150 - высота изображения клики.


3. Реализация на C#


3.1 Реализация алгоритма Брона-Кербоша


Реализация алгоритма Брона-Кербоша на С# представлена в Листинге 3.1. Представленные на нем функции являются методами класса Graph.

Листинг 3.1 – Реализация алгоритма Брона-Кербоша на С#.


public List<List<int>> FindAllCliques()

{

List<List<int>> output = new List<List<int>>();

//сюда помещаются вершины, образующие клику

List<int> M = new List<int>();

//список вершин графа

List<int> K = new List<int>();

//список "отработанных" вершин

List<int> P = new List<int>();

//вершина

int v;

Stack<int> stackV = new Stack<int>();

Stack<List<int>> stackM = new Stack<List<int>>();

Stack<List<int>> stackK = new Stack<List<int>>();

Stack<List<int>> stackP = new Stack<List<int>>();

//список несмежных с вершиной вершин

List<int> GS = new List<int>();

//заполняем список вершинами графа

for (int i = 0; i < gmatrix.Dimension; i++)

K.Add(i);

while (K.Count != 0 || M.Count != 0)

{

if (K.Count != 0)

{

v = K[0];

stackM.Push(M.GetRange(0, M.Count));

stackK.Push(K.GetRange(0, K.Count));

stackP.Push(P.GetRange(0, P.Count));

stackV.Push(v);

M.Add(v);

GS = G(v);

SubtractSet(K, GS);

SubtractSet(K, v);

SubtractSet(P, GS);

}

else

{

if (P.Count == 0) //клика найдена

output.Add(M.GetRange(0,M.Count));

M = stackM.Pop();

K = stackK.Pop();

P = stackP.Pop();

v = stackV.Pop();

SubtractSet(K, v);

P.Add(v);

}

}

return output;

}

/* вычитает вершину из множества */

void SubtractSet(List<int> set, int vert)

{

for (int i = 0; i < set.Count; i++)

{

if (set[i] == vert)

set.RemoveAt(i);

}

}

/* вычитает второе множество из первого */

void SubtractSet(List<int> set1, List<int> set2)

{

for (int i = 0; i < set1.Count; i++)

for (int j = 0; j < set2.Count; j++)

if (set1.Count != 0 && i < set1.Count)

if (set1[i] == set2[j])

set1.RemoveAt(i);

}

/* возвращает список вершин, не смежных с vert */

List<int> G(int vert)

{

List<int> ret = new List<int>();

for (int i = 0; i < gmatrix.Dimension; i++)

if (gmatrix.Get(i, vert) == 0)

ret.Add(i);

return ret;

}


Примечание: gmatrix – матрица смежности вершин, реализованная объектом класса VertexMatrix. Свойство Dimension определяет порядок матрицы (число вершин графа).


3.2 Использование нестандартных компонентов


В программе был использован элемент, не входящий в поставку .NET Framework 2.0 – DockPanel. Компонент является opensource и написан китайским разработчиком Weifen Luo (sourceforge/users/weifenluo) под лицензией MIT. Подробное описание компонента, а также исходные коды находятся на прилагаемом к курсовой компакт-диске в папке DockingWindowsComponent.

Назначение компонента

Компонент предназначен для создания "плавающих" окон, окон, способных "прилипать" к краям невидимой панели, а также быть независимыми от нее. Подобный элемент интерфейса, например, использует пакет MS Visual Studio (окна "Properties", "Solution Explorer", etc) и другие программы. Достоинства такой организации интерфейса состоит в том, что не требуемые в данный момент окна могут быть скрытыми и не занимать экранное место, а, при необходимости отображения окна, компактно располагаются по краям родительского окна, что экономит общее экранное место, или же находятся в отсоединенном ("плавающем") состоянии. Панель невидима на экране и занимает всю доступную площадь окна.

Внесенные в компонент изменения

В компонент были внесены изменения, адаптирующие его под решаемую задачу. Поскольку, как уже было сказано выше, компонент занимает всю площадь экрана, было принято решение выполнять отрисовку графа именно на нем. Первоначальный вариант панели не имел средств для рисования на ней, поэтому были внесены изменения в метод OnPaint класса DockPanel, которые находятся в файле DockPanel.cs. На листинге 3.2 показан этот метод до изменения, на листинге 3.3 – после. Также было запрещено обработка события OnPaintBackground, что позволило избежать мерцания рабочей области.

Листинг 3.2 - Первоначальное состояние метода OnPaint класса DockPanel.


protected override void OnPaint(PaintEventArgs e)

{

base.OnPaint(e);

if (DockBackColor == BackColor)

return;

Graphics g = e.Graphics;

SolidBrush bgBrush = new SolidBrush(DockBackColor);

g.FillRectangle(bgBrush, ClientRectangle);

}


Листинг 3.3 - Состояние метода OnPaint класса DockPanel после редактирования.


protected override void OnPaint(PaintEventArgs e)

{

base.OnPaint(e);

}


Как видно из листинга 3.2.2 изменение свелось к удалению запрете закраски панели собственным цветом фона. Это приведет к невозможности установки свойства BackColor компонента, но оно не используется в данном приложении.

Использование компонента в данном приложении

В данном приложении элемент DockPanel использовался для создания окна, отображающего свойства графа (класс MatrixWindow). Для этого сначала было создано окно-пустышка класса ToolWindow, наследуемое от класса DockContent. Это позволило окну ToolWindow стать "плавающим". Далее от класса ToolWindow был наследован MatrixWindow.


3.3 Реализация алгоритма удаления ребра графа мышью


Задача: удалить ребро графа, лежащее под курсором мыши (Рис. 3.2).


Разработка программы нахождения всех полных подграфов (клик) данного графа

Рисунок 3.2 - Мышь находится рядом с ребром графа, который требуется удалить.


Решение:

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


Разработка программы нахождения всех полных подграфов (клик) данного графа

Рисунок 3.3 - Прямоугольник, образованный двумя треугольниками, делит пополам ребро графа. Координаты мыши принадлежат одному из треугольников.

Так задача сводится к одной из классических задач аналитической геометрии – определение принадлежности точки треугольнику.

Рассмотрим алгоритм определения принадлежности точки к одному треугольнику. Для начала необходимо узнать, к какой области принадлежит точка (Рис. 3.4).


Разработка программы нахождения всех полных подграфов (клик) данного графа

Рисунок 3.4. Области, в которых может лежать точка относительно линии.


Этим в классе Graph занимается частный метод pointClassify(Point source, Point dest), который возвращает один из элементов перечисления PointPlace, которое определяет область нахождения точки.

Перечисление PointPlace:


enum PointPlace : int

{

LEFT = 0,

RIGHT = 1,

BEYOND = 3,

BEHIND = 4,

BETWEEN = 5,

ORIGIN = 6,

DESTINATION = 7,

}

Листинг 3.4 – Метод pointClassify класса Graph.


PointPlace pointClassify(PointF point, PointF origin, PointF dest)

{

PointF a = dest;

a.X -= origin.X;

a.Y -= origin.Y;

PointF b = point;

b.X -= origin.X;

b.Y -= origin.Y;

double sa = a.X * b.Y - b.X * a.Y;

if (sa > 0.0)

return PointPlace.LEFT;

if (sa < 0.0)

return PointPlace.RIGHT;

if

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: