Calculating hashes for nodes in an acyclic graph is well known using a Merkle tree.
With some simplifying assumptions, a simple algorithm will also calculate hashes for nodes in a cyclic graph... but it runs in quadratic time, making it impractical to use except for very small graphs.
Is it possible to do better?
Graph characteristics
We have a directed graph, which can be cyclic, where each node contains a value.
Nodes are not labeled, and different nodes can contain the same value.
The outgoing edges of a node are ordered (or labeled 1, 2, 3, ... N, where N is the number of outgoing edges from the node).
(That is, it's a k-ary tree, if such a term can be used for a cyclic structure).
Equal nodes
We define an equivalence relation this way: two nodes are equal if they contain the same value, they have the same number of outgoing edges, and, recursively, the subgraphs reachable from the two nodes following the outgoing edges in order are equal.
As I explain further below, it's also OK but not a requirement for nodes to be equal if following their edges produces the same sequence of values.
Note that this isn't an isomorphism problem for labeled graphs. We're not trying to find out if two graphs are equal. (Even with a cheap O(1) test available to see if two nodes are equal, worst case we'd still need to check many combinations of nodes between the two graphs to find out if the graphs are equal).
And, since edges are ordered, we don't need to perform an exponential search of alternatives to find out if two nodes are equal. We can tell if two nodes are equal by inspection, performing a breadth-first search from the two nodes in edge order.
Equal hashes
For nodes in the graph, we wish to calculate a cryptographic hash such as SHA-256 for each node.
A minimal requirement is that given a hash for a node from a trusted source, we can query an untrusted server with the hash, the server replies with the node and subgraph reachable from the node, and we can verify that the data we've received matches the hash. (That's not very hard to do).
It would also be very convenient if equal nodes produce equal hashes, which the Merkle tree does for acyclic graphs, and the simple quadratic algorithm described below does for cyclic graphs.
However, the quadratic algorithm is too slow to be practical.
Thus my question as to whether it's possible to do better than the quadratic algorithm.
If not, we can give up on having equal nodes produce equal hashes.
But it would also be nice to know if it is impossible before giving up!
Value unfolding equality option
It's OK (but not a requirement) if nodes end up being considered equal (have the same hash) if following the edges from the nodes produce the same values.
For example,
and
produce (if for example we start with the leftmost node) the same (infinite) unfolding of values: A, B, A, B, A, B...
These nodes are considered different by the simple quadratic algorithm I describe below, and they don't have to be considered equal, but if it would help a heuristic is free to give them the same hash.
https://www.cs.indiana.edu/~dyb/pubs/equal.pdf describes some algorithms for detecting equality by the unfolding of values... and I don't know if these algorithms are more or less efficient than testing for structural equality or if the algorithms could be modified to generate a hash... but maybe something like that would be an option.
Annotating the graph
We're also free to add information to the graph (to annotate the graph with additional information), if that would help in some way.
We could, for example, take the hash for the node, add additional useful information about the graph, and hash that.
Acyclic algorithm
For an acyclic graph, we can use a linear algorithm such as the Merkle tree: visit the nodes in post order. Calculate the hash based on the node's value, and in edge order, the previously calculated hashes of the node's successors.
(For example, in Git, the hash of a commit is based on the contents of the commit and the hashes of its parent commits).
Cyclic quadratic algorithm
For a cyclic graph, here's the simple quadratic algorithm. For each node in the graph:
Number the nodes in the subgraph reachable from the node, which I can do in a specific order (such as breadth-first, ignoring nodes already numbered) because the outgoing edges of a node are ordered.
Describe the subgraph reachable from the node by listing the nodes in the subgraph in order by the assigned number, and for each node in the list include the node's value and for each outgoing edge for the node (in label order), include the number assigned to the tail node of the edge.
Hash the description to produce the hash for the node.
(This algorithm is quadratic because for each node, it visits all the nodes reachable from that node).
For example, for a tree with nodes containing values A, B, C, and D:
We describe A by assigning 0, 1, 2, 3 to the nodes containing A, B, C, D, and enumerate the values and edges this way:
0: A [1 2 3]
1: B []
2: C [0]
3: D []
Note in particular the outgoing edges from the node containing "A" are ordered (B, C, D), which makes this a unique description of the subgraph (which it wouldn't be if edges were unordered).
And similarly, to calculate the description for C:
0: C [1]
1: A [2 0 3]
2: B []
3: D []
As another example:
both nodes get the same hash, since the algorithm produces the same description when run for each node.
To reduce the number of such cyclic hash calculations we need to do, we can compute the strongly connected components of the graph, and then we only need to do the cyclic calculation for the nodes within each component.
However, within each strongly connected component, the simple algorithm is still quadratic.
Is it possible to do better?
Typical graph structure
In my graphs, most nodes only have one direct predecessor, and usually only have a few direct successors. A small number of nodes ("central" nodes) have many direct predecessors and many direct successors.
(I'm modeling code modules, where modules, the "central" nodes, contain references to code and code contains references to modules).
It is these central nodes which are involved in large cycles that makes the quadratic algorithm impractical. Remove the central nodes, and the graph becomes acyclic, or the remaining cycles are small and can be handled by the quadratic algorithm.
Given this structure, is there an algorithm which, not worrying about worst case performance, would usually be better?
Thanks!
