Computing k-disks fast

graph-tool
#1

Hello,

given an undirected, unweighted graph and a vertex v, I want to compute
the k-disk around v, i.e. the induced subgraph of vertices at a distanst
at most k from v.

Of course, this can be easily be done by a variation of BFS or DFS. Is
it possible do use graph_tool.search.bfs_search in some way for this?

Best regards,
Chris

attachment.html (1.1 KB)

#2

Just do:

     dist = shortest_distance(g, source=v)
     k_disk = GraphView(g, vfilt=dist.fa <= k)

Best,
Tiago

#3

Thanks for the quick response.

   dist = shortest_distance(g, source=v)
   k_disk = GraphView(g, vfilt=dist.fa <= k)

This will work. But doesn't it first compute the shortest distance from
v to all other vertices in g and then applies a filter? This is rather
inefficient, especially when then graph is huge...

attachment.html (1.73 KB)

#4

You can set "max_dist" in shortest_distance() to limit the search.

Best,
Tiago