Example ORTHO_EMBEDDING()

Let G=(V,E) be a planar graph. ORTHO_EMBEDDING() computes an orthogonal drawing where the edges around high-dregree nodes are drawn arbitrarily in a (relatively) small region.

We first generate a random planar graph G with 10 nodes and 20 edges and make connected. Afterwards we insert reversal edges for all edges in G and set the reversal information by Make_Bidirected(). Finally we compute a planar map for G. Then we define node_array<double> xpos, ypos for the x- and y-coordinates of the nodes and edge_array<list<double> > xbends, ybends for the bends on the edges. Using these parameters we call ORTHO_EMBEDDING() and delete the dummy edges again. 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_planar_graph(G,10,20);
  Make_Connected(G);

  list<edge> dummy_edges;
  Make_Bidirected(G,dummy_edges);
  G.make_planar_map();

  node_array<double> xpos(G), ypos(G);
  edge_array<list<double> > xbends(G), ybends(G);

  ORTHO_EMBEDDING(G,xpos,ypos,xbends,ybends);

  edge e; forall(e,dummy_edges) G.del_edge(e);

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

  gw.set_layout(xpos,ypos,xbends,ybends);
  gw.open(); gw.display();

  return 0;
}	   

See also:

Orthogonal Algorithms

Planar Maps

Node Arrays

Edge Arrays

Linear Lists

GraphWin

Graph Drawing Algorithms

Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Graph Drawing Algorithms