Removing vertices but keeping old indices or other unique identifer for vertices?

graph-tool
1

graph-tool 2.98, CachyOS Linux

I am trying to find all triangles in a planar graph using Chiba and Nishizeki’s algorithm (https://doi.org/10.1137/0214017). This involves lists of neighbours of vertices and iterative removal of vertices that have been found so far.

With NetworkX I can simply remove a vertex from a graph and the remaining vertices still keep their old indices.

If I understand correctly this does not work in graph-tool because ‘[v]ertices are always indexed contiguously in the range [0, N-1]’ ( Graph — graph-tool 2.98 documentation ).

I tried masking, but it seems to me that this fails for the same reason: a vertex identified by its index before masking does not (necessarily) have the same index after masking.

import copy
import graph_tool.all as gt
import numpy as np

points = np.random.random((10, 2)) * 4
g, pos_triangulation = gt.triangulation(points)

triangles = []
g_ = copy.deepcopy(g)
vs = np.argsort(g_.get_total_degrees(list(g_.vertices())))[::-1]  # vs is a list of nodes sorted by degree in descending order, https://stackoverflow.com/questions/16486252/is-it-possible-to-use-argsort-in-descending-order
nodes_to_mask = []
for v in vs:
    v_neighbours = g_.get_all_neighbors(v)  # errors out here because of re-indexed vertices after first iteration
    for u in v_neighbours:
        u_neighbours = g_.get_all_neighbors(u)
        for w in u_neighbours:
            if w in v_neighbours:
                triangles.append([int(v), int(u), int(w)])
        np.delete(v_neighbours, np.argwhere(v_neighbours==u))
    # g_.remove_vertex(v)
    nodes_to_mask.append(v)
    mask_for_all_nodes = np.zeros_like(g_.get_vertices())
    for node in nodes_to_mask:
        mask_per_node = (g_.get_vertices()==node)
        mask_for_all_nodes = [a or b for a, b in zip(mask_for_all_nodes, mask_per_node)]  # https://stackoverflow.com/questions/32192163/python-and-operator-on-two-boolean-lists-how
    mask_gt = g_.new_vp('bool', vals=mask_for_all_nodes)
    g_.set_vertex_filter(mask_gt)

print(triangles)

What would be a proper workaround or method to effectively remove vertices from a graph but keep the old indices, or some other unique but persistent identifier?

2

Please read the documentation in detail, specially the part about property maps: Quick start guide — graph-tool 2.98 documentation

You can convert the indices to a property map, which will remain invariant when you remove vertices.