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

Subject: Re: [Boost-users] taking the subgraph of a boost graph
From: Ryan Lewis (me_at_[hidden])
Date: 2010-12-30 09:58:23

Ah, yes. This is fine. Although, I still maintain a simple function
with some type-dispatching should exist.

-rhl

On Thu, Dec 30, 2010 at 2:36 AM, Cedric Laczny <cedric.laczny_at_[hidden]> wrote:
> 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
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>