Реализация алгоритма определения изоморфизма графов при помощи языка C#

Данная статья демонстрирует реализацию алгоритма определения изоморфизма графов при помощи языка C#.

Введение

Прикрепленный код является реализацией алгоритма изоморфизма графов. Данный алгоритм доступен в библиотеке сравнения графов VF, и существуют другие программы, которые формируют оболочку для вызова данной библиотеки , к прирмеру, из Python. То же самое может быть сделано для C#, но данный код реализует алгоритм только в C#, обходя все библиотеки C++ по множеству причин. Во-первых, это предлагает алгоритм, который полностью управляется средой. Во-вторых, мы поняли, что оригинальный код C++  не был настолько эффективен и хорошо написан, чтобы о нем говорить. В-третьих, библиотека VF была на самом деле создана для выполнения сравнений различных алгоритмов, поэтому вы сможете получить данные алгоритмы все скопом в случае, если вы будете использовать библиотеку.

Сведения общего характера

Два графа служат в качестве входных данных для решения задачи изоморфизма графов, а возвратным значением будет «Истина» или «Ложь», где результат «Истина» означает, что один граф повторяет другой. Алгоритм VF также выполняет проверку изоморфности подграфа, где есть такой подграф первого графа, который будет изоморфен второму графу. Он также позволяет наложение после того, как было получено соответствие. Также есть возможность проверки контекста, где узлы могут иметь атрибуты, и данные атрибуты могут быть проверены относительно соответствующих атрибутов изоморфного узла, а совпадение может быть отклонено на основе результатов таких тестов. Проще говоря , это позволяет использовать цветные узлы и одобрять сопоставление только одноцветных узлов различных сравниваемых графов.

Алгоритм VF по своей сути строит изоморфизм по одному совпадению за раз, и выполняет образованный поисковый перебор с возвратом для сопоставленных элементов. Для того, чтобы одобрить  дополнение к найденному соответствию, существуют различные критерии для определения такой возможности. Некоторые из них просто улучшают производительность, но самым главным критерием является то, что только добавленное совпадение содержит изоморфизм группы, полученной до данного момента. Таким образом, сразу становится ясно, что если вы обработали все узлы во втором графе, то вы нашли искомый изоморфизм.
Мы будем использовать отсортированный список для некоторых внутренних наборов узлов, что означает, что мы будем ближе к получению верного соответствия. Это также даст нам более быстрое завершение алгоритма.

 

Использование кода

interface IContextCheck
{
    bool FCompatible(IContextCheck icc);
}

Graph graph = Graph();
// ID первого узла всегда равен 0 а остальные следуют
// за ним, тем самым у нас узлы 0, 1, 2 и 3
graph.InsertNodes(4)
graph.InsertEdge(0,1);
graph.InsertEdge(1,2);
graph.InsertEdge(2,3);
graph.InsertEdge(3,0);

