Example SP_EMBEDDING()

Let G=(V,E) be a series parallel graph. SP_EMBEDDING() computes a series parallel embedding of G. We first generate a random series parallel graph G with 10 nodes and 20 edges.

Then we define node_array<double> xpos, ypos for the x- and y-coordinates of the nodes, node_array<double> xrad, yrad for the size of the nodes, edge_array<list<double> > xbends, ybends for the bends on the edges, and edge_array<double> xsanch, ysanch, xtanch, ytanch for the position the edges touch their source and target node. Using these parameters we call SP_EMBEDDING(). If a drawing could be computed, we use GraphWin to visualize the result.

Large Screenshot of Example

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

using namespace leda;

int main()
{ 
  graph G; 

  random_sp_graph(G,10,20);

  node_array<double> xpos(G), ypos(G);
  node_array<double> xrad(G), yrad(G);
  edge_array<list<double> > xbends(G), ybends(G);
  edge_array<double> xsanch(G), ysanch(G);
  edge_array<double> xtanch(G), ytanch(G);

  bool feasible=
  SP_EMBEDDING(G,xpos,ypos,xrad,yrad,
               xbends,ybends,xsanch,ysanch,xtanch,ytanch);

  if (feasible) {
    GraphWin gw(G);
    gw.set_node_shape(rectangle_node);
    gw.set_node_color(red);

    double dx,dy,f;
    gw.fill_win_params(xpos,ypos,xbends,ybends,dx,dy,f,f);
    gw.transform_layout(xpos,ypos,xbends,ybends,dx,dy,f,f);

    node v;
    forall_nodes(v,G) {xrad[v] *= f;yrad[v] *= f;}

    gw.set_layout(xpos,ypos,xrad,yrad,
    xbends,ybends,xsanch,ysanch,xtanch,ytanch);
    gw.open(); gw.display();
  }

  else std::cout << "No corresponding embedding possible!" << std::endl;
  
  return 0;
}  

See also:

Algorithms for Series Parallel Graphs

Node Arrays

Edge Arrays

Linear Lists

GraphWin

Graph Drawing Algorithms

Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Graph Drawing Algorithms