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

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

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. Это, скорее всего, зависит от сохранения данных, чем является частью алгоритма.