Re: [Boost-users] Subgraph at distance n

Subject: Re: [Boost-users] Subgraph at distance n
From: Nick Edmonds (nicholas.g.edmonds_at_[hidden])
Date: 2015-07-14 14:53:36

On Sat, May 2, 2015 at 2:47 AM, Rossano Schifanella <schifane_at_[hidden]>
wrote:

> Hi all,
>
> which is the easiest way to extract from a graph G and a generic node
> source a subgraph with all the vertices/edges at distance at most n from
> source?
>
> Thanks a lot for your help.
> Best,
> Rossano
>
>
I'm assuming that you've already figured this out given that it's been
quite a while, but it's an easy question to answer so I figured I'd leave
the answer here for posterity.  In the sequential case, customize a BFS
visitor to throw an exception on the first path encountered longer than n.
In the parallel case you could either add an all_reduce per epoch to the
algorithm explicitly or customize the queue to embed the 'terminate_early?'
predicate into the distributed queue.  This is (IMHO) the canonical way to
handle depth-limited searches in BGL and a method that I find myself using
repeatedly.  It's so trivial to implement (at least in the sequential case)
that I've never felt that it warranted a separate algorithm.

Regards,
Nick