Re: [boost]: Hypergraph

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-06-25 23:15:35

Hi Ruth,

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

Great!

Ruth.B> Here's my thoughts, what do all of you think?
Ruth.B> 
Ruth.B> - sets and multisets instead of pairs to store edges 

The adjacency_list edges appear as pairs, but underneath what is stored is
a list of target vertices for each vertex. The "stored_edge",
"stored_edge_property", and "stored_edge_iter" (in
detail/adjacency_list.hpp), are the actual objects stored in the EdgeList
containers in various situations.

I'm not sure how moving to sets and multisets would affect the internal
interfaces of adjacency_list... they may not fit well into the current
model. However it is worth looking into. If hyperedges can be incorporated
with a moderate amount of change, great! If not, then having a separate
hypergraph class would be OK.

Ruth.B> - overload add_edge() to accept either one of these containers

Sounds good. Just make sure these containers don't get copied unecessarily
(which might get expensive). And perhaps to allow more flexibility also
have a version of add_edge() that takes a begin/end vertex iterator pair.

Ruth.B> - edges could still be stored in any of the current EdgeList containers
Ruth.B> - add another parameter to the adjacency_list constructor to indicate
Ruth.B> binary graph or hypergraph?

Sounds good!

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate, IU B'ton          email: jsiek_at_[hidden]
 Summer Manager, AT&T Research      phone: [phone]
----------------------------------------------------------------------