Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

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