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

return PointPlace.LEFT;

if (sa < 0.0)

return PointPlace.RIGHT;

if ((a.X * b.X < 0.0) || (a.Y * b.Y < 0.0))

return PointPlace.BEHIND;

if (Math.Sqrt(a.X * a.X + a.Y * a.Y) < Math.Sqrt(b.X * b.X + b.Y * b.Y))

return PointPlace.BEYOND;

if (point == origin)

return PointPlace.ORIGIN;

if (point == dest)

return PointPlace.DESTINATION;

return PointPlace.BETWEEN;

}

Далее достаточно определить лежит ли точка в области, образованной ребрами треугольника. Эту задачу выполняет метод pointInTriangle, который принимает координаты треугольников и точку, принадлежность треугольникам которой следует проверить. Метод возвращает true, если точка принадлежит треугольнику и false в противном случае.

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

bool pointInTriangle(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. http://algolist.manual.ru/maths/geom/belong/poly2d.php

2. http://algolist.manual.ru/maths/geom/datastruct.php

3.4 Тестирование реализации алгоритма Брон-Кербоша

Тестирование алгоритма производилось:

– на пустом графе

– на графе с единственной вершиной

– не графе с тремя не соединенными ребрами вершинами

– на графе из двух вершин, соединенных ребром