How to hash and check equality of objects with circular links

Question

I have a cyclic graphical structure that is represented by Node objects. A Node is either a scalar value (leaf) or a list of n> = 1 nodes (inner node).

Due to possible circular references, I cannot just use the recursive function HashCode (), which combines the HashCode () of all the child nodes: it will end in infinite recursion.

Although the HashCode () part seems at least feasible by placing and ignoring already visited nodes, I am having some problems to think of a working and efficient algorithm for Equals ().

To my surprise, I did not find any useful information about this, but I am sure that many smart people thought of good ways to solve these problems ... right?

Example (python):

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

A is equal to B because it represents exactly the same graph.

BTW. This question is not aimed at any particular language, but the implementation of hashCode () and equals () for the described Node object in Java will be a good practical example.

Answer 1

If you think of it as a graph, a node sheet is a node that has only one connection, and a complex node is one with at least 2. So you get it that way, implement a simple BFS algorithm uses a hash function for each node which it passes and then returns the result. This way, you will make sure that you don't go into loops or go through any node more than once.

Implementation can be very complex. Read about it here .

Answer 2

You need to go through the charts.

The question here is: are these graphs equal?

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

If so, you will need a set of (Node, Node) tuples. Use this set to catch loops and return "true" when you catch a loop.

If not, you can be a little more efficient and use a map from Node to Node. Then, while walking through the graphs, create a set of matches. (In the above case, A will correspond to B, A [2] will correspond to B [2], & c.) Then, when you visit the Node pair, you will make sure that the exact pair is on the map; if it is not a schedule, it does not fit.

Answer 3

I would also like to get a good answer. For now, I am using a solution based on the visited set.

When computing the hash, I cross the graph structure and I save the set of visited nodes. I do not enter the same node twice. When I get to an already visited node, the hash returns a number without recursion.

This work is even to compare equality. I am comparing node data and recursively referring to children. When I hit the already visited node, the comparison returns true without recursion.