Ein Spring Embedder sieht die Knoten als kleine Metallringe in der Ebene an, die durch Federn (engl. spring) miteinander verbunden sind und sich deshalb gegenseitig abstossen bzw. anziehen. Ein Spring Embedder arbeitet in Iterationen. In jeder Iteration werden für jeden Knoten v die auf ihn wirkenden Kräfte berechnet. Jede inzidente Kante (u,v) zieht ihn mit der Kraft f(u,v) in Richtung von u, wobei f(u,v) proportional zur Differenz aus dem Abstand von u und v und der Länge der Feder ist („Hooke'sches Gesetz“). Umgekehrt stösst ihn jede ausgehende Kante (v,u) mit der Kraft f(v,u)=−f(u,v) von u ab. Nachdem alle Kräfte summiert wurden, werden die Ringe gemäß den auf sie wirkenden Kräften in der Ebene bewegt. (Durch die auf ihn wirkende Kraft erfährt der Ring eine bestimmte Beschleunigung in eine bestimmte Richtung, die für einen kurzen Zeitraum als konstant angesehen wird; die neue Position des Ringes ist die Position am Ende dieses Zeitraums.) Danach geht der Spring Embedder in die nächste Iteration. Bei hinreichend großer Anzahl von Iterationen wird ein Gleichgewichtszustand erreicht, bei dem die auf jeden Ring wirkende Kraft 0 ist.

Abbildung 5.30 zeigt eine Zeichnung eines Graphen vor einem Spring Embedding und danach.

Abbildung 5.30. Spring Embedding eines Graphen

Vor dem Spring Embedding.

Nach dem Spring Embedding.

Anmerkung

Streng genommen unterscheidet man zwischen Zeichnungen, Einbettungen und planaren Einbettungen eines Graphen. Eine Zeichnung ist irgendeine Art und Weise, einen Graphen auf eine Oberfläche (wie z. B. ein Blatt Papier oder die Oberfläche einer Kugel) zu zeichnen. Eine Einbettung ist eine Zeichnung mit der zusätzlichen Eigenschaft, dass sich keine Kanten kreuzen. Eine planare Einbettung ist eine Einbettung in die zweidimensionale Ebene. Somit ist die Bezeichnung „Sping Embedder“ nicht ganz gerechtfertigt, da ein Spring Embedder i. Allg. keine (planare) Einbettung erzeugt, auch wenn der zu zeichnende Graph planar ist. Wie wir aber in Abbildung 5.30 sehen, ist das Ergebnis eines Spring Embeddings meistens nahezu planar, d. h. nur wenige Kanten schneiden sich in der erzeugten Zeichnung. Trotzdem wäre der Name „Spring Drawer“ angemessener.

LEDAs Spring Embedder verbirgt sich hinter der folgenden Funktion:

void SPRING_EMBEDDING(graph& G, 
                      node_array<double>& xpos, node_array<double>& ypos,
                      double xleft, double xright, 
                      double ybottom, double ytop, 
                      int iterations = 250);

Die Parameter sind wie folgt zu verstehen: SPRING_EMBEDDING() berechnet in insgesamt iterations Iterationen neue Koordinaten für die Knoten, die alle innerhalb des Rechteckes [xleft,xright]×[ybottom,ytop] liegen. Die ursprünglichen Koordinaten der Knoten müssen in den Knoten-Arrays xpos und ypos übergeben werden; dort legt die Funktion auch die neu berechneten Koordinaten wieder ab.

Um diese Funktion in einem GraphWin benutzen zu können, müssen wir erst einige weitere Konzepte der Klasse GraphWin und der Elternklasse window kennen lernen.

Jedem GraphWin (und jedem window, wovon GraphWin ja abgeleitet ist) liegt ein Benutzer-Koordinatensystem zugrunde, in dem die x-Koordinaten von links nach rechts, und die y-Koordinaten von unten nach oben anwachsen, das also die in der Mathematik übliche Orientierung besitzt. Dieses Koordinatensystem wird durch drei Zahlen vom Typ double definiert: xmin, die minimale x-Koordinate, xmax, die maximale x-Koordinate und ymin, die minimale y-Koordinate. Diese Koordinaten werden auf die Pixel-Koordinaten des am Bildschirm sichtbaren Fensters abgebildet; dadurch ergibt sich ymax, die maximale y-Koordinate, und ein Skalierungsfaktor scale, der immer dann benutzt wird, wenn (bei einer Zeichenoperation) Benutzer-Koordinaten in Pixel-Koordinaten umgerechnet werden müssen.

Alle Zeichenoperationen in einem window benutzen dieses Benutzer-Koordinatensystem, um die zur Zeichnung nötigen Koordinaten zu spezifizieren. Der Benutzer muss sich also nie mit Pixel-Positionen herumschlagen! Wir haben dieses Koordinatensystem bisher noch nie explizit benutzt, werden es aber gleich tun: Wir müssen der Funktion SPRING_EMBEDDING() mitteilen, in welches Rechteck sie die Knoten anordnen soll, und dann die Knoten auf diese neu berechneten Koordinaten verschieben.

Das Benutzer-Koordinatensystem kann durch die Methode init() festgelegt werden:

void W.init(double xmin, double xmax, double ymin);

Diese haben wir bisher ebenfalls nicht benutzt. Wird dieser Aufruf ausgelassen, so ergibt sich das Benutzer-Koordinatensystem durch die Geometrie des Fensters am Bildschirm, s. Übung 69.

Als Rechteck für SPRING_EMBEDDING() wählen wir einfach das Rechteck des Benutzer-Koordinatensystem. Mit den Methoden xmin(), xmax(), ymin() und ymax() der Klasse window können die Eckwerte des derzeitigen Benutzer-Koordinatensystems erfragt werden. Für die Klasse GraphWin gibt es die speziellen Methoden get_xmin() usw., die in Betracht ziehen, dass am unteren Rand der Zeichenfläche eines GraphWin zusätzliche Statusinformationen angezeigt werden, so dass die tatsächliche Zeichenfläche etwas kleiner ist als die des gesamten Fensters.

Um die ursprünglichen Koordinaten eines Knoten v im Benutzer-Koordinatensystem zu erfragen, benutzen wir die Methode

point p = gw.get_position(v);

die ein Objekt der Klasse point zurückliefert. Die beiden Koordinaten dieses Punktes können mit

double x = p.xcoord();
double y = p.ycoord();

abgefragt werden. Durch diese Methoden können wir SPRING_EMBEDDING() die augenblicklichen Koordinaten der Knoten im Benutzer-Koordinatensystem mitteilen.

Nachdem der Spring Embedder die neuen Koordinaten berechnet hat, müssen wir die Knoten an diese Koordinaten verschieben. Das geschieht durch einen Aufruf

gw.set_position(xpos, ypos);

Die beiden Knoten-Arrays müssen dabei Zahlen vom Typ double beinhalten.

Die Verschiebung wird dabei animiert gezeigt: Das Attribut animation_steps der Klasse GraphWin gibt an, wie viele diskrete Teilschritte in die Bewegung von Knoten (und Kanten) vom Start- zum Endpunkt eingefügt werden. Hat dieses Attribut den Wert 0, so geschieht die Bewegung ohne Teilschritte, d. h. unmittelbar. Je höher der Wert, desto glatter (und langsamer) wird die Animation der Bewegung. Der Wert dieses Attributs lässt sich durch

gw.set_animation_steps(number_of_steps);

einstellen.

Das folgende Programm stellt die soeben eingeführten Konzepte vor. Abbildung 5.30 wurde damit erzeugt.

#include <LEDA/graph_draw.h>
#include <LEDA/graph.h>
#include <LEDA/graphwin.h>
#include <LEDA/node_array.h>
#include <LEDA/point.h>

using leda::graph;
using leda::node;
using leda::node_array;
using leda::GraphWin;
using leda::window;
using leda::point;

int main()
{
  graph G;

  GraphWin gw(G, 500, 500, "Spring Embedding");
  gw.set_edge_width(2);
  gw.set_animation_steps(15);
  gw.display(window::center,window::center);
  
  while(gw.edit()) { 
  
    // get user coordinates of drawing area
    double xleft   = gw.get_xmin();
    double xright  = gw.get_xmax();
    double ybottom = gw.get_ymin();
    double ytop    = gw.get_ymax();

    // get user coordinates of nodes
    node_array<double> xpos(G);
    node_array<double> ypos(G);
    node v;
    forall_nodes(v,G) {
      point p = gw.get_position(v);
      xpos[v] = p.xcoord();
      ypos[v] = p.ycoord();
    }
    
    // number of iterations of spring embedding algorithm
    const int iterations = 1000;
    
    // compute embedding, starting with old embedding
    SPRING_EMBEDDING(G, xpos, ypos,
                     xleft, xright, ybottom, ytop,
                     iterations);
  
    // move nodes to new positions
    // to change layout instantly, set animations_steps to 0 
    gw.set_position(xpos, ypos);
  }
}

Ist ein Graph planar, so kann immer eine planare Einbettung gefunden werden, in der jede Kante als Geradensegment gezeichnet ist. Eine solche Einbettung heißt Straight Line Embedding. Abbildung 5.31 zeigt eine solche Einbettung.

Abbildung 5.31. Straight Line Embedding eines Graphen

Vor dem Straight Line Embedding.

Nach dem Straight Line Embedding.

LEDA bietet einen Straight Line Embedder durch die Funktion

int STRAIGHT_LINE_EMBEDDING(graph& G, 
                            node_array<int>& xc, node_array<int>& yc);

an. Der Graph G muss dabei planar sein. Die Funktion hinterlässt in xc und yc die ganzzahligen Koordinaten eines Straight Line Embeddings und gibt die maximale berechnete Koordinate zurück.

Das folgende Programm zeigt die Verwendung dieser Funktion. Neu daran ist die Methode

gw.place_into_win();

von GraphWin. Nachdem die neuen (ganzzahligen) Koordinaten der Knoten berechnet und mittels set_position() gesetzt wurden, ist es notwendig, diese so zu skalieren, dass sie in das Benutzer-Koordinatensystem des auf dem Bildschirm sichtbaren Fensters passen, und anschließend die Knoten auf diese skalierten Koordinaten zu transferieren. Dies leistet place_into_win().

#include <LEDA/graph_draw.h>
#include <LEDA/graph_misc.h>
#include <LEDA/graph.h>
#include <LEDA/graphwin.h>
#include <LEDA/node_array.h>

using leda::graph;
using leda::node;
using leda::node_array;
using leda::GraphWin;
using leda::window;

int main()
{
  graph G;

  GraphWin gw(G, 500, 500, "Straight Line Embedding");
  gw.set_node_label_type(leda::no_label);
  gw.set_node_width(15);
  gw.display(window::center,window::center);
  
  
  while(gw.edit()) { 

    if(!Is_Planar(G)) {
      gw.message("G is not planar. Click <done> and edit again.");
      gw.wait();
      gw.del_message();
      continue;
    }
    
    node_array<int> xc(G);
    node_array<int> yc(G);

    STRAIGHT_LINE_EMBEDDING(G, xc, yc);
    
    // set_position only accepts doubles, so we must copy xc and yc
    node_array<double> xpos(G);
    node_array<double> ypos(G);
    node v;
    forall_nodes(v, G) {
      xpos[v] = xc[v];
      ypos[v] = yc[v];
    }
    
    // do not animate the setting of the new positions
    gw.set_animation_steps(0);
    gw.set_position(xpos, ypos);

    // but animate the following place_into_win() very slowly
    gw.set_animation_steps(100);

    // scale and translate the layout so that it fits into the window
    gw.place_into_win();
  }  
}

Weitere Informationen zum Benutzer-Koordinatensystem finden sich auf der Manualseite der Klasse window.

Die verschiedenen Funktionen von LEDA zum Zeichnen von Graphen sind auf der entsprechenden Manualseite beschrieben.