Baumartige Struktur in der richtigen Reihenfolge berechnen

[cltom]

Hallo,

eine scheinbar einfache Aufgabe, die aber doch zwickt: es soll eine baumartige Struktur von Zweigen bis zum Stamm in der korrekten Reihenfolge abgearbeitet werden. Die Grundregel lautet: bevor ein Ast berechnet wird, müssen alle Zweige, die zu diesem Ast führen berechnet werden. Der "Stamm" bleibt also immer über und muss zuletzt berechnet werden. Davor all jene Äste, die zum Stamm führen. Davor jene, die zu diesen Ästen führen.

Alle Zweige/Äste/Stämme haben eine fortlaufende Nummer, die in keinem Zusammenhang mit der Struktur stehen. Jeder Zweig kennt aber die Nummer jenes Zweiges, auf den er trifft. Dazu noch eine Positionsangabe, um zwei Zweige, die nacheinander auf einen Ast treffen, zu unterscheiden.

Gesucht ist die Reihenfolge, in der die Zweige abgearbeitet werden sollen. Um das zu veranschaulichen, ein paar Beispiele anbei. Streng genommen ist im letzten Beispiel die Reihenfolge von 7 und 1 egal. 7 muss vor 6 berechnet werden und 1 vor 2. Ob aber 7 zuerst oder 1 zuerst, macht keinen Unterschied.

Als Startidee muss man wohl alle Zweige durchgehen und den Stamm finden. Jenen Zweig also, der keinen weiteren Zweig als Ziel hat. Dann muss man jene Zweige finden, die auf diesen Zweig führen. Dann jene, die auf diese Zweige führen. Dazu müsste man aber alle Zweige so oft durchgehen, wie es Anzahl an Zweigen gibt. Das müsste doch effizienter gehen?

Alternativ könnte man jeden Zweig durchgehen und den Pfad notieren. Das würde eine Liste von Pfaden ergeben, die letztlich alle im Stamm münden. Es würde aber natürlich nicht reichen, diese Pfade rückwarts durchzugehen.

Ich hab noch keine Idee.

Ein wenig Pseudo-Code, der aber nur die Struktur skizziert.

Delphi-Quellcode:

Type
  TBranch = record
    BranchID : integer;
    TargetBranchID : integer;
    TargetBranchPosition: integer;
  end;


Type
  TTree = record
    Branches : array[0..MaxBranches] of TBranch;
  end;


Type
  TCalculationOrder = array[0..MaxBranches] of integer;



procedure GetBranchOrder(Tree : TTree; var CalculationOrder : TCalculationOrder); 
var
  i : integer;
begin

  for i:=MaxBranches-1 downto 0 do
    begin
      

    end;

end;

[stahli]

Reicht es evtl. sogar, einfach alle Records nach TargetBranchPosition zu sortieren?
Nach Deiner Skizze würde es wohl reichen (wenn man die absoluten Rechts-Werte der Linien betrachtet), aber ob das für alle Varianten gilt, ist natürlich nicht sicher.

Zumindest könntest Du darüber vermutlich die ersten Zweige finden und Dich von dort durchhangeln. Jeden schon genutzten Zweig dann aus der Liste streichen.

[cltom]

Zitat:

Zitat von stahli (Beitrag 1496174)

Reicht es evtl. sogar, einfach alle Records nach TargetBranchPosition zu sortieren?
Nach Deiner Skizze würde es wohl reichen (wenn man die absoluten Rechts-Werte der Linien betrachtet), aber ob das für alle Varianten gilt, ist natürlich nicht sicher.

Zumindest könntest Du darüber vermutlich die ersten Zweige finden und Dich von dort durchhangeln. Jeden schon genutzten Zweig dann aus der Liste streichen.

Guter Gedanke. Allerdings ist TargetBranchPosition kein absoluter Wert, der über alle Zweige hinweg gilt sondern nur eine relative Angabe für jeden Zweig. Ich müsste mal sehen, ob ich einen solchen absoluten Wert ableiten könnte.

Was ich inzwischen gefunden habe:
https://en.wikipedia.org/wiki/Tree_traversal
https://towardsdatascience.com/4-typ...s-d56328450846

offenbar hat es wieder nur den richtigen Suchbegriff gebraucht ... Post-order traversal for non-binary trees ist die Antwort - jetzt noch eine nachvollziehbare Implementierung finden ... omg ... was für ein Hornissennest

[Möbius]

Guten Tag

