14
Существует ли алгоритм или эвристика для изоморфизма графа?Изоморфизм графиков
Сводка: график может быть представлен на разных рисунках.
Какой лучший подход найти другой рисунок графика?
A
ответ
13
Это чертовски проблематично.
Основная идея состоит в том, чтобы упростить график в канонической форме, а затем выполнить сравнение канонических форм. С этой целью генерируются связующие деревья, но связующие деревья не уникальны, поэтому вам нужно создать канонический способ их создания.
После того, как у вас есть канонические формы, вы можете выполнить сравнение изоморфизма (относительно) легко, но это только начало, поскольку неизоморфные графы могут иметь одинаковое остовное дерево. (например, подумайте о охватывающем дереве T и о единственном добавлении к нему ребра для создания T. Эти два графика не изоморфны, но они имеют одинаковое остовное дерево).
Другие методы включают в себя сравнение дескрипторов (например, количество узлов, количество ребер), которые в целом могут создавать ложные срабатывания.
Предлагаю вам ознакомиться с вики-страницей о graph isomorphism problem. У меня также есть книга, чтобы предложить: "Graph Theory and its applications". Это тома, но стоит каждой страницы.
Как и из вашего следствия, любое возможное пространственное распределение вершин данного графа является изоморфным. Таким образом, два изоморфных графа имеют одинаковую топологию и, в конце концов, один и тот же граф, с топологической точки зрения. Другое дело, например, найти те изоморфные структуры, которые обладают определенными свойствами (например, с не пересекающимися ребрами, если существует), и это зависит от свойств, которые вы хотите.
+0
:) Спасибо. Мне нравятся графические книги :) – DarthVader
+0
Спасибо за объяснение, я просто ищу простую эвристику, если существует. – DarthVader
+1
Тогда мое предложение - взглянуть на метод NetworkX. Это библиотека python для обработки графов, очень хорошая и хорошо документированная. –
3
Есть алгоритмы для этого, однако у меня не было причин серьезно их расследовать. Я считаю, что Дональд Кнут пишет или написал на эту тему в своей серии «Искусство вычислить» во время своего второго прохода в (ре), написав их.
Что касается простого способа сделать что-то, что может практиковаться на небольших графиках, я бы рекомендовал подсчитать градусы, а затем для каждой вершины также отметить набор степеней для смежных соседних вершин. Тогда это даст вам набор потенциальных изоморфизмов вершин для каждой точки. Затем попробуйте все это (с помощью грубой силы, но выбрав вершины в порядке возрастания потенциальных множеств изоморфизма вершин) из этого ограниченного множества. Интуитивно, большинство геометрических изоморфизм можно практически вычислить таким образом, хотя, очевидно, будут вырожденные случаи, которые могут занять много времени.
2
Мой проект - Griso - на sf.net: http://sourceforge.net/projects/griso/ с этим описанием:
Griso является утилита график тестирования изоморфизмом написан на C++. Он основан на моем собственном алгоритме POLYNOMIAL-TIME (в этом пункте соль проекта). См. Ввод/вывод образца Griso на странице http://funkybee.narod.ru/graphs.htm.
+3
Что побудило вас придумать свой собственный алгоритм? У вас есть документ, описывающий его и сравнивающий его по производительности с популярными алгоритмами (vf2, nauty) на разных типах графиков? – Szabolcs
+0
@Szabolcs, что меня мотивировало? Это алгоритм ** полиномиального времени **. – trg787
+0
Конечно, было бы невероятно, если бы алгоритм был на 100% правильным. Но я еще не встретил контрпример для него (для версии Griso_3in1). – trg787
6
Одним из лучших алгоритмов для нахождения изоморфизмов графа является VF2.
Я написал high-level overview of VF2 as applied to chemistry - там, где он широко используется. Сообщение касается различий между VF2 и Ullmann. Существует также from-scratch implementation of VF2 written in Java, что может быть полезно.
+1
спасибо. Я уже сделал с графиками. :) – DarthVader
2
Недавно я наткнулся на следующую бумагу: http://arxiv.org/abs/0711.2010 В настоящем документе предлагается «полиномиальное время алгоритм для Изоморфизм графов»
4
Очень похожая проблема - автоморфизм графа - может быть решена с помощью saucy, который доступен в исходном коде , Это находит все симметрии графика. Если у вас есть два графика, соедините их в один, и любой изоморфизм можно обнаружить как автоморфизм объединения.
Отказ от ответственности: Я являюсь одним из соавторов дерзкого.
1
nauty и следы программы для вычисления групп автоморфизмов графов и орграфов [*]. Они также могут создавать канонические этикетки. Они написаны в переносном подмножестве C и работают на значительном числе различных систем.
- AutGroupGraph команда в GRAPE's package of GAP.
- bliss: еще одна симметрия и каноническая программа для маркировки.
- conauto: сборник изображений.
0
Что касается эвристики: я фантазировал о модифицированном алгоритме Ульмана, в котором вы не только используете первый поиск по ширине, но и смешиваете его с глубиной первого поиска, так что сначала вы интенсивно используете поиск по ширине, чем вы устанавливаете предел для анализа широты и углубляетесь после проверки нескольких соседей, и вы уменьшаете каждый шаг на определенную сумму. Это практически то, как я нахожу свой путь на карте: сначала найдите себя с первым поиском по ширине, затем найдите маршрут с глубиной первого поиска - в основном, и это лучшая эволюция моего мозга, когда-либо изобретенная. :) В долгосрочной перспективе некоторый интеллект может быть добавлен для увеличения ширины первого соседнего счетчика поиска в критических вершинах - например, если имеется большое количество соседних вершин с одинаковым количеством граней. Как и проверка вашего фактического маршрута иногда с автомобилем (без GPS).
0
Я выяснил, что алгоритм относится к категории k-мерных алгоритмов Вайсфейлера-Лехмана, и он терпит неудачу с правильными графами. Для более здесь:
http://dabacon.org/pontiff/?p=4148
Оригинальное сообщение следующим образом:
Я работал над проблемой, чтобы найти изоморфные графы в базе данных графиков (содержащих химические составы).
Вкратце, алгоритм создает хэш графика, используя метод итерации мощности. Могут быть ложноположительные хеш-столкновения, но вероятность этого чрезвычайно мала (у меня не было таких столкновений с десятками тысяч графиков).
Путь алгоритм работает следующим образом:
Do N (где N радиус графа) итераций.На каждой итерации и для каждого узла:
- Сортировка хэш (из предыдущего шага) соседей узла
- Hash конкатенированной отсортированных хешей
- Заменить хэш узла с вновь вычисленной хэш
На первом шаге на хост узла влияют его непосредственные соседи. На втором этапе хеш узла влияет на окрестности 2-х прыжков от него. На N-м шаге на хэш-узел узла будет влиять окрестности N-hops вокруг него. Поэтому вам нужно продолжить выполнение шагов Powerhash для N = graph_radius. В конце концов, хэш хэда центра графа будет затронут всем графиком.
Чтобы создать окончательный хэш, выполните сортировку хэшей узла конечного шага и объедините их вместе. После этого вы можете сравнить финальные хэши, чтобы найти, являются ли два графика изоморфными. Если у вас есть метки, добавьте их (на первом шаге) во внутренние хэши, которые вы вычисляете для каждого узла.
Существует более фон здесь:
https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF
Вы можете найти исходный код этого здесь:
https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py
этот алгоритм может быть ответ ваш ищут. [ссылка для алгоритма полиномиального времени для изоморфного тестирования и отображения графа] (http://stackoverflow.com/questions/38579338/graph-isomorphic-polynomial-time-algorithm-counterexample) – Ahmad