[graph-tool] Extract a neighborhood of a randomly selected node

Alexandre Hannud Abdo abdo at member.fsf.org
Sat May 7 01:22:54 CEST 2016

Hi jimmy/gogurt,

The predecessor graph, returned by predecessor_tree, contains all the nodes
from the original graph, and edges representing the predecessor
relationships given by the map.

In any case, understand that normally you should not have to create an
intermediate graph in order to filter a graph, since you can just use the
information you had to begin with to directly build the filter.

In your case, notice that to get the information you need you don't need
the predecessor map, just the distance map which always gets returned by

The logic being: all vertices reached by shortest_distance get a distance
attributed which is an integer smaller than the size of the graph,
otherwise they get attributed an "impossible" distance which is larger than
the size of the graph.

(In your case the vertices of interest have distance of less or equal to 2,
but as you already tell shortest_distance to stop at distance 2, any vertex
that has a higher distance will still be mapped to the "impossible"
distance, so we can just compare the distance to the size of the graph.)

All you have to do is create a new property and assign values to it
according to what you find in the distance map:

g = gt.Graph()

v = g.vertex( random.randint( 0, g.num_vertices() ) )

dmap = gt.shortest_distance( g, source=v, max_dist=2 )

mymap = g.new_vertex_property( 'bool' )

for w in g.vertices():
  if dmap[w] < g.num_vertices():
    mymap[w] = True

Now you can use mymap in GraphView.

I haven't actually ran the code so there might be typos.
Good luck and have fun!


On Fri, May 6, 2016 at 11:02 PM, gogurt <gogurt at gmail.com> wrote:

> Hi all,
> I have a pretty large graph G from which want to do the following:
> 1) Randomly select a node from G
> 2) Get the vertices that lie within radius 2 of the node
> 3) Extract the subgraph induced by those vertices
> My code for doing this is the following:
> /
> randnode = random.randint(0,G.num_vertices())
> pred_map = gt.shortest_distance(G, source=G.vertex(randnode), max_dist=2,
> pred_map=True)
> pred_tree = gt.predecessor_tree(G, pred_map[1])
> #print(pred_tree.num_vertices())
> verts = pred_tree.vertices()
> vmap = G.new_vertex_property('bool')
> for i in verts:
>     vmap[G.vertex_index[i]] = True
> /
> Then using vmap, I plan to do a GraphView on G and get the subgraph. But
> something is clearly going wrong here. If I uncomment the line under the #
> DEBUG comment, then I clearly see that pred_tree always has the same number
> of vertices as the original graph.
> Am I missing something about how predecessor_tree() works? I expected it to
> only return a subgraph of the original graph, which should have a lot fewer
> vertices...
> --
> View this message in context:
> http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Extract-a-neighborhood-of-a-randomly-selected-node-tp4026565.html
> Sent from the Main discussion list for the graph-tool project mailing list
> archive at Nabble.com.
> _______________________________________________
> graph-tool mailing list
> graph-tool at skewed.de
> https://lists.skewed.de/mailman/listinfo/graph-tool
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20160507/6a13a012/attachment.htm>

More information about the graph-tool mailing list