Как уменьшить DAG, заменив каждый самый длинный неразветвленный путь ребром, соединяющим начало и конец пути?

Question

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

Например, для такого графа я хотел быхотелось бы уменьшить его

a->b->c->d
a->d

до следующего.Конечно, настоящий DAG может быть более сложным, чем этот.

a->d
a->d

Я не нахожу способ сделать это с networkx.Кто-нибудь знает, как это сделать в сети?Спасибо.

Answer 1

Насколько я знаю, Networkx не поддерживает его "из коробки".Однако это не слишком сложно для реализации.Вы можете просто перебрать узлы на графике и выполнить следующие шаги:

1. Удалить каждый узел с ровно одним входящим ребром и одним исходящим ребром.
2. Соединить с новым ребромисходный узел входящего фронта к целевому узлу исходящего фронта.

Кажется, это работает:

def should_remove_node(graph, node):
    return graph.in_degree(node) == 1 and graph.out_degree(node) == 1

for node in list(G.nodes()):
    if should_remove_node(G, node):
        in_node = list(G.in_edges(node))[0][0]
        out_node = list(G.out_edges(node))[0][1]
        G.add_edge(in_node, out_node)
        G.remove_node(node)