[boost] [gsoc] Graph : BGL - Incidence Matrices Project

Subject: [boost] [gsoc] Graph : BGL - Incidence Matrices Project
From: Om Prasad Patri (ompatri_at_[hidden])
Date: 2009-03-27 07:18:06

Hi,

     I'm a student applying for GSoC to Boost Graph Library. This is my
second post here and this mail is regarding the incidence matrices project
for the BGL(earlier one was for hypergraphs and these are the two ideas
which interested me the most in the 'ideas list'.) I have gone through the
idea and the BGL documentation and the idea appeals to me as pretty
interesting, useful and implementable. Also, I do not have any other
commitments during the summer. I am giving a rough idea of what I understood
we have to do in this project. Please correct me if I am wrong anywhere and
clarify my doubts.

Most of the concepts which I'm discussing here are obtained from wikipedia (
http://en.wikipedia.org/wiki/Incidence_matrix) . As far as I understand, we
have to implement generic incidence matrices for:

1. oriented incidence matrices for undirected graphs. The matrix will
contain zeroes and ones. 1 if the corresponding vertex and edge are
incident, 0 otherwise. One edge has two incident vertices.

2. incidence matrices for directed graphs. matrix will contain 1, 0 and -1.
-1 for edge coming out of vertex, +1 for edge going into vertex (or maybe
the opposite convention) and 0 for edge and vertex not incident.

3. unoriented incidence matrices for undirected graphs (similar to above
case).

4. Signed graphs. A method for filling up the incidence matrix is given here
: http://en.wikipedia.org/wiki/Signed_graph#Incidence_matrix

5. Bidirected graphs. A convention can be made but I'm not sure yet. It
would be better if you could throw some light on this topic, i.e  how to get
an incidence matrix of a bidirected graph.

6. Hypergraphs. Incidence matrices are a good way of representing
hypergraphs and this adpatation can help a lot in implementing hypergraphs.
The incidence matrix can be obtained as given here:
http://en.wikipedia.org/wiki/Hypergraph#Incidence_matrix

Apart from these, we can also think of using incidence matrices to get the
Kirchoff Matrix and adjacency matrix (I am not sure if adjacency matrix
already exists in BGL) if it is possible and time permits. Please tell me if
I am going in the right direction and if there is anything I left out or
included unnecessarily. Any other information regarding the project will be
highly appreciated.

Thanks for your reply in advance,
Ciao,
Om P Patri,
Sophomore,
Computer Science and Engineering
Indian Institute of Technology, Guwahati, India.
-----------------------------------------------------------------------------------------------------------
Incidence Matrices
 <https://svn.boost.org/trac/boost/wiki/soc2009#IncidenceMatrices>

An incidence matrix (http://en.wikipedia.org/wiki/Incidence_matrix) is a
graph data structure that relates vertices to the set of edges that connect
them. This project would entail the implementation of a generic incidence
matrix data structure that fits into the BGL generic graph interface. This
project can include the development and definition of concepts related to
graphs represented by incidence matrices (e.g., signed and bidirected
graphs). Incidence matrices can also be adapted to implement hypergraphs.