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
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
> Those two are really related. It shouldn't be
> difficult to support modification of the resultant
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk