Subject: Re: [boost] [gsoc] Boost graph library - Hypergraphs
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-03-26 18:21:31
> I have certain ideas and doubts on the hypergraph
> project which I would like to discuss with a mentor.
I posted the project idea, so I would be more than happy to address your
> First of all, what about the assumptions. Can we assume the hypergraph to
> directed ro undirected or do we have to try to find a generic solution for
My guess is that whatever data structure you choose to implement hypergraphs
will actually support both directed and undirected graphs. For example, the
BGL adjacency_list supports both directed and undirected graphs (via
parameterization over a tag class, actually). I think an ideal solution
could use the same data structure to do both. I've read something, somewhere
on how an incidence matrix can be used to represent directed hypergraphs
> "This project minimally involves the definition of one hypergraph data
> structure and a generic traversal algorithm". Now, for the data structure,
> we can use an incidence matrix with vertices as rows and edges as columns.
> This incidence matrix structure will have to be implemented. As an
> alternative, we can have a 'bipartite' kind of data structure with two
> groups of vertices V and E, where V represents the group of vertices and E
> the group of edges. Identification and definition of other concepts related
> to hypergraphs, like hyperedges etc. can then be done accordingly.
You could choose to implement a hypergraph using either approach - or both
:) Just remember that resizing matrices can be a very expensive operation,
so the bipartite approach may be more flexible. Defining hypergraph
*concepts* and a generic hypergraph interface would best be done using both.
> As for the traversal algorithm, is it to be decided now (before applying)
> which algorithm is to be used ? I searched for and found a few on the
> internet like
> http://www.icsi.berkeley.edu/cgi-bin/pubs/publication.pl?ID=000778 . I
> be happy if you could provide me links of some traversal algorithms I
> look at and which would help me understand the concept better.
That's probably the best place to start. As far writing a proposal goes,
citing this and trying to dig up a couple of other algorithms would be
sufficient. I don't know of any off the top of my head, and a quick search
just turned up a couple of variations on this algorithm.
> I'm new to Boost and I hope I have made an humble beginning. :)
> Hoping for some replies and suggestions,
Welcome :) Let us know if you have any questions.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk