Re: [boost] bgl subgraphs
From: Doug Gregor <dgregor@cs.indiana.edu> To: boost@lists.boost.org Date: Fri, 13 Oct 2006 10:35:24 -0400 Subject: Re: [boost] bgl subgraphs
On Oct 11, 2006, at 9:57 AM, Brian Makin wrote:
With respect to boost graph library.
Is anyone using subgraphs?
I've used them occasionally.
What are they being used for?
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.
Is there functionality which is needed wrt subgraphs?
New functionality for subgraphs? I'd love to see a subgraph-like adaptor that allowed one to create non-induced subgraphs, e.g., by allowing the user to add/remove any edges and vertices from the subgraph arbitrarily.
(The current subgraph is an induced subgraph: you state what vertices you're interested in, and the all of the edges among those vertices get added automatically).
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. Those two are really related. It shouldn't be difficult to support modification of the resultant graphs. Out of curiosity, what were you modeling?
Doug
__________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
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
participants (2)
-
Brian Makin -
Douglas Gregor