I work a lot with directed graphs resulting from heap dumps of Java programs. One thing that characterizes them is that they contain lots of repeating patterns. I would like to find a way of compressing such patterns whilst still retaining the essential structure of the graph. For instance consider the following "molecules":
| | A1 A5 / \ / \ B2 C4 B6 C8 \ / \ / D3 D7
the letter represents the type of the object and the number represents its unique id (or dfnum). Clearly the second molecule is a repeat of the first just with different ids. From a heap analysis point of view, the actual ids are unimportant so you could replace the molecule at A5 with something that said effectively "another copy of A1". On decompression (for input to heap analysers for instance) you could just assign arbitrary unique ids.
I could spot such patterns by maintaining a hash of the type of the objects during the dfs of the graph. So the hash for A1 would contain (for instance) "A^B^C^D" and this would match that for A5.
The problem I have is with molecules that point to some external molecule. By external I mean something that has been visited earlier in the dfs. For instance (sorry about the ugly ascii graphics):
| | A1 A5 / \ / \ B2 C4 B6 C7 \ \ / / \ \ / / \ | | / \ | | / \| |/ D3
for this situation when I come to descend from A5 I find that D3 has already been visited. So I would like the hash code for A5 to represent the unique value for D3 rather than just the type. I.e. something like "A^B^C^D3". So on compression/decompression we are differentiating A5 as being a copy of A1 rather than some other A whose B and C point to some other D.
My question is whether there are any tricks to do such a calculation, i.e. how to tell that D is "outside" our molecule whose root is A? This also has to be done in an efficient manner, preferably with one or two dfs's. (Heapdumps contain tens of millions of objects). You don't know in advance that A is a candidate so it probably needs to be an algorithm that does it during the dfs. Maybe something dominator tree related?
Hope that makes sense!
Edit: updated diagrams to clarify the fact that A1 and A5 themselves have parents and are just arbitrary nodes discovered during a DFS walk of the entire graph.
Clarification: for my purposes it's not important that the match is 100% guaranteed. By using hash codes as above I am happy to take the very small chance that there will be a hash collision and the algorithm will mistakenly classify a molecule incorrectly. Because such collisons will be rare they are unlikely to much affect the overall picture.