gogurt gogurt - 7 months ago 22
Python Question

Filtering a subgraph in graph-tool

This is a ridiculously basic question about graph-tool which should be trivial to figure out how to solve using the documentation, but I'm spinning in circles. I don't doubt that documentation comprehensive, but it certainly isn't making this easy.

GOAL: Given a graph G, extract the induced subgraph based on a list of vertices of G.

I know I should be doing this with a

GraphView
somehow. I get that. I also understand that I need to make a vertex
PropertyMap
for this. But what exactly should I be creating?

The documentation is very lacking here. For example, the page on PropertyMaps says that each
PropertyMap
can be of a certain type, but I haven't figured out what that means. What do the types represent? When would I want to use one type over another? Given apparently how important
PropertyMaps
are to the efficient usage of graph-tool, I'm a little bewildered at how unclear the docs are.

For this problem, I get the vague sense that I need to use the Boolean type, because maybe I want to set the vertices I want in the subgraph to "true" while the vertices I don't want in the subgraph to "false." But does that mean the
PropertyMap
I create needs to have the same length as the number of nodes in my original graph G? Or can I just provide a list of nodes and somehow let it be understood that those are the only ones to be set to True?

Answer

You are right. You have to use GraphView. In the following example a induced subgraph with vertices 0, 1, 3 are created from a complete graph with 5 vertices

from graph_tool import GraphView, generation

g = generation.complete_graph(5)

# select some vertices
vfilt = g.new_vertex_property('bool');
vfilt[0] = True
vfilt[1] = True
vfilt[3] = True

sub = GraphView(g, vfilt)

print [(g.vertex_index[e.source()], g.vertex_index[e.target()])
           for e in sub.edges()]

Output

[(0, 1), (0, 3), (1, 3)]