On Oct 13, 2006, at 6:07 PM, Brian Makin wrote:
From: Doug Gregor <dgregor@cs.indiana.edu> 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