Реализация алгоритма определения изоморфизма графов при помощи языка C# - Производительность
ОГЛАВЛЕНИЕ
Производительность
Когда мы рассматривали код, мы хотели найти, сколько совпадений у нас будет найдено при поиске кандидатов, сколько будет найдено при прохождении через тестер годности, и сколько пройдут оба теста, но были возвращены обратно. У нас есть наш создатель произвольных графов, и когда он создал граф с тысячью узлами, мы удивились, когда увидели, что ни один из узлов не был возвращен – комбинация поисковика кандидатов и тестера пригодности работали идеально. Это казалось невозможным, и для проверки, мы закомментировали вызов в том месте, где узлы были возвращены, и запустили заново код NUnit. Оба теста провалились, поэтому механизм возврата все же был полезен.
Оказывается, в случае с произвольным графом существует пара узлов, которые имеют максимальную степень. У этих узлов, у которых одинаковая максимальная степень, должно также быть одинаковое количество входящих и выходящих ребер для того, чтобы они прошли тест на пригодность. Это однозначно определяет вхождение первого совпадения в изоморфизм. С данного этапа по мере построения изоморфизма, шансы того, что изоморфизм сам по себе неверен, практически равны нулю, поскольку мы подразумеваем, что в противном случае мы подразумеваем существование двух изоморфически идентичных частей в произвольном графе. То же самое происходит с добавлением новых совпадений, поскольку они должны быть прикреплены к текущему изоморфизму и, скорее всего, могут подходить только одному месту изоморфизма. У нас есть высокий шанс того, что мы получим верные первые совпадения, а после них шансы, наоборот, еще больше растут, чем падают. Следовательно, нас стало интересовать то, как хорошо будет работать данный алгоритм с произвольными графами. Фактически, если мы предполагаем отсутствие возврата и постоянную среднюю степень узлов, нам кажется, что алгоритм будет O(n^2), что очень хорошо.
Конечно, на данном этапе нам необходимо исследовать гораздо худшие случаи. Кажется очевидным, что возвратов будет больше, в случае, если граф будет чересчур автоморфный, это означает, что большие части графа изоморфны другим. Наихудшим примером, по нашему мнению, будет сетка – узлы расположены на пересечениях линий сетки, а ребра расположены по данным линиям. Когда мы попробовали применить данный пример, то, как и ожидалось, мы получили множество возвратов. Мы поняли, что хотя мы и ждали худшего результата, мы решили соединить противоположные углы сетки одного графа ребром, которого мы не добавляли в другой. Это, скорее всего, и есть худший случай, потому что нам пришлось отменить пробу после долгого ожидания. Поскольку углы имели более низкую степень, чем узлы посередине, то они были проверены на изоморфность после тех, что в центре, а поскольку они были единственными неизоморфным частями графа, то алгоритм пытался провести миллиарды возвратов. Для проверки этого, вместо одного графа между двумя узлами, мы вставили несколько, тем самым их высшая степень вызвала их проверку с самого начала. Это сразу привело к успешному завершению. Конечно, мы пытались выполнить это с сеткой размера 30x30, и может алгоритм работал бы быстрее для более мелких версий графов. Эта проблема могла бы быть удалена простой проверкой степеней узлов. Поскольку мы уже сортируем узлы согласно степеням, то это не является сложной задачей. Это также будет работать для подграфов, где нам необходимо установить соответствие один-к-одному между узлами во втором графе и узлами с наивысшей степенью в первом графе.
Другой потенциальной проблемной областью может быть сравнение графа с более высокими степенями с графом, у которого степени заметно ниже. Это может удалить все преимущество от сортировки узлов, и уклонению к приведению изоморфных узлов вместе в поисковике кандидатов. Мы не думаем, что это было слишком большой проблемой, потому что оригинальный алгоритм, описанный в начале данной статьи, изначально никогда не применял сортировку. Конечно, если степени не слишком высоки, то это, скорее всего, будет более легким случаем, поскольку узлы будут быстрее проверены. Экстремальным случаем, любое соответствие 1-1 подойдет в случае, если граф будет полным.
Урок, который нам стоит выучить, заключается в том, что наихудший случай может быть ужасным, но меньшие графы или более автоматические графы могут иметь производительность O(n^2).
Мы также сделали некоторый опыт со временем (но мы не исключили фоновую обработку), и составили следующую статистику для произвольных графов в наших тестах:
Заметьте, что время/узел (time/node) были умножены на 4000 ,чтобы все было отражено красиво в одном рисунке. Фактор загрузки ребер для графа с узлами был(о) 0.1 , тем самым каждый узел имел в среднем примерно 100 входящих и 100 выходящих ребер. Нам хотелось иметь примерно равное значение степеней для всех графов, поэтому для графов других размеров фактор загрузки ребер обратно пропорционален числу узлов. Тем самым фактор загрузки для графа с 2000 узлами будет 0.05.
Интересные особенности
Кое- что стоит отметить. Во-первых, когда мы говорим об изоморфизме графа, определение подграфа здесь является равным графу, у которого отсутствуют некоторые узлы и связанные с ними ребра. Это означает то, что вы не можете убрать ребра напрямую в подграфе, если вы не убрали связанный с ними узел. Хоть это и не большая проблема, но это не было реализовано в алгоритме.
Код включает тестирование NUnit. Мы рекомендуем NUnit, а также уникальное дополнение TestDriven.NET Visual Studio. Они оба бесплатны и достойны того, чтобы их загрузили. Тем не менее, если вы не можете понять данные простые шаги алгоритма, то вам нужно удалить ссылки на NUnit.FrameWork в проекте и определение NUNIT из конфигурации отладки. Даже в этом случае, вы, скорее всего. поймете код, просто изучив код NUnit. В программе- примере нет никакой проверки или демо-версии, поскольку она была проверена полностью посредством NUnit.
Наконец, мы предполагаем, что код работает отлично на Mono, но он не был проверен. Мы не уверены, что NUnit будет работать, так что в этом случае его также придется убрать.