Re: [Boost-users] hash function for edge_descriptor

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-08-08 16:00:02

On Aug 8, 2005, at 3:50 PM, Wolfram Koska wrote:

>> Using source/target in the hash function works so long as the hash on
>> them is symmetric, because for undirected and bidirectional graphs you
>> can have the same edge e represented as (u, v) or (v, u), depending on
>> where you get it. Other than that restriction, you should be fine 
>> using
>> source/target: it's okay to have two edges hash to the same thing, so
>> long as your equality function compares the edge descriptors directly
>> instead of using source/target.
>
> I dug into the boost graph source for some more time, and I have to 
> admit
> that I'm far from understanding the big connections going on. I 
> wondered,
> though, what m_eproperty of the edge_desc_impl is. It is used in the
> operator== of the edge_desc_impl (I checked this after reading your 
> comment
> about the equality function). I could not figure out yet what exactly 
> this
> is. My assumption is that it has something to do with the address of 
> the
> property storage of the edge?

Yes, it's the address of the edge properties. It's used for identity 
comparison because even when there are multiple edges with the same 
source/target or if an edge has been reversed to (target, source), the 
pointer to the properties for that edge will remain the same.

>  Well, the big question for me is could I use
> this as my hash, too?

Well, yes, you could. However, by using the source and target for your 
hash function you can be sure that it will work for *all* BGL graphs, 
whereas accessing "m_property" in the edge descriptor will only work 
for some graphs.

        Doug