### 5.3.8. Algorithms for graph drawing

Learning objectives

 Algorithms from `graph_draw.h` Spring embedding Straight line embedding The user coordinate system of `window` and `GraphWin` Animations in `GraphWin`

A crucial point when dealing with graphs is how to visualize them. As a rule, one and the same graph allows both “good” and “bad” drawings. Good drawings are concise, bad ones are not, because, for example, great many edges cross, which may confuse the observer a lot.

There are several approaches for graph drawing, which differ considerably by their methodology. We shall present two of them here: spring embedding and straight line embedding. LEDA offers these and other good algorithms for drawing graphs via functions declared in the header file `graph_draw.h`.

#### Spring Embedding

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.

Filename: SpringEmbedding.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
```#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);
}
}
```

#### Straight line embedding

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()`.

Filename: StraightLineEmbedding.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
```#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

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.

#### Exercises

 Exercise 70. The methods `get_xmin()`, `get_xmax()`, `get_ymin()`, and `get_ymax()` of class `GraphWin` can be used to query the corner values of the current user coordinate system. Create a GraphWin like until now, without explicitly setting the coordinate system with `init()`, then output the corner values, which then are defined implicitly, and interpret them. Exercise 71. A Tutte embedder creates drawings such as the one from Figure 5.32 by interpreting each node as a mass point and trying to position it into the center of gravity of its adjacent points. For planar graphs, this algorithm creates planar embeddings; the faces created in doing so are convex. Also for non-planar graphs, the algorithm often computes quite concise drawings. Figure 5.32. A Tutte embedding of a graph The LEDA function ```bool TUTTE_EMBEDDING(graph G, list fixed_nodes, node_array& xpos, node_array& ypos);``` creates a Tutte embedding for `G` whose faces all are convex. If the latter is not possible, it returns `false`. `fixed_nodes` must hold a list of nodes whose position is already fixed in the embedding; the coordinates of these points must be stored in `xpos` and `ypos`. (For example, the nodes 0-5 have been fixed in Figure 5.32.) The function stores the coordinates of the embedding in `xpos` and `ypos`.Write a program that allows to enter a graph in a GraphWin and then to visualize the result of a call of `TUTTE_EMBEDDING()`. The fixed nodes can be identified with `gw.get_selected_nodes()`, for example.