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

Stack 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 cliques - список вершин найденных клик.

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

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

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

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

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

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

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

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

public List FindAllCliques()

{

List output = new List();

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

List M = new List();

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

List K = new List();

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

List P = new List();

//вершина

int v;

Stack stackV = new Stack();

Stack stackM = new Stack();

Stack stackK = new Stack();

Stack stackP = new Stack();

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

List GS = new List();

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

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 set, int vert)

{

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

{

if (set[i] == vert)

set.RemoveAt(i);

}

}

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

void SubtractSet(List set1, List 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 G(int vert)

{

List ret = new List();

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 (http://sourceforge.net/users/weifenluo) под лицензией MIT. Подробное описание компонента, а также исходные коды находятся на прилагаемом к курсовой компакт-диске в папке DockingWindowsComponent.

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

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

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

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