Как хэшировать и проверять равенство объектов с циклическими ссылками

Question

У меня есть циклическая графоподобная структура, представленная Node объектами. Узел - это либо скалярное значение (лист), либо список из n> = 1 Узлов (внутренний узел).

Из-за возможных циклических ссылок я не могу просто использовать рекурсивную функцию HashCode (), которая объединяет HashCode () всех дочерних узлов: это может привести к бесконечной рекурсии.

Хотя часть HashCode (), по крайней мере, кажется выполнимой, помечая и игнорируя уже посещенные узлы, у меня возникают некоторые проблемы с продуманным и эффективным алгоритмом для Equals ().

К моему удивлению, я не нашел никакой полезной информации об этом, но я уверен, что многие умные люди думали о хороших способах решения этих проблем ... верно?

Пример (python):

A = [ 1, 2, None ]; A[2] = A  
B = [ 1, 2, None ]; B[2] = B

A равно B, потому что оно представляет точно такой же график.

КСТАТИ. Этот вопрос не нацелен на какой-либо конкретный язык, но реализация hashCode () и equals () для описанного объекта Node в Java была бы хорошим практическим примером.

Answer 1

Вам нужно пройтись по графикам.

Вот вопрос: равны ли эти графики?

A = [1,2,None]; A[2] = A
B = [1,2,[1,2,None]]; B[2][2] = B

Если это так, вам нужен набор (Node, Node) кортежей.Используйте этот набор для перехвата циклов и возврата 'true', когда вы перехватываете цикл.

Если нет, вы можете быть немного более эффективным и использовать карту от узла к узлу.Затем, при ходьбе графиков, создать набор соответствий.(В приведенном выше случае A будет соответствовать B, A [2] будет соответствовать B [2] и т. Д.) Затем, когда вы посещаете пару узлов, вы убедитесь, что точная пара находится на карте;если это не так, график не совпадает.

Answer 2

Я бы тоже хотел узнать хороший ответ.Пока что я использую решение, основанное на посещенном наборе.

При вычислении хэша я пересекаю структуру графа и сохраняю набор посещенных узлов.Я не вхожу в один и тот же узел дважды.Когда я нажимаю на уже посещенный узел, хэш возвращает число без рекурсии.

Это работает даже для сравнения на равенство.Я сравниваю данные узла и рекурсивно вызываю детей.Когда я нажимаю на уже посещенный узел, сравнение возвращает true без рекурсии.

Answer 3

Если вы думаете об этом как о графе, конечный узел - это узел, который имеет только одно соединение, а сложный узел - как минимум с 2. Таким образом, если вы получили его таким образом, реализуйте простой алгоритм BFS, который использует хешФункция для каждого узла, который он передает, а затем отбрасывает результат.Таким образом вы гарантируете себе, что не попадете в циклы или не пройдете через какой-либо узел более одного раза.

Реализация может быть очень простой.Читайте об этом здесь .