Реализация алгоритма определения изоморфизма графов при помощи языка C# - Использование кода
ОГЛАВЛЕНИЕ
Использование кода
Код реализован в виде библиотеки классов. Существует два основных класса, необходимых для взаимодействия с кодом. Первым является класс Graph , который используется для создания/манипуляции вашим графом. Единственным конструктором для Graph является стандартный, который не принимает никаких параметров. Как только у вас будет граф, вы можете вставить узлы, используя InsertNode() и ребра, используя InsertEdge(). Обычно InsertNode вызывается без каких-либо параметров, и в таком случае он возвращает целочисленный идентификатор (ID) для вставленного узла. Эти идентификаторы могут быть использованы в вызове InsertEdge(int node1, int node2) для вставки ребер между узлами. Альтернативным способом является принятие InsertNode единого параметра object , который представляет атрибут для вставленного узла. Атрибуты могут быть опциональными, или же они могут представлять реализацию интерфейса IContextCheck. IContextCheck очень прост и выглядит следующим образом:
interface IContextCheck
{
bool FCompatible(IContextCheck icc);
}
Как показано ниже, соответствие может быть установлено на использование данных атрибутов проверки контекста, а в этом случае любые два узла, которые будут обследованы, будут обработаны контекстной проверкой. Если контекстная проверка возвратит false, то тогда соответствие не разрешено. В этом случае все атрибуты в графе должны реализовать IContextCheck. Любые узлы, которые не имеют атрибутов, будут соответствовать любому другому узлу. Атрибуты также могут быть привязаны к ребрам посредством InsertEdge(iNode1, iNode2, object attr), но они (пока что) не могут быть использованы с таким же эффектом, как атрибуты узлов.
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);
Также существуют методы удаления узлов (DeleteNode(int ID)) и ребер (DeleteEdge(int idFrom, idTo)). Пожалуйста, учтите, что мы вводим направленные ребра, тем самым InsertEdge(1,0) – это нечто другое, чем вставка InsertEdge(1,0).
Как только у вас будет пара графов, которые вы хотели бы проверить на изоморфность, вы можете создать объект VfState , а они будут использовать конструктор VfState(Graph graph1, Graph graph2). VfState может быть использован для проведения проверки следующим образом:
...
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;
...