Generic fingerprint ie hash value for compex data structure?

[Tim Richardson]

I am doing a depth-first generative search with a recursive algorithm.
My problem can return to a node already visited. I need to know this,
otherwise I could end up in loops. I think this is not unlike a chess
program, which I think solves the problem by a "hash table", which
quickly lets the search algorithm realise it is somewhere it has
already been.

I can also make a unique value for each node, and add this to a
special hash. I wonder if there is a good generic way to do this?
Using Digest::MD5 or something like it perhaps?

For sure I am reinventing the wheel, but this is a hobby program as I
try to improve my Perl.

Tim

 

[ctcgag]

I am doing a depth-first generative search with a recursive algorithm.
My problem can return to a node already visited. I need to know this,
otherwise I could end up in loops. I think this is not unlike a chess
program, which I think solves the problem by a "hash table", which
quickly lets the search algorithm realise it is somewhere it has
already been.

Well, I would think the best way would be to have some kind of marker in
the nodes themselves, indicating whether or not they have been visited.

I can also make a unique value for each node, and add this to a
special hash. I wonder if there is a good generic way to do this?
Using Digest::MD5 or something like it perhaps?

What would you be doing the digest on? whatever you would be doing the
digest on, why not just use the undigested thing directly?

Is this a multi-threaded program where something else may be changing the
structures while the depth-first search is running?

If your nodes are perl objects (i.e. blessed references), how about just
using the stringified references?

Xho

 

[Tim Richardson]

Well, I would think the best way would be to have some kind of marker in
the nodes themselves, indicating whether or not they have been visited.

Hmm. I am making each new state recursively from existing states, but
my code has no graph knowledge, ie it does not know how it got to
where it is. I could do this, it is fairly easy and I think in many
cases this would be the most efficient way to go.

What would you be doing the digest on?

The "serialised" value of the object instance (from Data:umper)

digest on, why not just use the undigested thing directly?

Yes, you're right, on first thought I was worried about how perl copes
with long hash keys but it's going to be a very special case where the
overhead of Digest is lower than whatever problems perl may have with
long keys. In fact I was being very silly; I know nothing about Perl
internals but this can not be a problem.

Is this a multi-threaded program where something else may be changing the
structures while the depth-first search is running? no


If your nodes are perl objects (i.e. blessed references), how about just
using the stringified references?

because the memory allocator will not be smart enough to know that my
new state representation is the same as existing ones, it is an object
equivalence problem (cf the allegedly missing === operator).

Xho

I ended up making a special low cost state string; I hope I got it
right. Perhaps I will test it by using Data:umper.

 

[ctcgag]

The "serialised" value of the object instance (from Data:umper)

From what you say later, I would be worried about this. I think that
Hashes which are formally identical, but which have different histories,
can possibly serialize differently. So if you do this, I'd set
$Data:umper::Sortkeys.

because the memory allocator will not be smart enough to know that my
new state representation is the same as existing ones, it is an object
equivalence problem (cf the allegedly missing === operator).

Hmmm. I think this is somewhat unusual. In the graph programs I've worked
on, it was always legal for two different nodes to have identical external
labelling and yet still be different entities. If this is not the case
for you, then I would think the labelling that constrains you from having
duplicates would also serve as the key for holding in a marker hash.

Xho