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

Subject: Re: [boost] [gsoc] Boost graph library - Hypergraphs
From: Larry Evans (cppljevans_at_[hidden])
Date: 2009-03-27 10:52:16

On 03/26/09 17:00, Andrew Sutton wrote:
 >> IIRC, hypergraphs are only "undirected". An edge is represented as a 
set of
 >> vertices, that is, as an element of the powerset of vertices.
 >>
 >
 > This is incorrect.
 >
 > http://www.cis.upenn.edu/~lhuang3/wpe2/papers/gallo92directed.pdf
 >

Hi Andrew and Om.

This is a little off-topic, but I was wondering about an application.
The application is representing Makefile dependencies.  It seems that
A target, Target (some vertex), would have a set of dependencies,
Dep(Target) (a subset of the vertices), which could be represented by
a hypergraph arc, E, (as defined on page 3 of gallo92directed.pdf, and
where H(E) == {Target} and T(E) = Dep(Target)).  Now if that
hypergraph arc were labelled, then the label would represent the
actions to produce the target from the dependencies.

Now one added complication is that some labels may require
"refinement". For example, boost build, when creating executables from
object files, requires (AFAICT) all object files be produced with the
same compiler.  So, maybe for those labels requiring refinement, there
could be some morphism to map each node in the hypergraph ending at
an exectuable node to a "similar" hypergraph where each label has the
same compiler or toolset in boost build terms.

Maybe this could a future project building on this hypergraph project.

-regards,
Larry