How can I map the index in an unfiltered graph to the index of a filtered graph in python's graph_tool library?

Question

I'm using graph_tool. I want to get the indices of some vertices in the filtered graph. The documentation says

vertex_index Vertex index map.

It maps for each vertex in the graph an unique integer in the range [0, num_vertices() - 1].

But this claim is in contradiction with my experience. Consider the following code:

import graph_tool as gt
import numpy as np

g = gt.Graph([(1,2),(3,4),(5,6)])
filt = np.array([False, False,False,False,True,True,True])
fg = gt.GraphView(g,vfilt=filt)
print(fg.get_vertices()) #as I expect [4,5,6]
print(fg.vertex_index[6]) #I expect 6 to map to 3, since it is the third index in the filtered graph
# perhaps it's messed up because I'm giving it an index, rather than a vertex?
print(fg.vertex_index[fg.vertex(6)]) # still doesn't map 6 to 3

the full output is

[4 5 6]
6
6

Obviously, 6 is not in the range [0, num_vertices()-1]. (or [0,2]). How do I get the index of vertex 6 within fg, the filtered graph?

Since the filtering of vertices in graph-tool is very similar to the filtering of numpy arrays, perhaps an answer could leverage this fact. if this instead was just a question about two numpy arrays, could you give me the index of 6 in fg from the index of 6 in g?

Answer 1

Here's my solution, hackish though it may be. I'd welcome any solution that is more efficient/uses graph-tool alone, but until then, here is how I solved the problem.

First we need to get the vertex filter as an array. Graph.get_vertex_filter() returns a tuple with the filter and a bool representing whether or not the filter is inclusive or exclusive (does true mean to include or exclude that vertex?). So we index the first of the two elements.

At this point, the filter is stored as a property map. We want it as an array, so we call get_array(). The complete line is as follows.

filt = np.array(fg.get_vertex_filter()[0].get_array())

filt in my example will be [0,0,0,0,1,1,1].

note: this filter is the cumulative filter of all graphviews. For example, if you have one graphView with filter [0,0,0,0,1,1,1] and another graphView of the first graphView with the filter [1,0,1], the cumulative filter will be [0,0,0,0,1,0,1].

We want a mapping from indices in an unfiltered graph to indices in a filtered graph. the index in the filtered graph will be the same as in the unfiltered graph, minus the number of elements filtered out that come before the index.

(for example, if our filter was [1,0,1] the 3rd index in the unfiltered graph would be 2 minus the number of zeros before the 3rd index, in this case, there is only one zero, so 2 minus 1.)

subtracting the zeros from the total is equivalent to adding the ones. So we can make an "integral array" (where the value of every index is the sum of the array up to that index).

integralArray = = np.cumsum(filt)-1

this will give us the array [18446744073709551615,18446744073709551615,18446744073709551615,18446744073709551615,0,1,2]. Now, the array maps 4=>0, 5=>1 and 6=>2. Notice, indices that should have been filtered out won't have a meaningful mapping. For example, 2=>18446744073709551615, is not meaningful, since vertex 2 is filtered out and doesn't have any index in the filtered graph.