Filtering a subgraph in graph-tool

Question

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?

Kingcup

Answer 1

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)]

Factory