Курсоваяработа
По предмету
«Программированиена языке высокого уровня»
Тема: «Разработкапрограммы нахождения всех полных подграфов (клик) данного графа»
Содержание
Введение
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 AllCliques of an Undirected Graph».), заявленный как один из самых быстрыхалгоритмов поиска клик (Cazals, F.; Karande, C.(2008), «A note on the problem of reporting maximal cliques»).Алгоритм разработан голландскими математиками Броном и Кербошем (Bron andKerbosh) в 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(intdimension) — создаетзаполненную нулями матрицу смежности порядка dimension.
Также класс имеетстатический метод-конструктор для создания матрицы из текстового файла:
static VertexMatrixFromTextFile(string filename) — создает матрицу вершин графа из текстового файла с именем,указанным в filename.
Формат файла: квадратнаяматрица, состоящая из нулей и единиц, например:
011
101
110
Примечание: в большинствекодировок символы цифр сохраняют свои коды, поэтому проблемы с загрузкойматрицы из текстового файла маловероятны.
Public методы
byte Get(int column, introw) — возвращаетзначение ячейки матрицы в столбце column строки row. В случае если значенияcolumn или row превышают порядок матрицы, генерируется исключениеIndexOutOfRangeException.
void Set(int column, introw, byte value) — Установитьзначение ячейки матрицы в столбце column строки row равным value. В случае еслизначения column или row превышают порядок матрицы, генерируется исключениеIndexOutOfRangeException.
void AddVertex() — добавляет к матрице новую строку истолбец, тем самым, расширяя порядок матрицы. Новая строка и столбецзаполняются нулями.
void DeleteVertex(intindex) — удаляет изматрицы строку и столбец с индексом index, тем самым, понижая ее порядок.Строки и столбцы с индексами index+1, если таковы имеются, занимают местоудаленных.
voidSaveToTextFile(string filename) — создает текстовый файл с матрицей. Формат файла был описанвыше.
Private методы
void AddRow() — добавляет строку к матрице.
void AddColumn() — добавляет столбец к матрице.
Свойства
int Dimension — возвращает порядок матрицы. Этосвойство только для чтения.
Private свойства
List>mat — сама матрица.
List row — используется для добавления строк кматрице.
int rlength — длина строки матрицы.
int clength — длина столбца матрицы.
int mat_dimension — порядок матрицы. 2.3.2Класс Graph
Конструкторы класса
Graph(VertexMatrixmatrix) — cоздает графиз матрицы смежности matrix.
Graph(VertexMatrix mat,int radius) – cоздаетграф размером radius из матрицы смежности mat.
По умолчанию вершиныграфа располагаются по окружности радиуса Radius. Первая вершина графарасполагается в направлении девяти часов.
Public методы
int AddVertex(PointF coords)- добавляет к графувершину с координатами coords, при этом порядок матрицы графа увеличивается наединицу. Возвращает индекс добавленной вершины.
void DeleteVertex(intindex) — удаляет изграфа вершину с индексом index. При этом из матрицы графа также удаляетсясоответствующие вершине строка и столбец.
intGetVertexIndexFromPoint(PointF p) — возвращает индекс вершины графа, которой принадлежит точка скоординатами p. В случае если такой вершины не найдено, возвращает -1.
int[]GetVerticesFromNodePoint(PointF node) – возвращает массив размерностью 2, в которых находятся индексывершин графа, ребру которых (если такое существует) принадлежит точка скоординатами node. Если таких вершин не найдено или они не соединены ребром,функция возвращает null.
voidSetVertexCoordinats(int index, PointF coord) — устанавливает координаты вершины с индексом indexравными coord.
void ArrangeByCircle()
void ArrangeByCircle(intradius) — располагаетвершины графа по окружности радиусом Radius.
ImageDrawVerticesToImage(int[] indexes) — рисует вершины с индексами indexes графа в объект классаImage. Размеры области рисования вычисляются из нахождения вершин скоординатами максимально и минимально удаленными от осей X и Y.
Возвращает объект классаImage, в котором было произведено рисование.
void Draw(Graphics g) — рисует граф в области g.
void SaveToFile(stringfilename) — сохраняетграф в бинарный файл. Описание формата представлено в таблице 2.3.1.
Таблица 2.1 — Форматфайла .gСмещение (байт) DEC Размер (байт) Содержимое 2 Сигнатура файла .g: 0x0A0D 2 2 Версия файла ( 0 ) 4 2 Число вершин в графе (порядок матрицы смежности). 6 Число вершин графа в квадрате Матрица смежности графа. Хранится построчно sizeof(float)*2 * число вершин в графе Координаты вершин графа. Хранятся построчно: x1y1x2y2…xnyn
static GraphFromFile(string filename) — создает граф из файла графа.
List>FindAllCliques() — возвращаетсписок списков вершин графа, образующих клики.
Private методы
PointPlace pointClassify(PointFpoint, 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,
}
boolpointInTriangle(PointF p, PointF a, PointF b, PointF c) — возвращает true, если точка pпринадлежит треугольнику с координатами вершин a, b, c. В противном случаевозвращает false.
voidSubtractSet(List set, int vert) — удаляет вершину c индексом vert из списка set.
voidSubtractSet(List set1, List set2) — удаляет из списка set1 элементы,содержащиеся в set2 (если таковые присутствуют).
List G(intvert) — возвращаетсписок вершин, не смежных с вершиной с индексом vert.
Свойства
int Radius — возвращает размер графа.
int VertexRadius — возвращает радиус вершины.
Private свойства
VertexMatrix gmatrix — матрица вершин графа.
Listvertices — списоккоординат вершин графа.
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 методы
IDockContentGetContentFromPersistString(string persistString) — метод, необходимый для подготовкикомпонента DockPanel к работе и обеспечивает возможность размещения в нейдокингого окна класса MatrixWindow.
Параметр persistString –имя класса докингого окна.
void Form1_Load(objectsender, EventArgs e) — обработчиксобытия Load окна.
void saveDocument(boolsaveAs) — отображаетменю «Сохранить», предоставляющее возможность сохранить граф в файл.Если граф создан не из файла, пользователю предоставляется возможностьсамостоятельно выбрать имя, тип и путь к сохраняемому файлу посредствомстандартного диалога сохранения файла Windows. В случае, если параметр saveAsравен true, будет вызвано стандартное окно «Сохранить как» Windows.
void openDocument() — отображает стандартное диалоговоеокно открытия файла Windows. Если до вызова этой функции был создан граф илипроизводились изменения в существующем, будет выведено диалоговое окно спредложением сохранить граф.
void newDocument() — закрывает текущий документ (еслитаковой имеется) и создает пустой граф для последующей с ним работе впрограмме. Если до вызова этой функции был создан граф или производилисьизменения в существующем, будет выведено диалоговое окно с предложениемсохранить граф.
void UNDOAction() — отменяет последнее совершенноепользователем редактирование графа.
void REDOAction() — отменяет отмену последнегосовершенного пользователем редактирования графа.
void AddToUNDO(Graphgraph) — добавляет графgraph в стек отмены.
voiddockPanel_Paint(object sender, PaintEventArgs e) — событие Paint объекта классаdockPanel.
void DoToolAction(AppToolt, PointF coords) — выполняетдействие, предписанное инструментом t с начальными координатами coоrds.
voiddockPanel_MouseDown(object sender, MouseEventArgs e) — обработчик события MouseDown объектакласса dockPanel.
Используется дляполучения координат мыши и вызова метода DoToolAction.
voiddockPanel_MouseMove(object sender, MouseEventArgs e) — обработчик события MouseMove объектакласса. Используется для получения координат мыши инструментами «Курсор»и «Добавление ребер».
voiddockPanel_MouseUp(object sender, MouseEventArgs e) — обработчик события MouseUp объектакласса DockPanel. Используется для уведомления инструмента «Добавлениеребра» о том, что действие закончилось.
voidtoolStripButtonCursor_CheckStateChanged(object sender, EventArgs e) — изменяет выбранный инструмент наинструмент «Курсор».
voidtoolStripButtonAddVertex_CheckStateChanged(object sender, EventArgs e) — изменяет выбранный инструмент на инструмент«Добавление вершин».
voidtoolStripButtonDelVertex_CheckStateChanged(object sender, EventArgs e) — изменяет выбранный инструмент наинструмент «Удаление вершины».
voidtoolStripButtonAddNode_CheckStateChanged(object sender, EventArgs e) — изменяет выбранный инструмент наинструмент «Добавление ребер».
voidtoolStripButtonDelNode_CheckStateChanged(object sender, EventArgs e) — изменяет выбранный инструмент наинструмент «Удаление ребер».
voidtoolStripButtonUndo_Click(object sender, EventArgs e) — обработчик клика по кнопке «Отменить»панели инструментов. Нажатие этой кнопке приведет к откату состояния графа напредыдущее.
voidtoolStripButtonRedo_Click(object sender, EventArgs e) — обработчик клика по кнопке «Повторить»панели инструментов. Нажатие этой кнопки приведет к отмену отмены изменений вграфе.
voidPropertiesWindowToolStripMenuItem_CheckStateChanged(object sender, EventArgs e)- обработчик клика попункту меню Вид -> Окно свойств. Скрывает или показывает окно «Свойстваграфа».
void ViewToolStripMenuItem_DropDownOpening(objectsender, EventArgs e) — обработчик события DropDownOpening панели меню Вид — > Окно свойств. Вслучае если окно свойств видимо обработчик отмечает элемент меню.
voidрасположитьВершиныПоОкружностиToolStripMenuItem_Click(object sender, EventArgse) — обработчик клика поэлементу меню Граф — > Расположить вершины по окружности. Вызов этого менюприведет к расположению графа по радиусу окружности равному свойству Radiusграфа.
voidSaveToolStripMenuItem_Click(object sender, EventArgs e) — обработчик клика по пункту меню Файл- > Сохранить. Этот же обработчик имеет кнопка «Сохранить» напанели инструментов.
voidOpenToolStripMenuItem_Click(object sender, EventArgs e) — обработчик клика по пункту меню Файл- > Открыть. Этот же обработчик имеет кнопка «Открыть» панелиинструментов.
voidNewToolStripMenuItem_Click(object sender, EventArgs e) — обработчик клика по пункту меню Файл- > Новый. Этот же обработчик имеет кнопка «Новый» на панелиинструментов.
voidprintToolStripMenuItem_Click(object sender, EventArgs e) — обработчик клика по пункту меню Файл- > Печать. Этот же обработчик имеет кнопка «Печать» на панелиинструментов.
voidpageToolStripMenuItem_Click(object sender, EventArgs e) — обработчик клика по пункту меню Файл- > Предварительный просмотр. Этот же обработчик имеет кнопка «Предварительныйпросмотр» на панели инструментов. Открывает окно предварительногопросмотра документа перед печатью.
DialogResultuserWantsToSaveChanges() — выводит окно с предложением сохранить изменения в документе. Вариантыответа «Да», «Нет», «Отмена». Возвращаетструктуру DialogResult, содержащую вариант выбранного ответа.
bool closeApp() — функция вызывается при закрытииприложения. Вызывает вышеописанную функцию и, в случае утвердительного ответа,возвращает true. В остальных случаях возвращает false.
voidExitToolStripMenuItem_Click(object sender, EventArgs e) — обработчик клика по пункту меню Файл- > Выход. Вызывает закрытие приложения.
Private свойства
delegate IDockContent DeserializeDockContentddc — необходим дляподготовке контрола dockPanel к работе.
MatrixWindow matrixWindow- окно «Граф».
AppTool currTool — перечисление, определяющее текущийвыбранный инструмент.
bool mouseDown — определяет, нажата ли левая кнопкамыши. Используется для работы с инструментами «Курсор» и «Добавитьребро».
int selVertexIndex- индекс выбранной вершины, с которойработает инструмент.
int selVertexIndex2 — индекс второй выбранной вершины, скоторой работает инструмент «Добавить ребро».
Point nodePointStart — координата первой выбранной вершины,с которой работает инструмент «Добавить ребро».
Point nodePointEnd — координата второй вершины, с которойработает инструмент «Добавить ребро».
bool documentModified — определяет, были ли произведеныизменения в графе. Следует отметить, что если изменения имели быть, но былиотменены, документ считается не модифицированным.
string openedDocumentPath- путь к файлу графа илиматрице (если граф был создан из файла, else – "").
Stack stackUNDO- стек отмены. В негопомещается экземпляр графа, перед тем как произвести в нем изменения.
StackstackREDO — стекповтора. В него перемещаются элементы из предыдущего стека при произведениипользователем отмены совершенного им действия.
Следует отметить, чтовместо двух стеков может использоваться список элементов типа Graph, чтосэкономит ресурсы.
Константы класса
const stringGRAPH_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 методы
VertexMatrixGetMatrixFromDataGrid() — возвращает содержащуюся в окне матрицу.
voidFillDataGrid(VertexMatrix mat) — заполняет окно матрицей mat.
void SetDefValues() — устанавливает в окне значения«Размер графа», «Размер вершин» и «Число вершин»равными по умолчанию, это 60, 10 и 0 соответственно. Граф в главном окне приэтом не меняется.
void BlockGraphProp(boolblock) — устанавливаетвозможность изменять свойства графа в окне. При block = true изменять свойстванельзя, else можно.
Private методы
voiddataGridView1_ColumnAdded(object sender, DataGridViewColumnEventArgs e) — обработчик события ColumnAddedконтрола, содержащего матрицу графа. Добавляет к новосозданной колонке еепорядковый номер.
void ClearDataGrid() — очищает контрол, отображающий матрицуграфа. Граф при этом не изменяется.
voiddataGridView1_RowsAdded(object sender, DataGridViewRowsAddedEventArgs e)- обработчик события RowsAddedконтрола, отображающего матрицу графа. Нумерует новосозданные ячейки.
voiddataGridView1_CellMouseDown(object sender, DataGridViewCellMouseEventArgs e) — обработчик события CellMouseDownконтрола, отображающего матрицу графа. Меняет значение в кликнутой ячейке напротивоположное. Значения на главной диагонали матрицы изменению неподвергаются.
Public свойства
Класс не имеет publicсвойств.
Private свойства
Класс не имеет privateсвойств.2.3.6 Класс CliquesWindow
Конструкторы класса
CliquesWindow() — cоздает экземпляр классаCliquesWindow.
Public методы
Класс не имеет publicметодов.
Private методы
voidCliquesWindow_Load(object sender, EventArgs e) — обработчик события Load формы. Если public свойствоgraph не равно null вызывает процедуру поиска клик. В противном случае выводитна экран уведомление об отсутствии в графе клик.
void FindAllCliques(Graphg) — находит все клики вграфе g.
Image ScaleImage(Imagesource, int width, int height) — изменяет масштаб изображения source на width и height.Возвращает полученное изображение.
ShowCliqueMatrix(int[] c)- отображает матрицувершин c клики.
void SaveClique(intindex) — отображаетдиалог сохранения клики с индексом index в файл.
void CreateReport(stringfilename) — создаетфайлы отчета обо всех найденных в графе кликах.
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 – Реализацияалгоритма Брона-Кербоша на С#.
publicList> FindAllCliques()
{
List>output = new List>();
//сюдапомещаются вершины, образующие клику
ListM = new List();
//списоквершин графа
ListK = new List();
//список«отработанных» вершин
ListP = new List();
//вершина
intv;
StackstackV = new Stack();
Stack>stackM = new Stack>();
Stack>stackK = new Stack>();
Stack>stackP = new Stack>();
//списокнесмежных с вершиной вершин
ListGS = new List();
//заполняемсписок вершинами графа
for(int i = 0; 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);
}
}
returnoutput;
}
/*вычитает вершину из множества */
voidSubtractSet(List set, int vert)
{
for(int i = 0; i
{
if(set[i] == vert)
set.RemoveAt(i);
}
}
/*вычитает второе множество из первого */
voidSubtractSet(List set1, List set2)
{
for(int i = 0; i
for(int j = 0; j
if(set1.Count != 0 && i
if(set1[i] == set2[j])
set1.RemoveAt(i);
}
/*возвращает список вершин, не смежных с vert */
ListG(int vert)
{
Listret = new List();
for(int i = 0; i
if(gmatrix.Get(i, vert) == 0)
ret.Add(i);
returnret;
}
Примечание: 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, что позволило избежать мерцания рабочейобласти.
Листинг 3.2 — Первоначальноесостояние метода OnPaint класса DockPanel.
protectedoverride void OnPaint(PaintEventArgs e)
{
base.OnPaint(e);
if(DockBackColor == BackColor)
return;
Graphicsg = e.Graphics;
SolidBrushbgBrush = new SolidBrush(DockBackColor);
g.FillRectangle(bgBrush,ClientRectangle);
}
Листинг 3.3 — Состояниеметода OnPaint класса DockPanel после редактирования.
protectedoverride 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(Pointsource, 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.
PointPlacepointClassify(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
return PointPlace.RIGHT;
if ((a.X * b.X
return PointPlace.BEHIND;
if (Math.Sqrt(a.X * a.X +a.Y * a.Y)
return PointPlace.BEYOND;
if (point == origin)
return PointPlace.ORIGIN;
if (point == dest)
returnPointPlace.DESTINATION;
returnPointPlace.BETWEEN;
}
Далее достаточноопределить лежит ли точка в области, образованной ребрами треугольника. Этузадачу выполняет метод pointInTriangle, который принимает координатытреугольников и точку, принадлежность треугольникам которой следует проверить.Метод возвращает true, если точка принадлежит треугольнику и false в противномслучае.
Листинг 3.5 – МетодpointInTriangle класса Graph.
boolpointInTriangle(PointF p, PointF a, PointF b, PointF c)
{
return ((pointClassify(p,a, b) != PointPlace.LEFT) &&
(pointClassify(p, b, c)!= PointPlace.LEFT) &&
(pointClassify(p, c, a)!= PointPlace.LEFT));
}
Более подробное описаниеалгоритмов можно найти по следующим ссылкам:
1. algolist.manual.ru/maths/geom/belong/poly2d.php
2. algolist.manual.ru/maths/geom/datastruct.php3.4 Тестирование реализации алгоритма Брон-Кербоша
Тестированиеалгоритма производилось:
– на пустом графе
– на графе сединственной вершиной
– не графе с тремяне соединенными ребрами вершинами
– на графе из двухвершин, соединенных ребром
– на сложном графе
Стратегия тестирования
Сперва,с помощью определения понятия «клика», были найдены клики данногографа, после чего результаты сравнивались с результатом работы программы.
1. Тестирование напустом графе.
Теоретическиерасчеты: поскольку граф пуст (множество его вершин есть пустое множество) кликв нем нет.
Практическийрезультат: клик в графе не найдено, получено соответствующее уведомление(рисунок 3.5).
/>
Рисунок3.5. Сообщение об отсутствии клик в графе.
Результат:теоретические и практические расчеты сходятся – на данном наборе алгоритмработает верно.
2.Тестирование на графе с единственной вершиной.
Теоретическиерасчеты: граф не содержит клик — подмножество еговершин, такое, что между каждой парой вершин этого подмножества существуетребро и, кроме того, это подмножество не принадлежит никакому большомуподмножеству с тем же свойством.
Практическийрезультат: клик в графе не найдено, получено соответствующее уведомление(рисунок 3.5).
Результат:теоретические и практические расчеты сходятся – на данном наборе алгоритмработает верно.
3.Тестированиена графе с тремя не соединенными ребрами вершинами.
Теоретическиерасчеты: аналогичны расчетом в пункте 2.
Практическийрезультат: клик в графе не найдено, получено соответствующее уведомление(рисунок 3.5).
Результат:теоретические и практические расчеты сходятся – на данном наборе алгоритмработает верно.
4.Тестированиена графе из двух вершин, соединенных ребром.
Теоретическиерасчеты: граф удовлетворяет понятию «клика».
Практическиерезультаты: найдена одна клика, представляющая собой данный граф. Результат: теоретические и практические расчеты сходятся – наданном наборе алгоритм работает верно.
Тестированиена сложном графе.
Впрограмме был создан граф, представленный на рисунке 3.6.
/>
Рисунок3.6. Сложный граф, используемый в тесте.
Матрицасмежности графа:
100011
10111000
11001100
01001100
01110100
00111000
10000000
10000000
Теоретическиерасчеты: алгоритмом должны быть найдены следующиеклики: {1,2,3},{1,7},{1,8},{2,3,5},{2,4,5},{3,5,6},{4,5,6}.Практическиерезультаты: программой был сгенерирован отчет,представленный на листинге 3.6.
Листинг 3.6. Отчет,сгенерированный программой.
Graph untitled.g
Vertices count: 8
Matrix:
100011
111000
001100
001100
110100
111000
000000
000000
Cliques count: 7
Clique 1
Vertices: 1 2 3
Matrix:
1
1
Clique 2
Vertices: 1 7
Matrix:
Clique 3
Vertices: 1 8
Matrix:
Clique 4
Vertices: 2 3 5
Matrix:
1
1
Clique 5
Vertices: 2 4 5
Matrix:
1
1
Clique 6
Vertices: 3 5 6
Matrix:
1
1
Clique 7
Vertices: 4 5 6
Matrix:
1
1
Результат: алгоритмработает верно. 3.5Системные требования
Требования к аппаратномуобеспечению:
Процессор с тактовойчастотой 1000 МГц.
Не менее 256 Мбоперативной памяти.
Монитор с разрешением1024 x 768.
Клавиатура, мышь.
Требования к программномуобеспечению:
OS Windows Xp/Vista/7
NET Framework 2.0
Заключение
На языке программированияC# была выполнена реализация алгоритма Брона-Кербоша по поиску клик внеориентированном графе. Также были реализованы средства создания иредактирования неориентированного графа, а также поиска и отображения его клики создания отчета о найденных кликах. Также были получены следующие навыки:
– Умение применятьи модифицировать opensource-компоненты.
– Навык работы сдинамическими структурами данных.
– Навык организациипечати документов средствами .NET Framework.
/>/>/>/>/>/>/>/>/>/>/>Списокиспользованной литературы и источников
1. Bron C., KerboshJ. (1973), Algorithm 457 — Finding all cliques of an undirected graph, Comm. ofACM, 16, p. 575—577
2. Cazals, F.; Karande, C. (2008), «Anote on the problem of reporting maximal cliques», TheoreticalComputer Science 407 (1):564–568,doi:10.1016/j.tcs.2008.05.010
3. Graph Drawing: Algorithms for the Visualization of Graphs.
4. Drawing Graphs: Methods and Models (Lecture Notes inComputer Science).
5. http://sourceforge.net/projects/dockpanelsuite/
6. http://nzeemin.livejournal.com/184415.html
7. http://algolist.manual.ru/maths/geom/datastruct.php
8. http://algolist.manual.ru/maths/geom/belong/poly2d.php
Приложение
Руководство пользователя
Описание интерфейса
На рисунке 1 представленоглавное окно приложения. Цифрами отмечены:
1. Рабочая область приложения.
2. Созданный на рабочей области граф.
3. Главное меню приложения.
4. Панель инструментов приложения.
5. Окно, отображающее матрицу смежности ипараметры графа.
6. Матрица смежности графа.
7. Параметры графа.
/>
Рисунок 1. Главное окноприложения.
Панель инструментовпрограммы (Рис. 2):
1. Кнопка созданиенового документа.
2. Открытие новогодокумента.
3. Сохранениеизменений в документе.
4. Предварительныйпросмотр документа перед печатью.
5. Кнопка печатидокумента.
6. Отменитьсделанное изменение (если таковое имело быть).
7. Отменить отменуизменение (если таковое имело быть).
8. Инструмент «Курсор».
9. Инструмент «Добавитьвершину».
10. Инструмент «Удалитьвершину».
11. Инструмент «Добавитьребро».
12. Инструмент «Удалитьребро».
/>
Рисунок 2. Панельинструментов приложения.
Инструменты:
Инструмент «Курсор»необходим для изменения координат вершин графа. Для изменения координат вершиныграфа достаточно навести курсор на вершину, и зажать левую кнопку мыши. Теперь,пока кнопка не была опущена, координаты вершины будут меняться в соответствии сизменениями координат мыши. Для окончания перемещения графа необходимоотпустить кнопку мыши.
Инструмент «Добавитьвершину» создает новую вершину в кликнутой рабочей области. Строка истолбец этой вершины в матрице заполняются нулями.
Инструмент «Удалитьвершину» удаляет из графа вершину, по которой кликнули мышью.
Инструмент «Добавитьребро» создает новое ребро графа. Для этого нужно выделить одну из вершин,которой будет принадлежать ребро, мышью и, не отпуская левую кнопку, перетащитькурсор на вторую вершину.
Инструмент «Удалитьребро» удаляет ребро графа, по которому кликнули мышью.
На рисунке 3 представленоокно «Граф», задачей которого ставится отображение матрицы ипараметров графа. Оно позволяет добавлять и удалять вершины, а такжеустанавливать или удалять ребра графа. Окно является «плавающим»(Docking), что означает, что оно способно «прилипать» к краямглавного окна, а также быть полностью независимым от него. Отобразить илискрыть это окно возможно при помощи функции меню Вид — > Окно свойств.
/>
Рисунок 3. Докинговоеокно «Граф».
На рисунке 4 представленоокно «Клики графа», задачей которого ставится поиск и отображениявсех клик графа, а также сохранение отдельных клик в графический, текстовый илиграфовый (*.g) файл, а также создание отчета обо всех найденных кликах. Доступк окну можно получить из меня Граф -> Операции -> Поиск клик. Следуетотметить, что если граф не создан или в нем отсутствуют клики, пользователь неполучит доступ к окну, получив соответствующее уведомление.
/>
Рисунок 4. Окно «Кликиграфа».
Назначение кнопок:
Кнопка «Создатьотчет» создает отчет обо всех найденных кликах в текстовом формате.
Кнопка «Сохранитьклику» сохраняет выбранную клику в одном из выбранных форматах (граф,матрица, графический файл).
Кнопка «Закрыть»закрывает окно и дает доступ к главному окну приложения.
Формат отчета о найденныхкликах
Graph: имя_файла_графа
Vertices:число_вершин_в_графе
Matrix: Матрица графа
Cliques count:число_клик_в_графе
Clique номер_клики
Vertices:вершины,_образующие_клику
Matrix: Матрица клики.
Кликовый блок содержитчисло записей, равное числу клик в графе.
Работа с программой
Запуск программы
Запуск программыосуществляется стандартным способом запуска приложений Windows.
Создание графа
Граф создается либо путемманипуляции инструментами, либо из файла матрицы или графа. Для того чтобсоздать граф из файла матрицы или графа, следует кликнуть по кнопке «Открыть»панели инструментов, либо щелкнуть по пункту меню Файл — > Открыть. Впоявившимся диалоговом окне открытия файла выбрать нужный и нажать кнопку «Открыть»
Редактирование графа
Редактирование графаможет осуществляться как инструментами, так и при помощи окна «Граф».Данное окно позволят задавать связи между вершинами, а также изменять размерграфа.
Отмена сделанныхизменений
Для отмены произведенныхв графе изменений следует нажать кнопку «Отменить» на панелиинструментов, либо воспользоваться горячей клавишей Ctrl+Z. Также эта функциядоступна из меню «Правка», пункт «Отменить».
Отмена отмены сделанныхизменений
Для отмены отменыпроизведенных в графе изменений следует нажать кнопку «Повторить» напанели инструментов, либо воспользоваться горячей клавишей Ctrl+Y. Также этафункция доступна из меню «Правка», пункт «Повторить»
Поиск клик в графе
Для вызова окна поискаклик следует обратиться к пункту меню «Граф» — > «Операции сграфом» — > «Поиск клик».
Если в графе были найденыклики, появится окно «Клики графа», содержащее все изображения клик,а также их матрицы смежности. В противном случае будет показано уведомление оботсутствии в графе клик.
Создание отчета онайденных кликах
Для создания отчета онайденных кликах следует вызвать окно «Клики графа» (Меню «Граф»->«Операциис графом» ->«Поиск клик»). Если в графе были найдены клики,нажать кнопку «Создать отчет», тем самым, вызвав стандартное диалоговоеокно сохранения файла. В нем следует ввести имя создаваемого отчета и нажать накнопку «Сохранить». Программой будет сгенерирован отчет в текстовомформате, содержащий информацию об исходном графе и всех содержащихся в немкликах. Также будет создан графический файл в формате png, содержащий всеизображения найденных клик.
Сохранение созданногографа
Для сохранения созданногографа следует нажать на кнопку «Сохранить» панели инструментов иливоспользоваться горячей клавишей Ctrl+S. Эти действия приведут к вызовустандартного диалога сохранения файла Windows.
Выход из программы
Выход из программыосуществляется по горячей клавише Alt+F4, либо при помощи стандартных методовзакрытия оконных приложений Windows. Также завершить работу с программой можнопри помощи меню «Файл» -> «Выход». Следует отметить, чтоесли, во время работы с программой, создавался новый или модифицировался ужесуществующий граф, будет вызвано диалоговое окно с предложением сохранитьвыполненные изменения.