python, igraph справляется с перенумерованием вершин

Question

Я реализую алгоритм поиска плотного подграфа в ориентированном графе с использованием питона + igraph. Основная петля поддерживает два подграфа S и T, которые изначально идентичны и удаляют узлы (и кромки инцидентов), соответствующие количеству (или outdegree) этих узлов по отношению к другому графику. Проблема заключается в том, что igraph renumbers вершины, поэтому, когда я удаляю некоторые из T, оставшиеся узлы больше не соответствуют тем же в S.

Вот основная часть цикла, который является ключевым.

def directed(S): 
    T = S.copy() 
    c = 2 
    while(S.vcount() > 0 and T.vcount() > 0): 
     if (S.vcount()/T.vcount() > c): 
      AS = S.vs.select(lambda vertex: T.outdegree(vertex) < 1.01*E(S,T)/S.vcount()) 
      S.delete_vertices(AS) 
     else: 
      BT = T.vs.select(lambda vertex: S.indegree(vertex) < 1.01*E(S,T)/T.vcount()) 
      T.delete_vertices(BT) 

Это не работает из-за эффекта удаления вершин на вершинах. Существует ли стандартный метод решения этой проблемы?

Answer 1

Одна из возможностей - назначить уникальные имена вершинам в атрибуте вершины name. Они сохраняются в неизменном виде, когда вершины удаляются (в отличие от идентификаторов вершин), и вы можете использовать их для ссылки на вершины в таких функциях, как indegree или outdegree. Например .:

>>> g = Graph.Ring(4) 
>>> g.vs["name"] = ["A", "B", "C", "D"] 
>>> g.degree("C") 
2 
>>> g.delete_vertices(["B"]) 
>>> g.degree("C") 
1 

Обратите внимание, что я удалил вершину B поэтому вершина C также получила новый идентификатор, но имя все та же.

В вашем случае, строка с условием select, вероятно, может быть переписан так:

AS = S.vs.select(lambda vertex: T.outdegree(vertex["name"]) < 1.01 * E(S,T)/S.vcount()) 

Конечно, это предполагает, что изначально имена вершин одинаковы в S и T.