I'm trying to compare two graphs using hash value ( i.e, at the time of comparison, try to avoid traversing the graph ) Is there a way to make a function such that the hash values compared can also lead to determining at which height the graphs differ? The comparisons between two graphs are to be made by comparing children at a certain level. One way to compare the graphs is have a final hash value for the root node and compare them, but that wouldn't directly reflect at which level the graphs differ, since their immediate children might be the same ( or any other case ).
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
A cobbled together solution:
You could probably cobble something together where each level of the graph affected a different portion of the hash value. What you'd essentially be doing here is creating a separate hash value for each level and appending them in sequence.
e.g. For a 32-bit hash and graphs with 8 levels, each level could hash to 4 bits: 1st level => bits 1-4; 2nd level => bits 5-8; etc.
If the number of levels in your graphs isn't fixed/known, then you'll have to wrap this around. This wouldn't tell you exactly which level was different, but it would narrow down your options.
e.g. For a 32-bit hash and graphs with an unknown number of levels, each level could still hash to 4 bits: bits 1-4 would be affected by the 1st, 9th, 17th, ... layers; bits 5-8 would be affected by the 2nd, 10th, 18th, ... layers; and so on.
Why it's probably a bad idea:
Some other possible approaches:
No there is no way to do what you are asking, the purpose of a hash value is to take something and make it something else with no apparent relation to what it was. This means hash values are only useful to tell you if to things are the same, not what is different between them.
It is theoretically possible to reverse engineer the source of a hash, and you could use the source to find differences, but this is both computationally expensive and entirely pointless when you have the source available with a much faster way to generate it.