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 designing a scene graph system, where it is required to compare two trees. The trees are populated with individual objects, each with varied number of children; and they have a root.
Eg: Parent: Scene, Children: Bullet1, Bullet 2, Player

What is a good way to compare two such tree? I'm using C++ for the code.
Also, this question is an off-shoot from this question

share|improve this question
    
On top of my head, could one just compare the 2 adjacency matrices? –  Emmad Kareem Jun 27 '12 at 16:14
    
Is your scene graph a graph or a tree? What are you comparing? –  Danny Varod Jun 27 '12 at 16:25
    
@EmmadKareem: Well, how do you suggest the adjacency matrices be populated? –  vsrao Jun 27 '12 at 16:25
    
@DannyVarod: It is a tree ( I use 'graph' here to suggest the scene graph ). I'm comparing two such graphs, drawn from different scenes to find where they exactly differ. –  vsrao Jun 27 '12 at 16:26
    
I know what scene graphs are. Most of the ones I have scene were trees. My question is what are you comparing e.g. items, positions, changes within the objects themselves (moved parts, changed colors). If you are comparing items, are you comparing them by name, by model, ... –  Danny Varod Jun 27 '12 at 16:42
show 5 more comments

2 Answers 2

up vote 2 down vote accepted

Create a stack of node pairs for in-depth comparison.

Define an identifier you can use for quick comparison e.g. ID/name/model-path.

  1. Shallow compare root nodes, if they match add them to stack.

  2. For each pair in stack:

2.1. Sort children according to chosen identifier

2.2. Shallow compare children and add matches to stack.

Decide whether algorithm should be terminated on first mismatch or not (depending on required results).

If your nodes are themselves sub-trees (of smaller parts), you can apply the same algorithm to them.

share|improve this answer
    
Thanks, but I've already implemented it that way. I was actually looking for alternative approaches to this. –  vsrao Jun 28 '12 at 6:41
    
You should write what you have already tried in the question, not wait for answers. –  Danny Varod Jun 28 '12 at 7:43
add comment

Depends rather what you mean by "compare", but if you can (effectively) serialize your trees (or at least the properties of them you care about) to strings then the "Levenshtein distance" (or some other related "edit distance" or "string metric") between a pair of strings ought to tell you something useful about the similarities between them.

You can also have some fun with compression-based similarity metrics: if strings A and B compress to size a and b, but compressing the file C created by concatenating A and B compresses to size c, then c/(a+b) tells you something about how much duplicate information there was in the two files: the nearer to 1.0, the less benefit there was from compressing the files together and so the less similar they are (subject to caveats re file size and the maximum window your compressor works over anyway). Think this sort of approach is used by bioinformatics people but with it's information theoretic roots it ought to be more generally applicable.

share|improve this answer
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.