Der Zweck Deiner Funktion ist nicht ganz klar.
Aber beim erstellen des Baums (also Bottom Up) und berechnen Deiner Werte soltest Du Deinem Baum bzw. seinen Knoten und Blättern einen Zeiger auf den Parent (Elternknoten) Node spendieren.
So kommst Du einfach vom Blatt zur Wurzel.
Der Rückweg ist allerdings etwas schwieriger (falls nötig). Du müsstest bei Deinen Eingabedaten einen Zeiger vermerken wenn Du Dich auf den "Vorwärtsweg" durch den Baum machst (und die Berechnungen durchführst) und so von den Eingangsdaten erneut zum gleichen Blatt/Knoten gelangst (ohne die Berechnung erneut durchzuführen).

So sollte es klappen

LLG
Möbius

[cltom]

Zitat:

Zitat von cltom (Beitrag 1496176)

Zitat:

Zitat von stahli (Beitrag 1496174)

Reicht es evtl. sogar, einfach alle Records nach TargetBranchPosition zu sortieren?
Nach Deiner Skizze würde es wohl reichen (wenn man die absoluten Rechts-Werte der Linien betrachtet), aber ob das für alle Varianten gilt, ist natürlich nicht sicher.

Zumindest könntest Du darüber vermutlich die ersten Zweige finden und Dich von dort durchhangeln. Jeden schon genutzten Zweig dann aus der Liste streichen.

Guter Gedanke. Allerdings ist TargetBranchPosition kein absoluter Wert, der über alle Zweige hinweg gilt sondern nur eine relative Angabe für jeden Zweig. Ich müsste mal sehen, ob ich einen solchen absoluten Wert ableiten könnte.

Was ich inzwischen gefunden habe:
https://en.wikipedia.org/wiki/Tree_traversal
https://towardsdatascience.com/4-typ...s-d56328450846

offenbar hat es wieder nur den richtigen Suchbegriff gebraucht ... Post-order traversal for non-binary trees ist die Antwort - jetzt noch eine nachvollziehbare Implementierung finden ... omg ... was für ein Hornissennest

Selbstkorrektur: Tree Traversal ist nicht die Antwort, weil dort die Knoten/Kinder gleichberechtigt sind. Das ist hier aber nicht der Fall, da ich zusätzlich ja noch die Information berücksichtigen muss, an welchem Punkt die Zweige ansetzen und die Reihenfolge stimmen muss. Es sind also die Zweige eines Astes (Childrenn eines Parent) zusätzlich zu sortieren ...

[Gausi]

Eine Baumstruktur in den Daten verwaltet man ja eigentlich nicht als "Zweige" sondern als einzelne "Knoten". In einem Baum gibt es dann genau einen Wurzelknoten. An diesem hängen dann Kindknoten, die dann weitere Kindknoten haben können. Bei Binärbäumen kann man die Kindknoten in zwei Knoten-Variablen speichern (die dann ggf. left und right heißen), bei Bäumen mit höherem Grad verwaltet man die Kindknoten in einer Liste/Array/Dictionary/whatever, die man nach eigenem Ermessen sortieren kann (oder auch nicht). Jeder Kindknoten hat meist noch eine Referenz auf den Parent.

Zum Berechnen von irgendwas auf dem Baum ruft man dann eine Methode "Calculate" des RootKnoten auf, die dann z.B. so aussehen könnte.

Delphi-Quellcode:

function TMyNode.Calculate: Integer;
var i, sum: Integer
begin
  sum := 0;
  for i := 0 to ChildNodes.Count - 1 do
    sum := sum + ChildNodes[i].Calculate; 
  fSubNodeCount := sum
  result := sum + 1;
end;

Diese Funktion würde z.B. die Anzahl der Elemente in dem Baum angeben (wenn ich mich auf die Schnelle nicht vertan habe), aber da kann man natürlich beliebige Dinge berechnen. ;-)

Oder anschaulich: Du musst den Wurzelknoten kennen - also den "Stamm". Wenn der etwas berechnen will, kümmert sich der Stamm darum, dass alle nötigen Daten vorliegen. Wenn er dazu Daten von seinen Kindknoten bzw. den daran hängenden Zweigen kennen muss, dann teilt er diesen das mit. Und wenn diese dafür wieder weitere Daten von Unterzweigen brauchen, dann läuft das automatisch nach unten durch.

Wenn die Reihenfolge der Kindknoten relevant ist (z.B. 5 muss vor 3 berechnet werden), dann kann man das erreichen, indem man die Kindknotenliste eines Knotens vor der Berechnung entsprechend sortiert.

