Вы можете найти актуальным следующий вопрос ...
По сути, автомат можно минимизировать с помощью хорошо известных алгоритмов из учебников по теории автоматов. Hopcrofts является примером. Существует ровно один минимальный автомат, эквивалентный любому данному автомату. Однако этот минимальный автомат может быть представлен по-разному. Построение безопасной канонической формы - это в основном вопрос перенумерации узлов и упорядочения таблицы смежности с использованием информации, которая важна для определения автомата, а не с помощью информации, специфичной для представления.
Основной принцип должен распространяться на общие графы. Возможность минимизации графиков зависит от их семантики, но основная идея перенумерации узлов и сортировки списка смежности по-прежнему применима.
Другие ответы здесь предполагают некоторые вещи о ваших графах - например, что узлы имеют уникальные метки, которые можно упорядочить и которые важны для семантики ваших графов, которые можно использовать для идентификации узлов в матрице или списке смежности. Это просто не сработает, если вы заинтересованы, например, в морфимах немаркированных графов. Различные способы нумерации узлов (и, следовательно, упорядочения списка смежности) приведут к различным каноническим формам для эквивалентных графов, которые просто будут представлены по-разному.
Что касается перенумерации и т. Д., То подход заключается в том, чтобы заимствовать и адаптировать принципы из алгоритмов минимизации автоматов. В принципе ...
Создание вектора блоков (наборов узлов). Первоначально, заполните это одним блоком на класс узлов (то есть на отдельную аннотацию узла). Модификация здесь заключается в том, что мы упорядочиваем их по деталям аннотации (а не по идентификаторам узлов, характерным для представления).
Для каждого класса (аннотации) ребер по порядку оцените каждый блок. Если каждый узел в блоке может следовать текущему типу ребра для достижения того же набора следующих блоков, оставьте его без изменений. В противном случае разделите его по мере необходимости, чтобы получить максимальные блоки, которые достигают этой цели. Держите эти разделенные блоки сгруппированными вместе в векторе (сохраните существующее упорядочение, просто уточните его немного), и упорядочите разделенные блоки на основе подходящего упорядочения наборов следующего блока. Например, используйте битовые векторы до текущего вектора блоков с установленным битом для каждого достижимого блока, следуя текущему типу фронта. Чтобы упорядочить битовые векторы, рассматривайте их как большие целые числа.
РЕДАКТИРОВАТЬ - я забыл упомянуть - во втором маркере, как только вы разбиваете блок, вы перезагружаетесь с первым блоком в векторе и аннотацией первого ребра. Очевидно, что наивная реализация будет медленной, поэтому возьмите этот принцип и используйте его для адаптации алгоритма минимизации Хопкрофта.
Если в итоге вы получите блоки с несколькими узлами, эти узлы эквивалентны. Означает ли это, что они могут быть объединены или нет, зависит от вашей семантики, но относительное расположение узлов внутри каждого такого блока явно не имеет значения.
Если иметь дело с графами, которые можно минимизировать (например, автоматными орграфами), я подозреваю, что лучше сначала минимизировать, хотя я до сих пор не дошел до реализации этого самостоятельно.
Ключевым моментом, конечно же, является обеспечение того, что ваше перенумерация чувствительна только к важным деталям графа - его структуре и аннотациям - а не к вещам, которые есть только там, чтобы вы могли построить представление, такое как идентификаторы / адреса узлов и т. д.
После того, как вы заказали блоки, получить каноническую форму будет легко.