LEDA Guide: Example Visibility Representation

Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Graph Drawing Algorithms > Visibility Representation > Example

Example Visibility Representation

Let G=(V,E) be a planar graph without self loops. VISIBILITY_REPRESENTATION() computes a visibility representation of G in time O(|V|).

The following program shows how VISIBILITY_REPRESENTATION() can be used.

We first generate a random planar graph G with 10 nodes and 20 edges.

Then we define node_array<int> xcoord, ycoord for the x- and y- coordinates and node_array<int> xrad, yradfor the width and height of the nodes. For the edges we define edge_array<int> xsanch, ysanch, xtanch, ytanch. They define the position at which the edge touches its source and target node.

Large Screenshot of Example

Using these parameters we call VISIBILITY_REPRESENTATION(). The function returns false if it could not compute a visibility representation and true otherwise.

We use GraphWin to visualize the result. To do this we need to transform the integer coordinates into appropriate GraphWin coordinates.

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

using namespace leda;

int main()
{
  graph G;
  random_planar_graph(G,10,20);
 
  node_array<double> xpos(G), ypos(G);
  node_array<double> xrad(G), yrad(G);
  edge_array<double> xsanch(G), ysanch(G);
  edge_array<double> xtanch(G), ytanch(G);

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

  if (feasible) {
    GraphWin gw(G);
    gw.set_node_shape(rectangle_node);
    gw.set_node_color(red);
 
    edge_array<list<double> > xbends(G), ybends(G);
    double dx,dy,f;
    gw.fill_win_params(xpos,ypos,xrad,yrad,xbends,ybends,dx,dy,f,f);
    gw.transform_layout(xpos,ypos,xrad,yrad,xbends,ybends,dx,dy,f,f);
    gw.set_layout(xpos,ypos,xrad,yrad,xbends,ybends,
                  xsanch,ysanch,xtanch,ytanch);
    gw.open(); gw.display();
  }
  
  return 0;
}

Example Visibility Representation

See also: