Graph-Tool: Как мне поддерживать упорядоченный набор вершин?

Question

Я работаю в сети, используя Graph-Tool.

В наборе всех вершин есть определенные группы вершин с четко определенным порядком, которые я хотел бы отслеживать. До сих пор я поддерживал внешнюю структуру данных со ссылками на вершины в правильном порядке. Однако, когда вершина удаляется, все вершины с индексом, превышающим индекс, который был удален, переиндексируются, что уничтожает ссылки, которые я хранил в моей внешней структуре данных.

Как правильно сохранить упорядоченное подмножество вершин, чтобы оно не разрывалось, когда (например) нулевая вершина удаляется из графа?

from graph_tool.all import *

graph = Graph(directed=False)
graph.add_vertex(5)

""" fifth_vertex is a reference to the vertex with an index of 5. """
fifth_vertex = graph.add_vertex()
assert graph.vertex_index[fifth_vertex] == 5

""" upon removal of a vertex at index i, all vertices of index > i are reindexed. fifth_vertex no longer references a vertex. """
graph.remove_vertex(graph.vertex(0))


""" assertion error """
assert fifth_vertex in graph.get_vertices()

Answer 1

Индексы вершин всегда находятся в непрерывном диапазоне в Graph-Tool.

Чтобы реализовать то, что вы хотите, вам нужно использовать карты свойств:

from graph_tool.all import *

g = Graph(directed=False)
g.add_vertex(6)

index = g.vertex_index.copy()  # copies the vertex index as a stand-alone property map

g.remove_vertex(0)

v = find_vertex(g, index, 5)[0]

assert g.vertex_index[v] == 4
assert index[v] == 5