[cltom]

Zitat:

Zitat von Möbius (Beitrag 1496179)

Guten Tag

Der Zweck Deiner Funktion ist nicht ganz klar.
Aber beim erstellen des Baums (also Bottom Up) und berechnen Deiner Werte soltest Du Deinem Baum bzw. seinen Knoten und Blättern einen Zeiger auf den Parent (Elternknoten) Node spendieren.
So kommst Du einfach vom Blatt zur Wurzel.
Der Rückweg ist allerdings etwas schwieriger (falls nötig). Du müsstest bei Deinen Eingabedaten einen Zeiger vermerken wenn Du Dich auf den "Vorwärtsweg" durch den Baum machst (und die Berechnungen durchführst) und so von den Eingangsdaten erneut zum gleichen Blatt/Knoten gelangst (ohne die Berechnung erneut durchzuführen).

So sollte es klappen

LLG
Möbius

Danke für Deine Überlegungen. Ganz hab ich sie nicht verstanden.

Die Struktur des Baumes ist erst einmal dadurch definiert, dass jeder Zweig einen Ziel-Zweig hat, in den er mündet und einen Wert, an welcher Position im Zielzweig er mündet.


Im letzten Beispiel:

BranchID 1 2 3 4 5 6 7
TargetBranchID 2 3 4 4 4 5 6
TargetPosition a b c d e f g

mit c>e, weil Zweig 3 vor Zweig 5 auf 4 trifft. Der Rest im Grunde beliebig. Und beim Stamm (4) selber ist der Zielwert (d) irrelevant (Null oder die Gesamtzahl des Zweiges).

Das Parent mitgeben hatte ich auch überlegt, ist aber nicht eindeutig für die Struktur, weil in dem Beispiel der Zweig 4 ja aus zwei weiteren Zweigen gespeist wird. Es könnte auch der Fall eintreten, dass ein Zweig selber viele (10+) Zweige hat, die auf ihm sitzen:

BranchID 1 2 3 4 5 6 7
TargetBranchID 7 7 7 7 7 7 7


Hier münden alle Zweige auf 7. 7 könnte also kein eindeutiges Parent haben. Es wäre eine Liste von Parents. Hilft das?

[stahli]

Ich verstehe das Problem als ähnlich einem Puzzle...

Die Zweige liegen in einer eindimensionalen Liste und müssen als Baum interpretiert werden - richtig?
Erst dann hat man eine Baumstruktur, von der Gausi ausgeht - auch richtig?

Vielleicht kannst Du ja Deine Datenstruktur gleich komplett so ändern, dass Du verkettete Listen verwendest?
So hättest Du direkt eine Wurzel, von der Du ausgehen kannst.

[cltom]

Zitat:

Zitat von stahli (Beitrag 1496185)

Ich verstehe das Problem als ähnlich einem Puzzle...

Die Zweige liegen in einer eindimensionalen Liste und müssen als Baum interpretiert werden - richtig?
Erst dann hat man eine Baumstruktur, von der Gausi ausgeht - auch richtig?

Vielleicht kannst Du ja Deine Datenstruktur gleich komplett so ändern, dass Du verkettete Listen verwendest?
So hättest Du direkt eine Wurzel, von der Du ausgehen kannst.

richtig und richtig. im Grunde hab ich keine Baumstruktur, sondern nur eine List von Verzweigungen.

Verkettete Listen - hmm, da hat jedes Element genau einen Vorgänger/Nachfolger. Das hab ich aber nicht. Ein Element kann nur einen Nachfolger, aber "beliebig" viele Vorgänger haben.

Die Datenstruktur ist in der Tat aber völlig offen. Es ist letztlich ein Haufen Objekte, die einige ihrer Werte an ein nächstes Objekt übergeben.

[stahli]

Du kannst ja einem Objekt eine Liste spendieren, in der es beliebige andere Objekte (Vorgänger oder Nachfolger ist egal bzw. nur eine Frage der Benennung) verwalten kann.

I.d.R. Geht man von einer Wurzel aus, die sich immer weiter verzweigt. Die Wurzel hat dann weitere Kinder, die ihrerseits wieder weitere Kinder haben. So kannst Du von der Wurzel aus alle Kinder erreichen. Wenn die Kinder wiederum ihren Parent kennen, kannst Du in beide Richtungen navigieren.

Was Du beschreibst, ist eigentlich genau solch eine Struktur, nur eben von Rechts nach links abgebildet anstatt üblicher von links nach rechts oder oben nach unten.