Re: Tree Hashing / Equivalence
Al wrote:
Let's say I have a node type such as:
class Node {
std::vector<Node> Children;
std::string Value;
int ID;
};
Are there any C++ libraries that could process a tree of such nodes and
calculate a hash value of some sort? Since I already depend on Boost, I
was hoping Boost.Graph provided an algorithm for something like this,
but I haven't found anything useful. Any other pointers?
The general idea is something like:
class Node {
std::vector<Node> Children;
std::string Value;
int ID;
size_t GetHash() const;
};
// Then:
int main() {
Node root1 = ...; // Load from somewhere.
Node root2 = ...; // Load from somewhere else.
if (root1.GetHash() == root2.GetHash())
; // Trees are equivalent.
else
; // Do some expensive work.
return 0;
}
There are two issues here.
The first is to visit the nodes in a canonic order. (Note that
if the order of the children in the vector doesn't affect
equality, it can't be allowed to affect the hash code either.)
The second is to recursively integrate the hash values of the
subtrees into the hash value of the node. Basically, this can
be handled the same way you hash a string, if 1) the subtree
hash is convertable to unsigned (which should be the case), and
2) either order matters, or you visit the subtrees in a
canonical order. (I've got some templates at my site,
http://kanze.james.neuf.fr/code-en.html. Subsystem Basic,
component Hashing. The elements there are designed for use with
my pre-standard hash tables, but it shouldn't be too difficult
to adapt them to other hash tables.)
On the other hand, if you're using it for caching, you'll
probably need a much better (and more expensive) hashing
algorithm---something like MD-5 or SHA-1. And even then, you'll
have to accept the fact that two different trees can hash equal.
If the goal is to avoid some expensive work when the trees are
equivalent, I don't think that hashing will do; you need to
check for complete equivalence.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient?e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S?mard, 78210 St.-Cyr-l'?cole, France, +33 (0)1 30 23 00 34
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]