Re: [Boost-users] hash function for edge_descriptor

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-08-08 14:14:41

On Aug 8, 2005, at 12:14 PM, Wolfram Koska wrote:
> I was trying to create hash_maps with vertex_descriptors and
> edge_descriptors.
>
> The first one was easy with vertex_descriptors being just void*'s, and 
> there
> is even an example in the boost detail namespace (although it's not
> activated using gcc):
>
> template <>
> struct hash< void* >
> {
>   std::size_t
>   operator()(void* v) const { return (std::size_t)v; }
> }
>
> But the edge_descriptors give me some serious headache. How could I 
> create a
> hash function for them? Is using the source and target a good idea in 
> graphs
> where there could easily be more than one edge between two vertices? 
> Or is
> there a great method I cannot come up with?

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.

        Doug