Hello there, 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? I hope that somebody can help me out here :) Thanks, Wolfram Koska
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
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? Well, the big question for me is could I use this as my hash, too? Thanks again, Wolfram
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
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.
Thank you very much for your help, Doug! I have only one last question: for which graphs will this not work? It seems to work for me, and I will most probably not change the graph I am using (a directed adjacency_list). Will it not work for graphs with edges without properties? I can't quite believe this... maybe it will not work for adjacency_matrix ? Again, thanks very much! Regards, Wolfram Koska
On Aug 9, 2005, at 3:18 PM, Wolfram Koska wrote:
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.
Thank you very much for your help, Doug! I have only one last question: for which graphs will this not work? It seems to work for me, and I will most probably not change the graph I am using (a directed adjacency_list). Will it not work for graphs with edges without properties? I can't quite believe this... maybe it will not work for adjacency_matrix ?
The BGL algorithms can work on any graph that matches the BGL Concepts. So, for instance, this probably wouldn't work on a LEDA graph, edge_list_graph, or vector_as_graph. Doug
participants (3)
-
Doug Gregor -
Douglas Gregor -
Wolfram Koska