Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

[Matze]

Hallo zusammen,

ich habe einen Fahrplan, durch den definiert ist, wo welche Teile in einer Produktion bearbeitet werden dürfen. Dafür werden Quell- und Zielstationen sowie eine Bedingung (nur Gutteile, nur Schlechtteile, ...) festgelegt.

Das sieht z.B. so aus (schematisch dargestellt):

Code:

class FahrplanEintrag
{
    int QuellStation; // -1 = Keine Vorgeschichte, d.h. ZielStation = Start-Station
    int ZielStation;
    int Bedingung;
}

List<FahrplanEintrag> Fahrplan = new List<FahrplanEintrag>()
{
    new FahrplanEintrag()
    {
        QuellStation = -1,
        ZielStation = 1,
        Bedingung = 0, // alle Teile
    },
    new FahrplanEintrag()
    {
        QuellStation = 1,
        ZielStation = 2,
        Bedingung = 1, // nur Gutteile
    },
    new FahrplanEintrag()
    {
        QuellStation = 1,
        ZielStation = 1,
        Bedingung = 2, // nur Schlechtteile (erneute Bearbeitung in Station 1 zulässig)
    },
    new FahrplanEintrag()
    {
        QuellStation = 2,
        ZielStation = 3,
        Bedingung = 1, // nur Gutteile
    },
    // ...
}

Das bedeutet für obiges Beispiel:

In der ZielStation 1 darf jedes Teil bearbeitet werden, das zuvor an keiner Station bearbeitet wurde oder in Station 1 war und schlecht bearbeitet wurde. Es beginnt also mit Station 1.
In Station 2 dürfen alle Teile bearbeitet werden, die zuvor in Station 1 waren und dort gut bearbeitet wurden. Waren die Teile in Station 2 gut, dürfen sie in Station 3 bearbeitet weerden.

Es kann mehrere Start-Stationen geben und mehrere Zielstationen.

Ein Teil dürfte auch z.B. wie folgt durchlaufen:

Code:

1 -> 2 -> 3 -> 4 -> 5 -> 6
      |               |
      |-> 7 ----------|

Das Teil darf also von Station 2 in Station 3 oder in Station 7 kommen.
Von 3 darf es nur in 4 und dann in 5 und dann in 6.
Geht das Teil von 2 nach 7, darf es von 7 nur in 6 weiterbearbeitet werden.

Es kann auch Fälle geben, in denen ein Teil, das in 6 schlecht wurde, wieder zurück nach 2 muss o.ä.

Es gibt also beliebige Verzweigungen und Zusammenführungen.

Anhand der obigen Definitionsliste (List<...>), in der die Einträge beliebig angeordnet sind, möchte ich nun alle möglichen Wege eines Teils bekommen.
Entweder mit einem Baum oder irgendwie anders. So, dass ich das auch visualisieren könnte.

Wie kann ich das denn machen?

Eine Start-Station ist für mich eine, in der die Quell-Station = -1 ist. D.h. damit muss ich vermutlich irgendwie beginnen (wie gesagt, es kann auch mehrere Start-Stationen geben).

Ich dachte evtl. an eine Struktur in der Art, aber vielleicht geht es auch schöner:

Code:

class EinzelneStation
{
    int AktuelleStation; // "Knoten" mit der Station, in der sich das Teil geared befindet
    List<EinzelneStation> NaechsteStationen; // Liste von "Knoten", zu denen das aktuelle Teil als nächstes darf
    List<int> RuecksprungStation; // im Falle, dass das Teil wieder zurück an vorige Stationen darf, steht hier die Nr., damit es keine "Endlosschleife" gibt
    int BedingungFuerBearbeitungsfreigabe;
}

List<EinzelStation> AlleMoeglichenWege

Evtl. mit Rekursion beginnend bei den Start-Staionen (Abbruchbedingungen sind: Rücksprung zu einer vorigen Station bzw. End-Station erreicht).

Ergebnis soll (wie auch immer) etwas in der Art sein, das mir alle möglichen Wege aufzeigt:

