Re: [boost] [gsoc] Boost graph library - Hypergraphs

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
questions.

> First of all, what about the assumptions. Can we assume the hypergraph to
> be
> directed ro undirected or do we have to try to find a generic solution for
> both?

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
(maybe wikipedia).

> "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
> would
> be happy if you could provide me links of some traversal algorithms I
> should
> 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.

Andrew Sutton
andrew.n.sutton_at_[hidden]