AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Graphzeichnen

Ein Thema von sahimba · begonnen am 5. Jun 2013 · letzter Beitrag vom 6. Jun 2013
Antwort Antwort
sahimba

Registriert seit: 14. Nov 2011
Ort: Berlin, Hauptstadt der DDR
137 Beiträge
 
Delphi 10 Seattle Professional
 
#1

Graphzeichnen

  Alt 5. Jun 2013, 20:34
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
  Mit Zitat antworten Zitat
Benutzerbild von sx2008
sx2008

Registriert seit: 16. Feb 2008
Ort: Baden-Württemberg
2.332 Beiträge
 
Delphi 2007 Professional
 
#2

AW: Graphzeichnen

  Alt 5. Jun 2013, 22:08
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.
fork me on Github
  Mit Zitat antworten Zitat
sahimba

Registriert seit: 14. Nov 2011
Ort: Berlin, Hauptstadt der DDR
137 Beiträge
 
Delphi 10 Seattle Professional
 
#3

AW: Graphzeichnen

  Alt 5. Jun 2013, 22:27
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.
  Mit Zitat antworten Zitat
sahimba

Registriert seit: 14. Nov 2011
Ort: Berlin, Hauptstadt der DDR
137 Beiträge
 
Delphi 10 Seattle Professional
 
#4

AW: Graphzeichnen

  Alt 5. Jun 2013, 22:29
Schau mal die Beispiele an, da schlackerst du mit Ohren
Wow!
Das Ergebnis würde einen auch größeren Aufwand der Integration rechtfertigen.
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#5

AW: Graphzeichnen

  Alt 6. Jun 2013, 00:43
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....
Angehängte Dateien
Dateityp: zip graph_demo.zip (18,5 KB, 22x aufgerufen)

Geändert von jfheins ( 6. Jun 2013 um 00:48 Uhr)
  Mit Zitat antworten Zitat
sahimba

Registriert seit: 14. Nov 2011
Ort: Berlin, Hauptstadt der DDR
137 Beiträge
 
Delphi 10 Seattle Professional
 
#6

AW: Graphzeichnen

  Alt 6. Jun 2013, 08:02
Vielleicht kannst du damit ja etwas anfangen
Mehr als nur allerbesten Dank

Grüße,
S.
  Mit Zitat antworten Zitat
Antwort Antwort

 

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 08:16 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz