# How can I efficiently and uniformly sample the set of vertices a fixed edge-wise distance away from a chosen vertex?

I have a large graph $G$, which may be either directed or undirected. How would I use DepthFirstScan[] or BreadthFirstScan[] to efficiently and uniformly sample the set of vertices a fixed shortest distance of $D$ away from some vertex $v_i \in V$?

Start with a graph and a distance d:

g = RandomGraph[BarabasiAlbertGraphDistribution[1000, 1]];

d = 5


Find the distance of a vertex (e.g. vertex 300) to all others:

distances = GraphDistance[g, 300];


Sample k vertices from those with distance d from 300:

RandomSample[
Pick[VertexList[g], distances, d],
k
]

• other variance could be: Reap[CheckAbort[ BreadthFirstScan[g, 300, "DiscoverVertex" -> ((If[#3 > 5, Abort[]]; If[#3 == d, Sow[#1]]) &)], "Done"]][[2, 1]] or Complement[AdjacencyList[g, 300, d], AdjacencyList[g, 300, d - 1]] – halmir Apr 24 '13 at 14:13
• @halmir Why don't you post it as another answer? Instead of Abort[] I'd use Return[] (after wrapping the whole thing in a function). Or use two-argument Return. It's cleaner. – Szabolcs Apr 24 '13 at 15:08

Alternative way to extract vertices:

g = RandomGraph[BarabasiAlbertGraphDistribution[1000, 1]];
d = 5;

1. Szabolcs suggestion

distances = GraphDistance[g, 300];
set1 = Pick[VertexList[g], distances, d];


set2 = Reap[
CheckAbort[
BreadthFirstScan[g, 300, "DiscoverVertex" -> ((If[#3 > 5, Abort[]];
If[#3 == d, Sow[#1]]) &)], "Done"]][[2, 1]];


with Return[]

set3 = Reap[
BreadthFirstScan[g, 300, "DiscoverVertex" -> ((If[#3 > 5, Return[]];
If[#3 == d, Sow[#1]]) &)]][[2, 1]];


set4 = Complement[AdjacencyList[g, 300, d], AdjacencyList[g, 300, d - 1]];


Compare results:

In[271]:= Sort[set1] == Sort[set2] == Sort[set3] == Sort[set4]
Out[271]= True