Реализация алгоритма определения изоморфизма графов при помощи языка C#
ОГЛАВЛЕНИЕ
Введение
Прикрепленный код является реализацией алгоритма изоморфизма графов. Данный алгоритм доступен в библиотеке сравнения графов VF, и существуют другие программы, которые формируют оболочку для вызова данной библиотеки , к прирмеру, из Python. То же самое может быть сделано для C#, но данный код реализует алгоритм только в C#, обходя все библиотеки C++ по множеству причин. Во-первых, это предлагает алгоритм, который полностью управляется средой. Во-вторых, мы поняли, что оригинальный код C++ не был настолько эффективен и хорошо написан, чтобы о нем говорить. В-третьих, библиотека VF была на самом деле создана для выполнения сравнений различных алгоритмов, поэтому вы сможете получить данные алгоритмы все скопом в случае, если вы будете использовать библиотеку.
Сведения общего характера
Два графа служат в качестве входных данных для решения задачи изоморфизма графов, а возвратным значением будет «Истина» или «Ложь», где результат «Истина» означает, что один граф повторяет другой. Алгоритм VF также выполняет проверку изоморфности подграфа, где есть такой подграф первого графа, который будет изоморфен второму графу. Он также позволяет наложение после того, как было получено соответствие. Также есть возможность проверки контекста, где узлы могут иметь атрибуты, и данные атрибуты могут быть проверены относительно соответствующих атрибутов изоморфного узла, а совпадение может быть отклонено на основе результатов таких тестов. Проще говоря , это позволяет использовать цветные узлы и одобрять сопоставление только одноцветных узлов различных сравниваемых графов.
Алгоритм VF по своей сути строит изоморфизм по одному совпадению за раз, и выполняет образованный поисковый перебор с возвратом для сопоставленных элементов. Для того, чтобы одобрить дополнение к найденному соответствию, существуют различные критерии для определения такой возможности. Некоторые из них просто улучшают производительность, но самым главным критерием является то, что только добавленное совпадение содержит изоморфизм группы, полученной до данного момента. Таким образом, сразу становится ясно, что если вы обработали все узлы во втором графе, то вы нашли искомый изоморфизм.
Мы будем использовать отсортированный список для некоторых внутренних наборов узлов, что означает, что мы будем ближе к получению верного соответствия. Это также даст нам более быстрое завершение алгоритма.