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
.
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.
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 twodimensional 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 xcoordinates increase from left to
right, and the ycoordinates from bottom to top (the usual
coordinate system in mathematics). This coordinate system is
defined by three numbers of type double
:
xmin
, the minimal xcoordinate,
xmax
, the maximal xcoordinate, and
ymin
, the minimal ycoordinate. These
coordinates are mapped to the pixel coordinates of the window
visible on the screen; this yields ymax
,
the maximal ycoordinate, 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.
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.
Exercise 70.  The methods

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 nonplanar graphs, the algorithm often computes quite concise drawings. The LEDA function bool TUTTE_EMBEDDING(graph G, list<node> fixed_nodes, node_array<double>& xpos, node_array<double>& ypos);
creates a Tutte embedding for Write a program that allows to enter a graph in a
GraphWin and then to visualize the result of a call of
