[boost] Google SoC idea - Relations

Subject: [boost] Google SoC idea - Relations
From: Michael Lopez (mlopez7_at_[hidden])
Date: 2009-03-30 20:41:05

Hello everyone.

I am an undergraduate student of Kent State University and I am drafting a
proposal for GSoC to try and extend the BGL. I don't exactly know to whom I
should direct this post, but I wanted to informally pass this idea to the
boost community.

I would like to add a binary relation data type to the BGL. Binary relations
are quite similar to graphs and can be visualized using directed graphs. I
would even like to use the graph interface for relations, since one of its
key features should be that a user can use relations just as she would use
graphs.

Sometimes, a single criterion is all that is needed to define a relation (an
edge) between two objects (vertices). This relation can be a '<' operator or
'>=' operator or something more complex, for instance an equivalence
relation between some geometric shapes. It doesn't really matter. The beauty
in this datatype is that the relation, in the form of a function, will be
user defined. I would like to provide several common relations such as less
than and modular equivalence, but the relation is completely up to the user
and packed snugly into a familiar interface that is quite capable of
handling relations.

Speaking of snug packing, the other key feature that differentiates
relations from graphs is data storage. The relation data type will store a
set of objects rather than vertices and edges. Since the relation is defined
as a function, checking to see whether there is a relation (an edge) between
two objects (vertices) simply requires a function call with those two
objects as parameters. This bypasses the look up of an edge in favor of a
computation.

The computation, however, does not have to be limited to a boolean value. In
the case of weighted complete graphs, the relation can be utilized as a
normal functions, such as distances between cities. Better yet, the
Boost.optional can be used to return either a type or false if a relation
does not exist.

Time permitting, I would also like to examine the possibility of providing
support for properties like transitivity and symmetry and also provide a
data type that would enable closures, such as transitivity (connectivity).

who am I: Like I mentioned above, I am a KSU student majoring in both
mathematics and computer science. I've been programming in c++ since early
highschool. good heavens, that would be about 8 years. I am fascinated by
generic and template programming and enjoy applications of math in
programming, particularly visulaization and applications of discrete math.

thank you for reading,

michael lopez