Example ORTHO_DRAW()

Let G=(V,E) be a planar graph. ORTHO_DRAW() computes an orthogonal drawing where the high-dregree nodes are made bigger in order to draw the incident edges horizontally and vertically. 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, 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 ORTHO_EMBEDDING() and delete the dummy edges again. 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/corlist.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);
  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=ORTHO_DRAW(G,xpos,ypos,xrad,yrad,xbends,ybends,
                           xsanch,ysanch,xtanch,ytanch);

  if (feasible) {
    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);

    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:

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