Эффективный способ замены узлов в графе networkx сквозными ребрами

Question

Я пытаюсь заменить узлы в графе переходными ребрами.Это означает, что каждый предшественник замененного / удаленного узла будет связан с каждым преемником замененного / удаленного узла.

Например, рассматривая граф путей с 5 узлами, такими, что ребра (0, 1), (1, 2), (2, 3), (3, 4), я хочу заменить узлы 1 и 3 на следующие ребра ((0,2) для узла 1) и ((2,4) дляузел 3).Конечный график должен иметь ребра (0, 2), (2, 4).

Answer 1

Networkx не имеет встроенных функций / алгоритмов для этого, поэтому вы должны сделать это вручную. Itertools Модуль поможет вам автоматизировать построение ребер для создания:

import itertools as it
import networkx as nx


G = nx.DiGraph()
G.add_edges_from([
    (1,2),
    (2,3),
    (3,5),
    (4,5),
    (5,6),
    (5,7)
])

nodes_to_delete = [2, 5]
for node in nodes_to_delete:
    G.add_edges_from(
        it.product(
            G.predecessors(node),
            G.successors(node)
        )
    )
    G.remove_node(node)

Таким образом, G.edges вернет необходимые ребра (1->2->3 перемещено в 1->3 и 3,4,6,7 соединены в пару):

OutEdgeView([(1, 3), (3, 6), (3, 7), (4, 6), (4, 7)])

---

P.S. Я сомневаюсь, что существует более эффективный метод в сети x. В networkx вы должны проверить предшественников / преемников каждого узла, чтобы сложность O была одинаковой.