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

See also:

Spring Embedding

Node Arrays

GraphWin

Graph Drawing Algorithms

Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Graph Drawing Algorithms