Re: [Boost-users] taking the subgraph of a boost graph

Subject: Re: [Boost-users] taking the subgraph of a boost graph
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2010-12-30 02:36:35

On Thursday, 30. December 2010 00:52:04 Ryan Lewis wrote:
> an interface called subgraph(Graph g, Graph s, vertexiterator begin,
> vertexiterator end), doing the obvious thing.
> 

Referring and agreeing to the answer from Jeremiah Willcock about 
filtered_graph, this might actually do this obvious thing. After all, you have 
only vaguely stated your requirements and still not included an example. You 
could create your subgraph like so: "filtered_graph< adjacency_list< ... >, 
EdgePredicate, VertexPredicate > subgraph( origG, edge_pred, vertex_pred)" by 
simply defining appropriate predicates. It might even be enough to specify a 
vertex-predicate in order to select the vertices you otherwise specify by the 
VertexIterator-range, like so:
filtered_graph< adjacency_list< ... >, keep_all, VertexPredicate > subgraph( 
origG, keep_all(), vertex_pred)
Also, you would not have to take care of the edges, because, unless a separate 
edge-predicate is provided, only those edges will be visible where both of the 
incident vertices are visible.

The filtered_graph interface does only introduce little overhead and is also 
fast for simple predicates. Of course, if the predicate is complex and perhaps 
needs a lot of interaction with the internals of the graph, it will be slow. 
But this is not due to an inefficiency of the interface but the design of the 
predicate. I experienced dramatic differences, e.g. when retrieving properties 
from the graph each time instead of providing a property_map directly.

> I don't see why that needs to be hard.
> 

If the functionality of filtered_graph does exactly that for you, you are 
right.
Please let me know if this actually does not suit your needs.

> -rhl
> 

Best,

Cedric
> On Wed, Dec 29, 2010 at 6:23 PM, Jeremiah Willcock <jewillco_at_[hidden]> 
wrote:
> > On Wed, 29 Dec 2010, Ryan Lewis wrote:
> >> I do mean adjacency list, and I agree this should be documented a lot
> >> better.
> >> 
> >> I'm not sure how the internals of adjacency_list<..> work, but I
> >> fundamentally don't understand why a subgraph can't be a method built
> >> on top of a simple adjacency list, it may be less efficient than
> >> something typed as a 'subgraph' capable graph, but I don't see why a
> >> graph shouldn't have one of it's fundamental operations work on it.
> > 
> > What would a built-in subgraph capability do?  If you want it to produce
> > an adjacency_list without copying the original graph, it would need to
> > wrap all of the iteration functions (like filtered_graph does), leading
> > to a slowdown for graphs whose subgraphs aren't used.
> > 
> >> I will look into forcing our graph types to be subgraph < Graph >
> >> types. What is the right way to 'raise' this question to an
> >> appropriate developer?
> > 
> > Boost-users works for that.
> > 
> > -- Jeremiah Willcock
> > _______________________________________________
> > Boost-users mailing list
> > Boost-users_at_[hidden]
> > http://lists.boost.org/mailman/listinfo.cgi/boost-users
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users