LEDA Guide: Example 2D Spring Embedding

Guide > Graph Algorithms > Graph Drawing Algorithms > Spring Embedding > Example 2D

Example 2D Spring Embedding

Let G=(V,E) be a graph. SPRING_EMBEDDING() computes a Spring Embedding of G. The following program shows how SPRING_EMBEDDING() can be used.

We first generate a random graph G with 40 nodes and 30 edges without antiparallel edges, selfloops, and parallel edges and make G connected. The reason is that the best results are obtained for sparse, tree-like graphs.

Then we define node_array<int> xpos, ypos for the x- and y- coordinates of the nodes.

We use GraphWin to visualize the result. We place the nodes of G randomly inside the GraphWin gw.

Large Screenshot of Example

This random layout together with the bounds xleft, xright, ybottom, ytop of the GraphWin ensures that the resulting spring embedder layout directly fits into gw. Using these parameters we call SPRING_EMBEDDING() and display the result.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/node_array.h>
#include <LEDA/graph/graph_draw.h>
#include <LEDA/graphics/graphwin.h>
#include <LEDA/core/random_source.h>

using namespace leda;

int main()
{
  graph G; 

  int n=40,m=30;

  bool no_antipara=true,loopfree=true, no_para=true;

  random_graph(G,n,m,no_antipara,loopfree,no_para);

  Make_Connected(G);

  node_array<double> xpos(G), ypos(G);

  GraphWin gw(G); 
  double xleft   = gw.get_xmin();
  double xright  = gw.get_xmax();
  double ybottom = gw.get_ymin();
  double ytop    = gw.get_ymax(); 
  int lower_bound=static_cast<int>(xleft);
  int upper_bound=static_cast<int>(xright);
  random_source S(lower_bound,upper_bound);
  int x; node v;
  forall_nodes(v,G) {S >> x;xpos[v]=x;}
  lower_bound=static_cast<int>(ybottom);
  upper_bound=static_cast<int>(ytop);
  S.set_range(lower_bound,upper_bound);
  int y; forall_nodes(v,G) {S >> y;ypos[v]=y;}

  SPRING_EMBEDDING(G,xpos,ypos,xleft,xright,ybottom,ytop);
  
  gw.set_node_color(red);
  gw.set_node_height(15);
  gw.set_node_width(15);
  gw.set_position(xpos,ypos);
  gw.open(); gw.display();

  return 0;
}

Example 2D Spring Embedding

See also: