Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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 ).

share|improve this question
    
Are you using SVG, JSON? If this is a web based graph it is easiest to make comparison on the data, separate from the implementation. –  ClintNash Jun 27 '12 at 15:25
    
You're going to have to traverse the graphs to create that hash value. Are you planning on caching the hash value? –  Baqueta Jun 27 '12 at 15:29
    
No, I'm using C++. I'm writing code to compare scene graphs. The scene consists of objects holding the hash value too. So, I'd say they're cached. –  vsrao Jun 27 '12 at 15:33
    
I'm guessing that what you're after is an efficient way to compare two graphs: if so then you might be better off asking a question about that rather than the specifics of one potential approach to the problem... –  Baqueta Jun 27 '12 at 15:56
    
@Baqueta: Yes, that seems a better approach. –  vsrao Jun 27 '12 at 15:58
add comment

2 Answers

up vote 1 down vote accepted

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:

  • The hash function I've described is a rubbish hashing function. I expect it would produce a lot of clashes, and poor distribution.
  • Using hash values to detect differences is only quicker if there is a difference. hash(A) != hash(B) tells you that A and B are different, but hash(A) == hash(B) does not tell you that they are the same. In the second case, you'll have to do a full comparison to be sure.

Some other possible approaches:

  • Take another approach. If the comparisons are too slow, run a profiler and see if there are other ways you can speed up the comparison: try using a different data structure for storing your graphs, etc.
  • Try a compromise:
    • Create a separate hash value for each level as well as one for the entire graph. Comparing hash values for each level is still going to be loads quicker than comparing every single node.
    • Instead of using a hash value to speed up your comparisons, create two objects with metadata about the graphs (e.g. # of levels, # of nodes on each level, etc.) and compare those.
share|improve this answer
add comment

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.

share|improve this answer
    
Just because it's a bad idea, it isn't necessarily impossible! ;) –  Baqueta Jun 27 '12 at 15:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.