...
VfState vfs = new VfState(graph1, graph2);
bool fIsomorphic = vfs.FMatch();
if (fIsomorphic)
{
    // mapping[i] это узел в graph2 который соответствует 
    // узлу i в graph1...

    int[] mapping = vfs.Mapping1To2;
    ...

Также существует Mapping2To1 с установлением соответствия от graph2 к graph1. В случае изоморфизма подграфов (что используется по умолчанию), алгоритм ищет подграф графа graph1 , который будет изоморфен графу graph2.  VfState может получать два параметра типа boolean, либо в виде VfState(graph gr1, graph gr2, boolean fIso) или VfState(graph gr1, graph gr2, boolean fIso, boolean fContextCheck). Если fIso будет true, то алгоритм ищет какой-то определенный изоморфизм. Это более эффективно, чем поиск изоморфизма подграфа. Если fContextCheck является true, то все атрибуты узлов были контекстно проверены относительно своих двойников в соответствии, как указано выше.

В дополнение к указанным выше сигнатурам для конструктора VfState, существует еще одна, которая получает третий параметр типа boolean: VfState(graph gr1, graph gr2, boolean fIso, boolean fContextCheck, boolean fFindAll). По умолчанию fFindAll является равным false. Если он равен true, то после нахождения соответствия, вы можете получить список всех соответствий всех изоморфизмов. Каждый изоморфизм представлен в списке посредством структуры FullMapping, которая просто содержит соответствия 1 к 2 и 2 к 1 в двух массивах типа int[], как это показано в следующем примере.

...
VfState vfs = new VfState(graph1, graph2, false, false, true);
bool fIsomorphic = vfs.FMatch();
if (fIsomorphic)
{
    // mapping[i] это узел в graph2 который соответствует
    //узлу i в graph1...foreach(FullMapping fm in vfs.Mappings)
    {
        int[] mapping1to2 = fm.arinodMap1To2;
        int[] mapping2to1 = fm.arinodMap2To1;
        ...

Обзор алгоритма

bool FMatchRecursive()
{
    Match mchCur;
    CandidateFinder cf;

    if (FCompleteMatch())
    {
        return true;
    }

    cf = new CandidateFinder(this);
    while ((mchCur = cf.NextCandidateMatch()) != null)
    {
        if (FFeasible(mchCur))
        {
            BacktrackRecord btr = new BacktrackRecord();
            AddMatchToSolution(mchCur, btr);
            if (FMatchRecursive())
            {
                _fSuccessfulMatch = true;
                return true;
            }
            btr.Backtrack(this);
        }
    }
    return false;
}

Стоит заметить, что это рекурсивная версия, и она проста для понимания, но ifdef  было убрано для того, чтобы она стала не рекурсивной. Вы можете вернуть ifdef и проверить, работает ли он  посредством кода NUnit, но он может переполнить стэк довольно большими графами, при этом будет менее эффективным. Метод использует CandidateFinder для нахождения потенциальных совпадений, пробегает по ним и использует доступный метод для выполнения более точной проверки. Данная проверка обеспечивает то, что совпадение не будет разбивать изоморфизм, который мы пока что собрали. BacktrackRecord позволяет обратить эффект вызова AddMatchToSolution в случае, если совпадение не сработает. Мы условно добавляем совпадение к текущему изоморфизму, расширяем его область в каждом графе и рекурсивно проверяем, можем ли мы расширить данный новый изоморфизм к более полноценному соответствию относительно графа graph2. Если это возможно, то мы закончим и возвратим true, а если нет, то мы вернемся в прошлое состояние, до того момента, как мы добавили совпадение, и поищем другие потенциальные совпадения в основном цикле.

Настоящими ключевыми функциями являются NextCandidateMatch и FFeasible. Данные две функции значительно зависят от разделения  узлов на четыре набора по каждому графу. Первый набор, который мы будем называть I1/I2 по графам graph1/graph2, является набором узлов, которые участвуют в изоморфизме, составляемом на каждом этапе алгоритма. Второй набор - T1/T2 для графов graph1/graph2 - является набором узлов, которые имеют хотя бы одно ребро, указывающее в сторону узла в I1/I2. Третий набор - F1/F2 для графов graph1/graph2 - это набор узлов, которые имеют хотя бы одно ребро, указывающее на них из набора I1/I2. Учтите, что если узел имеет как предшественников, так и последователей в I1/I2, то он будет членом обоих наборов F1/F2 и T1/T2. Наконец, узлы, которые не связаны ни с одним узлом изоморфизма, будут членами четвертного набора D1/D2.

Эти группы поддерживаются с использованием enum:

[Flags]
enum Groups
{
    ContainedInMapping = 1,     // Содержится в соответствии
    FromMapping = 2,            // Находится за пределами соответствия, но на него ссылаются из соответствия 
    ToMapping = 4,              // Находится за пределами соответствия, но указывает на узел в соответствии 
    Disconnected = 8            // Находится за пределами соответствия, без каких-либо ссылок на узлы в соответствии
}

Каждый узел содержит поле enum, которое указывает, к какой группе он принадлежит. В дополнение, класс VfState содержит список каждой из данных групп, отсортированный по узлам.

Очевидно то, что если мы сохраняем изоморфизм путем добавления совпадений между узлом N1 в графе graph1 и  N2 в графе graph2, то необходимо соблюдать некоторые структурные правила, и это то, как наш поиск способен очень быстро перебирать кандидатов для того, чтобы выбрать некоторые из них и отложить несовпадающие. К примеру, CandidateFinder обеспечивает то, что оба узла будут взяты из T-наборов, или оба из F-наборов, D-наборов. Случай с  T-наборами исходит из наблюдения того, что если N1 точек включены в  текущий изоморфизм, то также должны быть включены и N2. Аналогично для наборов F и D. Если не существует узлов в T1 или T2, то поисковик кандидатов смотрит в F-наборах, а после этого в D-наборах. Когда CandidateFinder ищет в определенной группе на совпадения, он делает это в убывающей степени, поскольку таким образом отсортированы списки. Это, конечно, имеет некоторые последствия. Во-первых, у нас есть больше шансов нахождения совпадения верных узлов на ранней стадии. Во-вторых, поскольку N1 должен иметь столько же ребер, что и N2 (помните, что граф graph2 может входить в подграф графа graph1), то мы можем закончить цикл, как только мы найдем узел в списке T1 , имеющем более низкую степень, чем N2 , поскольку теперь все узлы будут иметь более низкие степени. На самом деле, если истинный изоморфизм будет найден, то мы можем остановиться в том случае, если первый узел в T1 будет иметь степень, отличную  от первого узла в T2. Существует множество ситуаций, где у нас равные шансы в случае истинного изоморфизма или a >= условию отказа в случае с подграфом изоморфизма. Для этого у нас есть делегат в классе VfState, fnComp, который выполняет один из данных тестов, и мы устанавливаем его однажды, когда будет собран VfState , и затем используем fnComp для этих тестов в дальнейшем коде.

Как только CandidateFinder выберет подходящее совпадение, мы произведем дальнейшую проверку при помощи FFeasible(). Существует четыре теста, которые применяются по отношению к совпадению для того, чтобы оно прошло проверку FFeasible(). Первый и основной тест просто проверяет то, что совпадение при добавлении к изоморфизму не нарушит его. Точнее, каждый узел в изоморфизме, который связан с N1, должен соответствовать узлу, который аналогично связан с N2. В дополнение к этому, если выполняется контекстная проверка, то она также применяется здесь в проверке на годность, а совпадения могут быть отклонены, если их атрибуты конфликтуют. На самом деле, это единственное абсолютное требование. Пока это истина, и мы добавляем узлы, мы всегда будем сохранять верный изоморфизм узлов в I-наборах, поэтому, когда все узлы graph2 будут в I2, у нас будет наш завершенный изоморфизм. Тем не менее, используя только данный критерий, вы допустите множество совпадений, которые затем придется возвращать в исходное состояние, поэтому нам нужно сокращать наш выбор на данном этапе, а этим и займутся остальные три требования FFeasible.

Остальные три требования на самом деле просто версии того же правила, примененные к группам T, F и D, поэтому мы обсудим только T-группы, но та же самая логика применяется к другим двум группам. Мы все еще предполагаем, что мы добавляем совпадение между узлами N1 графа graph1 и N2 графа graph2. Нам необходимо, чтобы число входящих в узлы ребер из T1 к N1 превышало число входных в узлы ребер в T2 к N2. Это также касается и выходящих ребер. Это еще одна ситуация , где мы можем использовать fnComp , как показано выше, для того, чтобы провести тест на равенство с изоморфизмом или на неравенство для подграфа изоморфизма. Этот же тест применяется к наборам F и D. Код первого теста описан ниже (входящие ребра из узлов T1 сравниваются с входящими ребрами из узлов T2):

if (!fnCmp(
    GetGroupCountInList(lstIn1, _vfgr1, Groups.FromMapping),
    GetGroupCountInList(lstIn2, _vfgr2, Groups.FromMapping)))
{
    return false;
}

Здесь GetGroupCountInList() просто подсчитывает узлы в списке первого аргумента, которые расположены в верной группе для графа, и предоставлены от _vfgr1 (graph1) или _vfgr2 (graph2). lstIn1 является всего лишь списком узлов, которые обладают ребром, указывающим в сторону N1, а также и для lstIn2.

Когда мы добавляем совпадение к изоморфизму, это потенциально переносит несколько других узлов в другие группы. Метод AddMatchToSolution() следит за всеми передвижениями в журнале возвратов, поэтому все может быть возвращено в случае, если сопоставление было безуспешным. Записи возврата являются списками ссылок BacktrackAction, каждый из которых либо является движением в изоморфизм, либо движением из одной группы в другую.

Это завершает обзор алгоритма. Мы не включили преобразование между Graph и VfGraph. Основным отличием является сортировка узлов в сторону увеличения их степени в VfGraph и установка различных списков узлов при подготовке к алгоритму VF. Все узлы изначально располагаются в группе D, а группа I является пустой. Мы также сохраняем сопоставление между не отсортированными узлами в оригинальной структуре Graph и узлами в структуре VfGraph , тем самым мы может сортировать все это в конце и возвратить сопоставления посредством Mapping2To1 и Mapping1To2, которые ссылаются на идентификаторы узлов в оригинальных объектах Graph , а не на идентификаторы, используемые в VfGraph. Это, скорее всего, зависит от сохранения данных, чем является частью алгоритма.

Производительность

Когда мы рассматривали код, мы хотели найти, сколько совпадений у нас будет найдено при поиске кандидатов, сколько будет найдено при прохождении через тестер годности, и сколько пройдут оба теста, но были возвращены обратно. У нас есть наш создатель произвольных графов, и когда он создал граф с тысячью узлами, мы удивились, когда увидели, что ни один из узлов не был возвращен – комбинация поисковика кандидатов и тестера пригодности работали идеально. Это казалось невозможным, и для проверки, мы закомментировали вызов в том месте, где узлы были возвращены, и запустили заново код 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 будет работать, так что в этом случае его также придется убрать.

Скачать исходник - 83.8 KB