Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

[Namenloser]

Zitat von Matze:

Stopp!
Mir geht's NICHT um die Visualisierung. Vielleicht habe ich mich falsch ausgedrückt.
Ich möchte das nur in einer internen Struktur haben, die ich ausgeben KÖNNTE, aber mir geht's hauptsächlich darum, dass die Software intern "weiß", welche möglichen Wege es gibt ohne Visualisierung.

Aber die interne Struktur hast du doch bereits mit deiner „schematischen Darstellung“. Du hast eine Liste von Knoten und eine Liste von Kanten, dadurch ist der Graph vollständig definiert.

Was willst du durch die Darstellung dem Nutzer denn erleichtern? Welche Fehlerquellen sollen z.B. aufgedeckt werden? Davon würde ich dann abhängig machen, wie die Darstellung aussehen soll. Und davon ist wiederum abhängig, welche interne Darstellungsform am besten geeignet ist.

Wie bereits gesagt wurde, gibt es exponenziell viele Pfade, mit Kreisen sogar unendlich viele. Da bringt es wohl wenig, einfach alle theoretisch möglichen Pfade bruteforce-mäßig auszugeben.

Die Glaskugel sagt, dass eine Wegematrix vielleicht das sein könnte, was du suchst. Die gibt an, welche Knoten von einem bestimmten Knoten aus direkt oder indirekt (über beliebig viele Sprünge) erreichbar sind.

[BUG]

Letztendlich ist halt wirklich die Frage, was du damit machen willst.

Wenn die Anzahl der Stationen klein ist oder die Eigenschaften der Verknüpfung günstig, dann macht es vielleicht wirklich Sinn, alle Pfade auszugeben. Bei mehr als ein paar dutzend Pfaden würde ich das aber bezweifeln.

Du könntest anstelle einzelnen Pfade auch einen Prefixbaum ausgeben, das würde die Sache dann deutlich übersichtlicher machen, in extremen Fällen würde es nicht helfen.

Es folgt: Werbung für theoretischere Informatik in der Industrie

Wenn du ein schönen Model suchst, um Abläufe mit komplexe Abhängigkeiten zu untersuchen, sind vielleicht Petri-Netze was für dich.
Je nach Ziel könntest du dich mit temporaler Logik auseinandersetzen, was Fragen erlaubt, die wie folgt aussehen: Kann es ein Werkstück geben, das Station 1 erreicht, nachdem es Station 2 in schlechter Qualität verlassen hat.
Bei kleineren Problem könnte man auch mit naiv implementierte Model-Checkern Spaß haben; für größere Probleme schadet etwas Rechenpower und eine clevere Implementierung nicht.

[Phoenix]

Die Hinweise auf den Zustandsautomaten waren ja schon ein Volltreffer.
Schau Dir mal an, wie die Windows Workflow Foundation das abbildet. Die können die Wege ja auch alle durchvalidieren und auch in einem Workflow-Designer darstellen.

WF ist leider nicht Teil der .NET Foundation und damit (noch?) nicht Open Source, aber mit dotPeek kann man da dennoch ziemlich gut reingucken