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

Question

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

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

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

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

Спасибо!

Answer 1

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

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