Code:

1 (Rücksprung: 1, Bedingung: Wenn Schlechtteil in 1)
2 (Bedingung: nur Gutteil)
3 (Bedingung: nur Gutteil)

ODER

1 (Rücksprung: 1, Bedingung: Wenn Schlechtteil in 1)
2 (Bedingung: nur Gutteil)
4 (Bedingung: nur Schlechtteil)

ODER

...

Konntet ihr's halbwegs nachvollziehen?

Ich möchte aus der Fahrplandefinition ermitteln, welche möglichen Wege ein Teil nehmen kann (mit den entsprechenden Bedingungen).

Grüße
Matze

[Perlsau]

Ob man das mit einer gewöhnlichen Baumstruktur (TTreeView) überhaupt darstellen kann? Sieht eher nach Ablaufplan aus ...

[BUG]

Zitat von Matze:

Es kann auch Fälle geben, in denen ein Teil, das in 6 schlecht wurde, wieder zurück nach 2 muss o.ä.

Wenn du Kreise drin hast, gibt natürlich ein Problem, wenn du alle Pfade ausgeben möchtest

Im Prinzip ist dein Plan ein nicht deterministischer Zustandsautomat, wobei das Tupel (Quell-Station, Teil-Art) der Zustand ist. Die Fahrplan-Einträge fügen dann eine (Gutteil/Schlechtteil) oder zwei Transitionen (alle Teile) hinzu.
Dieser Automat erkennt dann alle möglichen Wege für ein Teil.

[Matze]

Danke für die Antworten.

Zitat von BUG:

Wenn du Kreise drin hast, gibt natürlich ein Problem, wenn du alle Pfade ausgeben möchtest

Hehe jupp. Daher genügt mir hier die Angabe "Rücksprung nach Station x möglich", sodass keine "Kreise"/"Endlosschleifen" entstehen.

Zitat von BUG:

Im Prinzip ist dein Plan ein nicht deterministischer Zustandsautomat, wobei das Tupel (Quell-Station, Teil-Art) der Zustand ist.

Stimmt, laut Wikipedia ist es das, was hier vorliegt.
Hättest du mir dafür ein konkretes Programmierbeispiel für meinen Anwendungsfall?

@Perlsau: Ich brauche keinen TreeView dafür. Ich möchte eine Struktur haben, mit der ich das z.B. als Text o.ä. ausgeben kann. Jupp, so eine Art Ablaufplan wäre das, rein grafisch betrachtet. Mir geht's jedoch erstmal darum, dass ich in der Software die möglichen Wege kenne ohne das zu Visualisieren.

[jobo]

Da hat Perlsau glaub ich Recht.
Du hast ja schon einen Baum gezeichnet, der keiner ist.

Wozu dient das? Optische "Validierung" der Pläne?
Es gibt eine dll, graphwiz oder so, die ist glaub ich frei verfügbar und kann sowas wahrscheinlich malen. Ich hab die mal vor langer Zeit ausprobiert. Bin mir nicht sicher, aber die verarbeitet auch unterschiedliche Eingabeformate.

