Re: [boost] Google SoC idea - Relations

Subject: Re: [boost] Google SoC idea - Relations
From: Larry Evans (cppljevans_at_[hidden])
Date: 2009-03-31 09:46:19

On 03/30/09 19:41, Michael Lopez wrote:
[snip]
> 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.
[snip]
> 
> 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).

You might also consider topological sort.  This has application in
representing the rules in a Makefile, e.g.:

   TARGET_i: PREREQUISITE_i_1 PREREQUISITE_i_2 ... PREREQUISITE_i_ni

Where the binary relation R_i representing this rule
would be the ordered pairs:

   R_i = { (TARGET_i, PREREQUISITE_i_1 )
         , (TARGET_i, PREREQUISITE_i_2 )
         ...
         , (TARGET_i, PREREQUISITE_i_ni)
         }

[snip]