graph - How to hash and check for equality of objects with circular references

Question

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

Because of the possible circular references, I cannot simply use a recursive HashCode() function, that combines the HashCode() of all child nodes: It would end up in an infinite recursion.

While the HashCode() part seems at least to be doable by flagging and ignoring already visited nodes, I'm having some troubles to think of a working and efficient algorithm for Equals().

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

Example (python):

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

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

BTW. This question is not targeted to any specific language, but implementing hashCode() and equals() for the described Node object in Java would be a good practical example.

Answer 1

If you think about this as graph, a leaf node is a node that has only one connection and a complex node is one with at least 2. So one you got it that way, implement a simple BFS algorithm witch applies the hash function to each node it passes and then drops the result. This way you ensure yourself that you wont fall in cicles or go through any node more than once.

The implementation could be very straihgtforward. Read about it here.

Answer 2

你需要走图表。

这里有一个问题：这些图是否相等？

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

如果是这样，您需要一组 (Node, Node) 元组。使用此集合捕获循环，并在捕获循环时返回“真”。

如果没有，您可以更高效一些，并使用从节点到节点的映射。然后，在遍历图表时，建立一组对应关系。（在上面的例子中，A 对应于 B，A[2] 对应于 B[2]，等等。）然后，当您访问一个节点对时，请确保准确的对在映射中；如果不是，则图表不匹配。

Answer 3

我也想知道一个好的答案。到目前为止，我使用基于访问集的解决方案。

在计算哈希时，我遍历图结构并保留一组访问节点。我不会两次进入同一个节点。当我点击一个已经访问过的节点时，哈希返回一个没有递归的数字。

这甚至适用于平等比较。我比较节点数据并递归调用子节点。当我点击一个已经访问过的节点时，比较返回 true 而不递归。