[boost] [gsoc] Boost graph library - Hypergraphs

Subject: [boost] [gsoc] Boost graph library - Hypergraphs
From: Om Prasad Patri (ompatri_at_[hidden])
Date: 2009-03-26 16:54:12

Hi,

      I'm a Computer Science undergrad from India applying for GSoC 2009.
This mail is regarding the hypergraph project for the BGL on the ideas list.
I have taken courses in graph theory and algorithms and have the C++
background required. I have gone through the idea and done a little
'research' on the topic. I have also read the boost graph library
documentation and found the concept to be quite interesting and somewhat
tough to implement. I have certain ideas and doubts on the hypergraph
project which I would like to discuss with a mentor.

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?

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

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.

I'm new to Boost and I hope I have made an humble beginning. :)
Hoping for some replies and suggestions,

Ciao,
Om P Patri,
Sophomore,
Computer Science and Engineering
Indian Institute of Technology, Guwahati, India

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

A hypergraph (http://en.wikipedia.org/wiki/Hypergraph) is a generalization
of graphs where an edge can connect any number of vertices (instead of
exactly two). Hypergraphs can also be directed or undirected, and have their
own algorithms (e.g., traversal and partitioning). This project minimally
involves the definition of one hypergraph data structure and a generic
traversal algorithm. This project would also involve the identification and
definition of generic concepts related to hypergraphs.

Note: This is a non-trivial project that requires substantial knowledge of
graph theory, algorithms, and generic programming.