python, копирование igraph с перенумерацией вершин

Я реализую алгоритм поиска плотного подграфа в ориентированном графе с использованием python + igraph. Основной цикл поддерживает два подграфа S и T, которые изначально идентичны, и удаляет узлы (и инцидентные ребра) в соответствии с подсчетом степени (или степени выхода) этих узлов по отношению к другому графу. У меня проблема в том, что igraph перенумеровывает вершины, поэтому, когда я удаляю некоторые из 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)

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


python igraph
person Raphael    schedule 24.08.2012    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Одна из возможностей - присвоить вершинам уникальные имена в атрибуте вершины 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.

person Tamás    schedule 24.08.2012
comment
Спасибо. Как это будет работать, если граф считывается с помощью Graph.Read_Ncol () (у него миллионы узлов / ребер)? Должен ли я как-то написать цикл, который называет каждую вершину собственным идентификатором? - person Raphael; 25.08.2012
comment
Вы можете назначить имена всем вершинам сразу, используя g.vs["name"] = list_of_names, как я сделал выше в моем примере (см. Вторую строку). Но на самом деле, если вы используете Graph.Read_Ncol, атрибут name уже присутствует, он содержит имена из исходного файла NCOL. - person Tamás; 26.08.2012