A spring embedder considers the nodes little metal rings in the plane that are connected by springs and that therefore repel or attract each other. A spring embedder works in iterations. In each iteration, the forces exerted on each node v are computed. Each incident edge (u,v) attracts the node v with the force f(u,v) in the direction of u, with f(u,v) being proportional to the difference from the distance of u and v and the length of the spring (“Hooke's Law”). Conversely, each leaving edge (v,u) repels the node v away from from u with the force f(v,u)=−f(u,v). After all forces have been summed up, the rings are moved in the plane according to the forces exerted on them. (By the force exerted on it, a ring is subject to a certain acceleration into a certain direction that is considered constant for a short period; the new position of the ring is the position at the end of this period.) Then the spring embedder steps into the next iteration. With a sufficiently large number of iterations, a state of equilibration is reached, in which the force exerted on each ring is 0.

Figure 5.30 shows a drawing of a graph before and after a spring embedding.

Figure 5.30. Spring embedding a graph

Before spring embedding.

After spring embedding.

Note

Strictly speaking, one distinguishes between drawings, embeddings and planar embeddings of a graph. A drawing is any way of drawing a graph onto a surface (such as a sheet of paper or the surface of a sphere). An embedding is a drawing with the additional property that no edges cross. A planar embedding is an embedding into the two-dimensional plane. Thus the term “spring embedder” is not fully justified, since in general, a spring embedder does not create a (planar) embedding, even if the graph to be drawn is planar. In the majority of cases, however, the result of a spring embedding is almost planar, that is, only a few edges cross in the drawing created, as we can see in Figure 5.30. Nevertheless, the name “spring drawer” would be more adequate.

The spring embedder embedded into LEDA can be used via the following function:

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

The meaning of the parameters is as follows: SPRING_EMBEDDING() computes new coordinates for the nodes in a total of iterations iterations. These coordinates originate from the rectangular [xleft,xright]×[ybottom,ytop]. The original coordinates of the nodes must be passed in the node arrays xpos and ypos; the function also stores the newly computed coordinates in these arrays.

To be able to use this function in a GraphWin, we first have to familiarize ourselves with some further concepts of the class GraphWin and its parent class window.

Each GraphWin (and each window, from which GraphWin is derived) has an underlying user coordinate system in which the x-coordinates increase from left to right, and the y-coordinates from bottom to top (the usual coordinate system in mathematics). This coordinate system is defined by three numbers of type double: xmin, the minimal x-coordinate, xmax, the maximal x-coordinate, and ymin, the minimal y-coordinate. These coordinates are mapped to the pixel coordinates of the window visible on the screen; this yields ymax, the maximal y-coordinate, and a scaling factor scale, which is used whenever user coordinates have to be converted to pixel coordinates in a drawing operation.

All drawing operations in a window use this user coordinate system to specify the coordinates that are necessary for the drawing. So the user never has to grapple with pixel positions! Until now, we have never made explicit use of this coordinate system, but we shall do so soon: We have to tell the function SPRING_EMBEDDING() into which rectangle it shall order the nodes. Then we have to move the nodes onto these newly computed positions.

The user coordinate system can be defined by the method init():

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

We have not made use of this method until now. If this call is left out, the user coordinate system results from the geometry of the window on the screen, see Exercise 70.

As the rectangle for SPRING_EMBEDDING() we simply choose the rectangle of the user coordinate system. The corner coordinates of the current user coordinate system can be queried with the methods xmin(), xmax(), ymin(), and ymax() of the class window. For the class GraphWin, there are the special methods get_xmin() etc., which take into consideration that additional status information is displayed at the lower margin of the drawing area of a GraphWin, so that the actual drawing area is a little smaller than the area of the overall window.

To query the original coordinates of a node v in the user coordinate system, we use the method

point p = gw.get_position(v);

which returns an object of class point. The two coordinates of this point can be queried with

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

With these methods, we can inform SPRING_EMBEDDING() about the current coordinates of the nodes in the user coordinate system.

After the spring embedder has computed the new coordinates, we have to move the nodes to these coordinates. This is done with a call

gw.set_position(xpos, ypos);

Here the two node arrays must contain numbers of type double.

The movement is shown with animation. The attribute animation_steps of the class GraphWin specifies how many discrete partial steps are inserted into the overall motion of nodes (and edges) from their start point to their end point. If this attribute has a value of 0, the movement is performed without partial steps, that is, immediately. The higher the value, the smoother (and the slower) the animation of the movement. The value of this attribute may be set by

gw.set_animation_steps(number_of_steps);

The following program presents the concepts just introduced. Figure 5.30 has been created with it.

#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);
  }
}

If a graph is planar, a planar embedding in which each edge is drawn as a line segment always can be found. Such an embedding is called a straight line embedding. Figure 5.31 shows a straight line embedding.

Figure 5.31. Straight line embedding of a graph

Before straight line embedding.

After straight line embedding.

LEDA offers a straight line embedder through the function

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

Here the graph G has to be planar. The function stores the integer coordinates of a straight line embedding in xc and yc, and returns the maximal coordinate computed.

The following program shows the usage of this function. What is new here is the method

gw.place_into_win();

of GraphWin. After the new (integer) coordinates of the nodes have been computed and set by means of set_position(), it is necessary to scale them such that they fit into the user coordinate system of the window visible on the screen, and then to transfer the nodes onto these scaled coordinates. This is achieved by 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();
  }  
}

Further information about the user coordinate system can be found on the manual page of the class window.

LEDA's different functions for graph drawing are described on the corresponding manual page.