Grid Layouts ( GridLayout )

Definition

A grid layout gl of a graph G stores for each node of G an integer x- and y-coordinate and an integer width and height, and for each edge of G a list of bend points of type IPolyline.

A node at position (x, y) with width w and height h covers the rectangular region rect(v) defined by the two grid points (x, y) and (x + w, y + h). An edge e = (v, w) with bend point list p₁,..., p_k is represented by a polyline line(e) defined by the points p₁,..., p_k plus point p_v at the beginning if p₁$\notin$rect(v), and plus point p_w at the end if p_k$\notin$rect(w), where p_v and p_w are the positions of node v and w, respectively.

Class GridLayout provides also utility functions for measuring aesthetic criteria like area, total number of bends, or total edge length, and for removing unnecessary bends from integer polylines.

#include < AGD/GridLayout.h >

Creation

GridLayout	gl	creates an instance gl of type GridLayout initialized to the empty layout with no associated graph.
GridLayout	gl(const leda_graph& G)	creates an instance gl of type GridLayout initialized to a grid layout for graph G. Initially, all x- and y-coordinates are 0, all nodes have width and height 0, and all bend point lists are empty.
GridLayout	gl(const GridLayout& gl)	copy constructor.

Operations

void	gl.init_node_size(int w, int h)
		sets the width of all nodes to w and the height to h.
GridLayout &	gl = const GridLayout& gl1
		assign gl1 to gl.

a) Access operations

const leda_graph&	gl.get_graph()	returns the associated graph.
int&	gl.x(leda_node v)	returns a reference to the x-coordinate of node v.
int&	gl.y(leda_node v)	returns a reference to the y-coordinate of node v.
int	gl.width(leda_node v)	returns the width of node v.
void	gl.width(leda_node v, int width)
		sets the width of node v to width.
int	gl.height(leda_node v)	returns the height of node v.
void	gl.height(leda_node v, int height)
		sets the height of node v to height.
bool	gl.in_rect(IPoint ip, leda_node v)
		returns true iff ip $\in$ rect(v).
IPolyline&	gl.bends(leda_edge e)	returns a reference to the bend point list of edge e.
void	gl.get_line(leda_edge e, IPolyline& ipl)
		computes the whole line corresponding to edge e and returns it in ipl, i.e., the point connecting e at its source and target are appended (at the start or end, resp.) to the bend point list of e.
leda_node_map<int>&	gl.x()	returns a reference to the node map storing the x-coordinates of the nodes.
leda_node_map<int>&	gl.y()	returns a reference to the node map storing the y-coordinates of the nodes.
leda_edge_map<IPolyline>&	gl.bends()	returns a reference to the edge map storing the bend point lists of the edges.

b) Utility functions

IRect	gl.bounding_box()	returns a tight bounding box of the grid layout.
int	gl.area()	returns the area.
int	gl.number_of_bends()	returns the total number of bend points.
int	gl.total_manhattan_edge_length()
		returns the sum of the length of all edge segments using manhattan distance, that is, a segment (x1, y1),(x2, y2) has length | x2 - x1| + | y2 - y1|.
double	gl.total_edge_length()	returns the sum of the length of all edge segments using euclidean distance, that is, a segment (x1, y1),(x2, y2) has length $\sqrt{\Vert x_2-x_1\Vert^2+\Vert y_2-y_1\Vert^2}$.
IPolyline	gl.get_compact_bends(leda_edge e)
		returns the bend point list for edge e without unnecessary bends.
void	gl.compact_all_bends()	removes all unnecessary bends.
void	GridLayout::compact_bends(IPolyline& ip)
		removes unnecesary bends from integer polyline ip,

Implementation

All access operations take constant time, number_of_bends() takes time $\protectO$(m), total_edge_length() and total_manhattan_edge_length() take time $\protectO$(m + b), and bounding_box() and area() take time $\protectO$(n + m + b), where n is the number of nodes in G, m is the number of edges in G, and b is the total number of edge bends.