Использование итератора forEdges в networkit (python)

Question

Я внимательно прочитал документы, но мне все еще неясно, как использовать G.forEdges(), описанный как "экспериментальный интерфейс итераторов ребер".

Допустим, я хочу уменьшить плотность моего графика. У меня есть отсортированный список весов, и я хочу удалить ребра в зависимости от их веса, пока график не разделится на два связанных компонента. Затем я выберу минимальное количество ссылок, которые поддерживают график. Я бы сделал что-то вроде этого:

cc = components.ConnectedComponents(G).run()
while cc.numberOfComponents()==1:
    for weight in weightlist:
        for (u,v) in G.edges():
            if G.weight(u,v)==weight:
                G=G.removeEdge(u,v)

Кстати, из документов я знаю, что существует этот краевой итератор, который, вероятно, выполняет итерацию более эффективно. Но из документов я действительно не могу понять, как правильно использовать это forEdgesи я не могу найти ни одного примера в интернете. Есть идеи?

Или, может быть, альтернативная идея сделать то, что я хочу сделать: поскольку это огромный граф (125 миллионов ссылок), итерация будет длиться вечно, даже если я работаю над кластером.

Answer 1

Итераторы NetworKit принимают функцию обратного вызова, поэтому, если вы хотите выполнить итерацию по ребрам (или узлам), вы должны определить функцию и затем передать ее итератору в качестве параметра. Вы можете найти больше информации здесь. Например, простая функция, которая просто печатает все ребра:

# Callback function.
# To iterate over edges it must accept 4 parameters
def myFunction(u, v, weight, edgeId):
    print("Edge from {} to {} has weight {} and id {}".format(u, v, weight, edgeId))

# Using iterator with callback function
G.forEdges(myFunction)

Теперь, если вы хотите продолжать удалять ребра, вес которых находится внутри вашего списка весов, до тех пор, пока график не разделится на два связанных компонента, вы также должны обновить подключенные компоненты графика, поскольку ConnectedComponents не будет делать это автоматически (это также может быть одним из причины, по которым итерация длится вечно). Чтобы сделать это эффективно, вы можете использовать класс DynConnectedComponents (см. Мой пример ниже). В этом случае я думаю, что пограничный итератор не сильно вам поможет, поэтому я бы посоветовал вам продолжать использовать цикл for.

from networkit import *

# Efficiently updates connected components after edge updates
cc = components.DynConnectedComponents(G).run()

# Removes edges with weight equals to w until components split
def removeEdges(w):
    for (u, v) in G.edges():
        if G.weight(u, v) == weight:
            G.removeEdge(u, v)
            # Updating connected components
            event = dynamic.GraphEvent(dynamic.GraphEvent.EDGE_REMOVAL, u, v, weight)
            cc.update(event)
            if cc.numberOfComponents() > 1:
                # Components did split
                return True
    # Components did not split
    return False

if cc.numberOfComponents() == 1:
    for weight in weights:
        if removeEdges(weight):
            break

Это должно немного ускорить ваш оригинальный код. Тем не менее, это все еще последовательный код, поэтому даже если вы запустите его на многоядерном компьютере, он будет использовать только одно ядро.