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

Subject: Re: [boost] [gsoc] Boost graph library - Hypergraphs
From: Om Prasad Patri (ompatri_at_[hidden])
Date: 2009-03-27 06:36:56

Hi,

On Fri, Mar 27, 2009 at 3:51 AM, Andrew Sutton <andrew.n.sutton_at_[hidden]>wrote:

> >  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.
>
Thanks for your reply. I appreciate it :)

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

We will try to implement such  a data structure which works for both. This
should work since anything which works for directed graphs should work for
undirected graphs (I read something like this in the BGL docs).

>
> > "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.
>
> The ideal solution to use both because:
for some algorithms will be easier to use through the incidence matrix (but
as you said, resizing the matrix for every operation is an expensive
operation of O(V*E) ).
For some other algorithms, it is easier to use the bipartite approach.
We should leave to the user who adds an algorithm to BGL to choose whichever
suits his needs the most. Defining hypergraph concepts again, can be done
using the best of 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.
>
> Thanks for telling me that. There are also some directed hypergraph
'visit'  algorithms in the paper you mentioned. We could implement those.

As an afterthought, and being frank, I'm not very sure as of now as to how
the exact implementation will be done using the BGL and this is appearing to
be a tough (but tremendously exciting) problem! I'm looking at the other
proposed project idea on *incidence matrices* and will post on it soon.

Finally, thanks for all the support and the warm welcome. :)
Ciao,
Regards,
Om Patri.