Учитывая DAG, удаляйте узлы, которые присутствуют только в путях короче длины 3

Question

Я работаю с направленными ациклическими графами в networkx. У меня есть графики, которые выглядят как на рисунке ниже.

По сути, я хочу удалить из этого графа все узлы, которые связаны исключительно с путями длиной менее 3. Например, на приведенном выше графике я бы удалил все синие узлы и оставил только красные.

Каков наилучший алгоритм для этого, если учесть, что эти графики могут расти очень большими (до 10 тыс. Узлов)?

Подобный вопрос здесь касается только бинарных деревьев и не применим к моему случаю. Я бы предпочел добиться этого на Python (networkx).

Спасибо!

Answer 1

1. генерировать карту высоты (словарь от узла к высоте)
2. генерировать обратный граф, если необходимо (все ребра перевернуты)
3. генерировать карту глубины (которая является просто картой высот обратного графика)
4. node = [ n для n в узлах, если hmap[n] + dmap[n] >= 3 ]

Это О (узлы + ребра)