Самый низкий общий предок в Python NetworkX

Использование NetworkX

Я хочу получить наименьшего общего предка от node1 и node11 в DiGraph.

Ниже приведен код.

import networkx as nx

G = nx.DiGraph() #Directed graph
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])
G.add_edges_from([(2,1),(3,1),(4,1),(5,2),(6,2),(7,3),(8,3),(9,3),(10,4),(10,12),(14,9),(15,8),(12,11),(13,11),(14,12),(15,13)])

ancestors1 = nx.ancestors(G, 1)
ancestors2 = nx.ancestors(G, 11)

src_set = set(ancestors1)
tag_set = set(ancestors2)
matched_list = list(src_set & tag_set)

dic = {}

for elem in matched_list:
    print elem
    length1 = nx.dijkstra_path_length(G, elem, 1)
    path1 = nx.dijkstra_path(G, elem, 1)
    dist1 = len(path1)
    length2 = nx.dijkstra_path_length(G, elem, 11)
    path2 = nx.dijkstra_path(G, elem, 11)
    dist2 = len(path2)
    dist_sum = dist1 + dist2
    dic[elem] = dist_sum

min_num = min(dic.values()) 
for k, v in sorted(dic.items(), key=lambda x:x[1]):
    if v != min_num:
        break
    else:
        print k, v

У меня проблема со скоростью выполнения, поэтому я хочу повысить скорость выполнения.

Если у вас есть хорошая идея или алгоритм, пожалуйста, скажите мне эту идею.

Извините за плохой английский.

Источник

2 ответа

Решение

Перезапуск Dijkstra в цикле действительно кажется излишним.

Скажем, мы строим орграф, получаемый путем обращения краев:

import networkx as nx

G = nx.DiGraph() #Directed graph
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])
edges = [(2,1),(3,1),(4,1),(5,2),(6,2),(7,3),(8,3),(9,3),(10,4),(10,12),(14,9),(15,8),(12,11),(13,11),(14,12),(15,13)]
G.add_edges_from([(e[1], e[0]) for e in edges])

Теперь мы запускаем BFS с каждого из двух узлов:

preds_1 = nx.bfs_predecessors(G, 1)
preds_2 = nx.bfs_predecessors(G, 11)

Найти общие вершины, достижимые из обоих узлов в обратном графе, легко:

common_preds = set([n for n in preds_1]).intersection(set([n for n in preds_2]))

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

>>> min(common_preds, key=lambda n: preds_1[n])
10
Источник

Для этого вы можете использовать функции, определенные в networkx.algorithms.lowest_common_ancestor. Он имеет более быструю версию, которая работает только на деревьях, и более медленную версию, которая будет работать с любым ориентированным ациклическим графом. Поскольку ваш пример DAG, я буду использовать последний.

# Same as in your example
import networkx as nx
G = nx.DiGraph() #Directed graph
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])
G.add_edges_from([(2,1),(3,1),(4,1),(5,2),(6,2),(7,3),(8,3),(9,3),(10,4),(10,12),(14,9),(15,8),(12,11),(13,11),(14,12),(15,13)])

# Compute the lowest common ancestor of 1 and 11. This will print 15.
print nx.algorithms.lowest_common_ancestor(G, 1, 11)

Обратите внимание, что это вычисляет наименьшего общего предка, определяемого максимальным расстоянием от источников графа; согласно этому определению 10 и 15 являются самыми низкими общими предками для (1, 11), и это дает 15. Ваш исходный код (и предыдущий ответ) дополнительно минимизирует путь от 1 и 11 до LCA, что дает 10 (сумма расстояния 6) вместо 15 (сумма расстояния 7). Если вам также требуется это свойство, то этот модуль, скорее всего, не подойдет.

Используя этот модуль, время выполнения для поиска LCA для одной пары узлов составляет O(n log(n)) в размере графика. Время выполнения для поиска LCA для всех пар узлов - O(n^3).

Источник
Другие вопросы по тегам