Graphzeichnen

[jfheins]

Ich habe sowas auch mal in C# programmiert, das geht eigentlich ohne großen Aufwand straightforward.

In den Kanten hatte ich eine "Step" Methode, die die angrenzenden Knoten versetzt hat (.Delta) je nach "Federkraft":

Code:

// Federkraft wirkt auf die Knoten
internal void Step(float factor, float length)
{
   var dx = TargetNode.Position.X - SourceNode.Position.X;
   var dy = TargetNode.Position.Y - SourceNode.Position.Y;
   Vector distance = new Vector(dx, dy);
   double force = (distance.Length - length * Cost) * factor;
   distance.Normalize();

   SourceNode.Delta += distance * force;
   TargetNode.Delta -= distance * force;
}

In den Knoten dann das quadratische Abstoßungsgesetz:

Code:

// Abstoßung der Knoten nach dem Coulomb-Gesetz
internal void Step(Node other, float factor)
{
   double dx = other.Position.X - Position.X;
   double dy = other.Position.Y - Position.Y;

   if (dx == 0 && dy == 0) // Wenn 2 Knoten exakt die gleiche Position haben kommt es sonst zu einem Fehler
      dx = 1;

   Vector distance = new Vector(dx, dy);
   double force = factor / distance.LengthSquared; // F = k * r^-2
   distance.Normalize();

   Delta -= distance * force;
   other.Delta += distance * force;
}

Und wenn du bis hierher gleesen hast: Jetzt kommt der interessante Teil. Nach meine damaligen Einschätzung hat sich der Graph nämlich noch sehr oft "verhakt" und ist quasi in lokalen Energieminima stecken geblieben. Knoten die eigentlich nach außen gelegt werden konnten, kamen nicht über die Barriere hinaus, die von dern anderen Knoten gebildet wurde. Deshalb habe ich eine angepasste Version entwickelt, die zuerst die Knotenabstoßungen übermächtig macht und den Graphen demzufolge komplett "aufbläht". Die Knoten können sich dann passend auseinanderfriemeln. Die Kräfte lassen dann mit einer Parabelfunktion stark nach und werden schließlich gleich den eingestellten Kräften. Schaut dann so aus:

Code:

public void AutoLayout(float NodeForcefactor, float EdgeForgeFactor, float EdgeRelaxedLength)
{
   const int loops = 800; // Layout-Iterationen
   const int nf_elev = 300; // Erhöhungsfaktor für die Knotenkräfte am Anfang

   for (int i = 0; i < loops; i++)
   {
      foreach (var edge in Edges)
      {
         edge.Step(EdgeForgeFactor, EdgeRelaxedLength); // Federkräfte auf die Knoten wirken lassen
      }
                // Die Knoten abstoßen lassen
      for (int a = 0; a < Nodes.Count(); a++)
      {
         for (int b = a + 1; b < Nodes.Count(); b++)
         {
            float x = 1 - (float)i / loops;
            Nodes[a].Step(Nodes[b], NodeForcefactor * (1 + x * x * nf_elev));
         }
      }
      foreach (var node in Nodes)
      {
         node.Layout(); // Anhand der Vektorsumme der Kräfte jeden Knoten passend verschieben.
      }
   }
}

Vielleicht kannst du damit ja etwas anfangen
Die Ergebnisse des Auto-Layouts kannst du im Anhang betrachten. Du kannst ein paar Sachen im Kontextmenü machen wenn du auf Knoten/Kanten klickst. Mit Bearbeiten kannst du rechts auch die Kosten verändern, falls du nicht alle Kanten gleich lang haben möchtest....