Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

[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:
beispiel.png

[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