Ich analysiere den Kontrollflussgraphen einer Funktion, die eingehende Daten grundsätzlich auf ausgehende Daten abbildet. Die meisten Blöcke sind wie folgt:
%Vor%Ein typisches Kontrollflussdiagramm für einen solchen Code sieht wie das folgende Diagramm aus
%Vor% wobei die Ausführung von 3 und 4 durch den Wert von input_variable bedingt ist, aber 5 unabhängig ist.
Wie finde ich bei einem gerichteten Graphen und einem Startknoten den nächsten Knoten, so dass ein beliebiger Pfad vom Startknoten durch diesen Knoten geht?
Beispiel: In Anbetracht dieses Diagramms finde ich 6 beginnend mit 2 oder 12 startend von 8 ?
Kann ich einen Lowest Common Ancestor-Algorithmus umkehren und wäre das effizient? Wie
%Vor%Meine Programmiersprache ist Python und ich habe gerade NetworkX entdeckt, aber jeder Algorithmus wäre willkommen. Ich bin nicht an die Graphentheorie gewöhnt und ich glaube, ich vermisse das grundlegende Glossar, um zu finden, wonach ich suche.
Danke für Ihre Hilfe!
Nicht die effizienteste Lösung, aber hier ist etwas, das Ihnen den Einstieg erleichtern sollte:
Machen Sie ein DFS, berechnen Sie dann die Schnittmenge aller Pfade (Knoten, die in jedem Pfad existieren). Suchen Sie dann unter diesen Knoten denjenigen, der in jedem Pfad dem Anfang am nächsten erscheint:
%Vor% Beachten Sie, wie 6 in einigen Pfaden bei Index 2 und in einigen anderen Pfaden bei Index 1 angezeigt wird. Wenn es einen Knoten (etwa x) gäbe, der bei Index 1 in den Pfaden auftauchte, wo 6 bei Index 2 auftaucht, und bei Index 2, wo 6 bei Index 1 auftaucht, dann wäre das eine Bindung, die dieser Algorithmus hat würde willkürlich brechen. Je nach Ihren Anforderungen möchten Sie möglicherweise festlegen, wie dieser Fall besser behandelt wird
Sie können so etwas tun:
Finde für jeden Knoten die Liste aller seiner Vorfahren und Nachkommen. Wenn Größe (Vorfahren) + Größe (Nachkommen) + 1 gleich der Netzwerkgröße ist, ist es ein Kandidat. Finde nun einen solchen Knoten mit mindestens einem Vorgänger und einer maximalen Anzahl von Nachkommen.
Die Liste der Vorfahren und Nachkommen kann ziemlich einfach berechnet werden. Lassen Sie es mich wissen, wenn Sie nicht sicher sind, und ich werde meine Antwort erweitern.
Bei all Ihren vorgeschlagenen Lösungen habe ich eine Idee gefunden. Ich gebe meinem ersten Knoten eine Menge von 1. Rekursiv erhalten alle Kinder einen gleichen Anteil dieses Betrags. Sie schicken diesen Betrag ihrerseits nach unten. Wenn ein Kind insgesamt 1 (die Startmenge) erhält, ist es der "Knotenpunkt". Hier ist meine Implementierung (offen für Kommentare !!).
Ich hoffe, dass das BFS-Konstrukt die Anzahl der besuchten Knoten begrenzt.
%Vor%