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

Tiago de Paula Peixoto tiago at skewed.de
Sat May 7 10:00:31 CEST 2016


On 07.05.2016 01:22, Alexandre Hannud Abdo wrote:
> 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 shortest_distance.
>
> 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.

This is entirely right. I would just like to point out that it is a good
idea to avoid iterator loops whenever possible. The above can be done
more compactly and efficiently with:

    dmap = gt.shortest_distance(g, source=v, max_dist=2)
    u = GraphView(g, vfilt=dmap.a < g.num_vertices())

Best,
Tiago

-- 
Tiago de Paula Peixoto <tiago at skewed.de>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20160507/3a1335ba/attachment.asc>


More information about the graph-tool mailing list