Эффективный способ суммирования всех уникальных значений предков в инкрементной DAG - PullRequest
Новая
       37

Эффективный способ суммирования всех уникальных значений предков в инкрементной DAG

3 голосов
/ 18 марта 2019

Допустим, у нас есть группа DAG, которая создается постепенно.Это означает, что:

  • узлы добавляются один на
  • , когда добавляется узел, все его узлы-предки уже должны существовать в графе).

Когда добавляется узел, я хотел бы эффективно рассчитать сумму всех его уникальных предков (включая текущий узел).Sample graph

Например, когда добавляется узел, помеченный «7», сумма его уникальных предков равна 29. Один из способов (неэффективный) сделать это просто пройти всепредки, и добавьте значение узла к сумме, если он еще не был посещен.

Другой способ - отслеживать сумму предков на каждом узле.Когда добавляется новый узел, я могу использовать суммы от родителя, но мне нужно убедиться, что некоторые узлы не учитываются дважды (узел 5 и узел 10).

Какой самый эффективный способсделать это?

1 Ответ

0 голосов
/ 01 апреля 2019

Ну, может, мой калькулятор сломан, но он показывает, что 7 + 18 + (19-15) + 7 = 36, а не 29, что приводит нас к тому, что ваша задача - вычислить сумму предков всех узлов , Есть два способа их вычисления:

Загрузка процессора, но экономия памяти и простота чтения:

В библиотеке Python networkx это можно решить с помощью одной строки:

sum(DAG.nodes[n]['cost'] for n in nx.ancestors(DAG, your_node) | {your_node})

Где cost - атрибут на узел, представляющий его значение.

Вот полный рабочий процесс, вы можете скопировать его в блокнот Jupyter и проверить в интерактивном режиме: 

import networkx as nx
from random import randint

# Create DAG
G = nx.gnp_random_graph(10,0.3,directed=True)
DAG = nx.DiGraph([(u,v) for (u,v) in G.edges() if u<v])

# Fill 'cost' attributes
for n in DAG.nodes:
    DAG.nodes[n]['cost'] = randint(1,10)

# Set the start node
node = 8

# Print the ancestors sum
print(sum(DAG.nodes[n]['cost'] for n in nx.ancestors(DAG, node) | {node}))

Обратите внимание, что ancestors довольно потребляет процессор ( O (n ^ 2) для каждого узла в невзвешенном графе, как я понимаю) и не должен использоваться для больших графов.

Экономия ЦП, но занимающая много памяти и довольно сложная для чтения:

Если информация о предках необходима для всех узлов, нет необходимости пересчитывать все возможные предки для каждого узла, вы можете повторно использовать предков предшественников. Таким образом, вы должны реализовать эту логику вручную: 

def set_node_ancestors(DAG, node):
    ancestors = {node}
    for n in DAG.predecessors(node):
        ancestors = ancestors | DAG.nodes[n]['ancestors']
    DAG.nodes[node]['ancestors'] = ancestors

Этот алгоритм проверяет всех предшественников данного узла, принимает их параметры ancestors, объединяет их и записывает результат в параметр ancestors данного узла. Затем для каждого узла вы можете суммировать все затраты на узлы в параметре ancestors.

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

Второй алгоритм намного быстрее первого. Вот сравнение общего времени вычисления предков для каждого узла графа (ось X содержит количество узлов в графе, ось Y - время в миллисекундах):

enter image description here

...