Gegeben eine DAG, entfernen Sie Knoten, die ausschließlich in Pfaden vorhanden sind, die kürzer als Länge 3 sind.

Question

Ich arbeite mit gerichteten azyklischen Graphen in networkx. Ich habe Diagramme, die wie die folgende Abbildung aussehen.

Ich möchte im Wesentlichen alle Knoten aus diesem Graph entfernen, die ausschließlich mit Pfaden mit einer Länge von weniger als 3 verbunden sind. Zum Beispiel würde ich im obigen Diagramm alle blauen Knoten löschen und nur die behalten Rote.

Was wäre ein bester Algorithmus dafür, wenn man bedenkt, dass diese Graphen sehr groß werden können (bis zu 10K Knoten)?

Eine ähnliche Frage here konzentriert sich nur auf Binärbäume und wird nicht auf meinen Fall anwendbar sein. Ich würde es vorziehen, dies auf Python (networkx) zu erreichen.

Danke!

Answer 1

1. erzeugen, um die Höhenkarte (ein Wörterbuch von Knoten zu Höhe)
2. die inversen Graphen erzeugen, wenn nötig (alle Ränder umgekehrt sind)
3. die Tiefenkarte erzeugen (die nur die Höhenkarte der inversen ist graph)
4. nodes = [n für n in Knoten, wenn HMAP [n] + DMAP [n]> = 3]

, dass O ist (Knoten + Kanten)