[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.

[BUG]

Wenn du die Kreise bloß erkennen willst, dann hast du es einfacher. Eine Breiten- oder Tiefensuche sollte ausreichen.

Breitensuche:
Du hast eine Menge von (unfertigen) Pfaden. In jedem Schritt erstellst du eine neue Menge, die alle Pfade enthält, die durch Herabhängen einer gültigen Folge-Station entstehen. Wenn du Kreise feststellst (den bisherigen Pfad durchgehen) oder ein Pfad das Ziel erreicht, wird er ausgegeben.

Tiefensuche:
Hänge an einen Pfad solange gültigen Folge-Station an, bis er entweder eine Zielstation erreicht oder eine schon besuchte Station erreicht. Dann gibst du den Pfad aus, gehst zurück zur letzten Entscheidung und probierst die nächste andere Abzweigung aus.

Das ist erstmal so aus dem Handgelenk, da kann man sicher noch was optimieren
Beachte, das du auch ohne Kreise exponentiell viele Pfade (in Anzahl der Stationen) bekommen kannst:

[Dejan Vu]

Um einen gerichteten Graphen darzustellen, gibt es derlei viele Möglichkeiten. Ich favorisiere zwei:

Adjacent Matrix: Eine AdjacentMatrix A einer Knotenmenge definiert die Pfade zwischen zwei Knoten. Bei N Knoten im Graph sind i und j zwei Knoten im Graphen. Dann bezeichnet A[i,j] einen Übergang i-> genau dann, wenn A[i,j] <> e ist. (e ist bei Dir z.B. -1) A[i,j] = 0 bedeutet, das alle Teile von i->j laufen können, =1 bedeutet, nur Gutteile usw.

Daneben benötigst Du noch eine Liste der Startpunkte und eine Liste der Endpunkte. Obwohl: Benötigen wirst Du sie nicht, denn es gilt: Ein Startknoten ist ein Knoten, der von keinem Knoten der Nachbar ist. Ein Endknoten ist ein Knoten, der keine Nachbarn hat.

Wenn Du sehr viele Knoten hast, wird die Matrix riesig, ist aber kaum gefüllt. Dann kann man das Speicherkonzept der sparse matrix verwenden.

Neighbors: Das ist eine Struktur, ähnlich deiner.

Code:

enum PathType
{
  All = 0,
  Good = 2,
  Bad = 3
}

interface IPath 
{
  PathType PathType{get;}
  INode Destination{get;}
}  

interface INode
{
  int ID{get;}
  IEnumerable<IPath> Neighbors {get;}
}

Wie man die Pfade bestimmt? Dazu hat BUG schon die Stichpunkte genannt. Hier mal C# (oder so ähnlich)

Code:

void FindAllPaths()
{
  foreach (var pathType pathType in typeof(PathType).GetValues())
  {
    foreach (var node in StartNodes)
    {
      Visit (pathType, new List<INode>(), node)
    }
  }
}

void Visit (PathType pathType, List<INode> path, node)
{
  if (visited[node]) return;
  visited[node] = true;
  path.Add(node);

  var matchingNeighbors = node.Neighbors.where (n=>n.PathType == pathType);
  if (!matchingNeighbors.Any())
  {
    OutputPath(path);
  }
  else
  {
    foreach (var singleStep in matchingNeighbors)
    {
      Visit(pathType, path, singleStep.Destination)
    }
  }

  path.Remove(node);
  visited[node] = false;
}

Dahingetippt, ohne Editor oder Compiler.

Die Idee ist das Markieren des besuchten Knotens ('Hier war ich schon') damit werden zirkuläre Pfade vermieden.

[Medium]

Ich würde hier zunächst einen kompletten Graphen aufbauen. Knotenklasse etwa so

Code:

public Station
{
  List<Station> NextStationsForGoodPart;
  List<Station> NextStationsForBadParts;
  String StationName;
}

Davon dann zunächst alle benötigten Instanzen erstellen, und von Hand den Graphen zusammenfriemeln. (Anders wird's ja nicht gehen.)
Dann alle Start-Stations in eine "List<Station> ValidEntryPoints" (Deine Quellstation -1 quasi, für den Fall dass es da mehrere gibt mal als Liste). Jetzt kannst du beginnend mit den Stationen in dieser Liste anfangen den Graphen für alle möglichen Wege zu traversieren. Während du das tust, führst du für jeden neu begonnenen Vorgang ab einem Entry-Point eine weitere "List<Station> VisitedStations" mit, und prüfst vor jeder Verzweigung ob der nächste Knoten in dieser Liste steht. Wenn ja, dann Rückverweis an den Stationsnamen, sonst nächste Station anspringen und die aktuelle in VisitedStations merken. Beim Traversieren musst du dann natürlich beide Wege (good und bad) ablaufen und entsprechend in der Ausgabe vermerken zu welchem Zweig der Schritt gehörte.
Ganz naiv gedacht das ganze, ich hoffe das klappt

[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.