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

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 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users