Graphzeichnen

[sahimba]

Hallo.

Bevor Mißverständnisse auftreten: ich suche keine Komponenten zum zeichnen oder ähnliches, sondern: http://de.wikipedia.org/wiki/Graphzeichnen
Im Grunde genommen habe ich auch gefunden, was ich suche: http://www.eclipse.org/gef/zest

"The Zest project also contains a graph layout package which can be used independently. [...]
The Zest graph layout package provides the following layout algorithms:
Spring Layout Algorithm
Tree Layout Algorithm
Radial Layout Algorithm
Grid Layout Algorithm"

Nun stellt sich mir die Frage, ob hier jemand den Code (nur die Layout Algorithmen!) bereits nach Delphi portiert hat und den Code zur Verfügung stellen kann, darf und möchte. Anderenfalls werde ich mich demnächst selber dran machen, darf ihn dann aber leider nicht weitergeben :?

Grüße,
sahimba

[sx2008]

Zitat:

Zitat von sahimba (Beitrag 1217586)

Im Grunde genommen habe ich auch gefunden, was ich suche: http://www.eclipse.org/gef/zest

Ich glaube nicht, dass das das Richtige für dich ist.
Zest ist Java entwickelt und kräftig mit Eclipse verbandelt.
Für Programmiersprachen die nicht auf der Java VM aufsetzen gibt es keine Möglichkeit die Bibliothek zu benützen.
Eine Umsetzung nach Delphi würde Monate dauern.

Alternativvorschlag:
Schau dir mal D3.js an.
Das ist eine sehr leistungsfähige Javascript (hax nix mit Java zu tun) Bibliothek die in jedem modernen Browser läuft.
Schau mal die Beispiele an, da schlackerst du mit Ohren.

Du könntest aus Delphi heraus HTML + Javascript Code erzeugen und als Datei abspeichern.
Diese Datei kann man z.B. per EMail verschicken und jeder kann sie anschauen.
Es sind auch interaktive Grafiken möglich.

Es ist bestimmt nicht so einfach, den richtigen Code aus Delphi zu erzeugen, aber wenn's funktioniert ist das Ergebnis hervorragend.

Vielleicht habe ich mit meiner Idee einige Leute hier angefixed, die Lust haben dir zu helfen.

[sahimba]

Zitat:

Zitat von sx2008 (Beitrag 1217595)

Zest ist Java entwickelt und kräftig mit Eclipse verbandelt.

Das Paket, welches die Layout Algorithmen implementiert (und nur um die Portierung dieser geht es mir) ist vollständig unabhängig von den anderen Paketen, welche ZEST bilden, als auch vollständig unabhängig von Eclipse. "The Zest project also contains a graph layout package which can be used independently.". Soweit ich beim browsen durch den Code sah, sind die Abhängigkeiten nur zur Klassen des Java-Kerns gegeben, vornehmlich Listen und Hashmaps.

Die anderen Links schaue ich mir dennoch an, Danke erst einmal.

[sahimba]

Zitat:

Zitat von sx2008 (Beitrag 1217595)

Schau mal die Beispiele an, da schlackerst du mit Ohren

Wow! :thumb:
Das Ergebnis würde einen auch größeren Aufwand der Integration rechtfertigen.

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

[sahimba]

Zitat:

Zitat von jfheins (Beitrag 1217608)

Vielleicht kannst du damit ja etwas anfangen :-)

Mehr als nur allerbesten Dank :)

Grüße,
S.