Re: [boost] bgl subgraphs

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-10-14 08:46:46

On Oct 13, 2006, at 6:07 PM, Brian Makin wrote:
>
>>> From: Doug Gregor <dgregor_at_[hidden]>
>> The last time I used them, it was to split a graph
>> up into subgraphs,
>> each of which was a strongly-connected component of
>> the full graph.
>
> This could be covered by multi-level graphs.  This is
> where ever vertex in the graph is mapped to a smaller
> set of vertices in a secondary graph.  Like an induced
> subgraph in BGL that includes ever vertex.
>
> I certainly want to support multi-level graphs, as
> described above.
> Concidering allowing clustering.  ie: collapse a group
> of vertices into a single vertex with a subgraph below
> it.

This, too, would be extremely useful... but for a completely  
different reason :)
We've had this "hierarchical graph" TODO item on our list for  
(literally) years... we want to be able to collapse a set of vertices  
into one vertex, and do so in a hierarchical fashion. This particular  
functionality is interesting to us because we'd like to use it in  
visualization.

> Those two are really related.  It shouldn't be
> difficult to support modification of the resultant
> graphs.
>
> Out of curiosity, what were you modeling?

With the subgraphs, I was determining the order of replacement of  
variables when simplifying symbolic expressions, e.g., 2*a + x*b -  
a*x, where the variables have symbolic upper and lower bounds, e.g.,  
x is in [a, 2*b]. Each vertex is a variable, and has an edge to any  
variable that appears in its lower or upper bounds. SCCs show where  
we have circular dependencies (so we are careful within SCCs).  
Topologically sorting the SCCs gives a good variable replacement  
strategy.

        Cheers,
        Doug