Re: [boost]: Hypergraph

From: Ruth Brown (Ruth.Brown_at_[hidden])
Date: 2001-06-22 16:06:50

Hi all,
Thanks for the ideas for HyperGraphs.  A generic solution is definitely
the best for my purposes.  Jeremy, my faculty mentor has asked me to 
extend BGL to accommodate hypergraphs, with the intent of submitting my
work to the list if I get far enough.  Your ideas are a good starting 
place, but I need more help.

Here's my thoughts, what do all of you think?

- sets and multisets instead of pairs to store edges 
- overload add_edge() to accept either one of these containers
- edges could still be stored in any of the current EdgeList containers
- add another parameter to the adjacency_list constructor to indicate
binary graph or hypergraph?

Joel, the algorithms I need to support are in an already-existing 
system that needs to be upgraded with templated classes.  They will 
need to be wrapped to interact with BGL.  See:
http://zhivago.elon.edu/~berryj/LINK.html

Thanks!
Ruth

On Thu, 21 Jun 2001 17:36:14 -0500 (EST) Jeremy Siek <jsiek_at_[hidden]> 
wrote:
> 
> There is not yet a BGL interface (or data-structure) for representing
> hypergraphs, however I have imagined how it might look. Instead of
> 
> source(e, g)
> target(e, g)
> 
> you would have
> 
> incident_vertices(e, g)
> 
> which returns a pair of iterators that can be used to loop through the
> vertices. The type of these iterators would be named something like
> 
> incident_vertex_iterator<Graph>::type
> 
> I haven't thought about efficient data-structure representations
> for hypergraphs. If anyone knows how to do this, I'd be glad to
> help with adding this to the BGL.

----------------------------------------
Ruth Brown
CS undergrad, Elon University
rbrown_at_[hidden]
336-278-6238