Implementation of Grid Layout Algorithms ( GridLayoutModuleImpl )

Baseclasses

Definition

The class GridLayoutModuleImpl< GRID_CONCEPT > represents a generic method for implementing grid layout algorithms. The template argument GRID_CONCEPT is the class which represents the used implementation concept. It is responsible for allocating the data structures used by the grid layout algorithm and for translating the grid layout computed by the algorithm into a layout or grid layout for the input graph. A class used as template argument GRID_CONCEPT must provide the following constructors:

GRID_CONCEPT(const graph &G,LayoutInterface &A)
	allocate data structures for graph G with layout interface A.
GRID_CONCEPT(const graph &G,face f,LayoutInterface &A)
	allocate data structures for planar map G with exterior face f and layout interface A.
GRID_CONCEPT(PlaneGraphCopy &PG,face f,LayoutInterface &A)
	allocate data structures for plane graph copy PG with exterior face f and layout interface A.
GRID_CONCEPT(const graph &G,GridLayout &gl)
	allocate data structures for graph G with grid layout gl.
GRID_CONCEPT(const graph &G,face f,GridLayout &gl)
	allocate data structures for planar map G with exterior face f and grid layout gl.
GRID_CONCEPT(PlaneGraphCopy &PG,face f,GridLayout &gl)
	allocate data structures for plane graph copy PG with exterior face f and grid layout gl.

These constructors correspond to call() and call_grid() methods inherited by LayoutModule and GridLayoutModule. If an exterior face f is passed, it may be nil indicating that the algorithm chooses an appropriate exterior face. Moreover, the following operations are required:

void get_node_grid_size(GridCoordinateMapper &gcm,const LayoutInterface &A)
	determines initial grid size of nodes, where gcm is the current grid coordinate mapper.
void get_node_grid_size(const GridLayout &gl)
	determines inital grid size of nodes. The input of the user is given by the node grid sizes in gl.
IRect get_bbox()
	returns the bounding box of the computed grid layout.
void update(GridCoordinateMapper &gcm,LayoutInterface &A)
	transforms the computed grid layout into a layout for the input graph, where gcm is the current grid coordinate mapper and A is a layout interface for the input graph.
void update(GridLayout &gl)
	transforms the computed grid layout into a grid layout gl for the input graph.
static void set_postcondition(list<AgdKey> &post)
	assigns the general postcondition to post, i.e., adds key::planar_map_callable to post if calls for planar maps (second and fifth constructor) are supported, and adds key::PlaneGraphCopy_callable to post if calls for PlaneGraphCopy's (third and sixth constructor) are supported.

GridLayoutModuleImpl< GRID_CONCEPT > implements all call() and call_grid() methods inherited by LayoutModule and GridLayoutModule. The computation of a grid layout (call_grid() methods) works as follows:

1. An object C of type GRID_CONCEPT is constructed using the constructor corresponding to the call_grid() parameter list.
2. The initial grid node sizes are determined by calling virtual method get_node_grid_size (C, gl).
3. The actual computation of the grid layout is performed by calling pure virtual method do_call(C).
4. The bounding box of the grid layout is determined by calling get_bbox() of C.
5. The computed grid layout is transformed into a grid layout for the input graph by calling update (gl) of C.

The following steps are preformed in order to compute a layout (call() methods):

1. An object C of type GRID_CONCEPT is constructed using the constructor corresponding to the call() parameter list.
2. The initial grid node sizes are determined by calling virtual method get_node_grid_size(C, A).
3. The actual computation of the grid layout is performed by calling pure virtual method do_call(C).
4. The bounding box of the grid layout is determined by calling get_bbox() of C.
5. The computed grid layout is transformed into a layout for the input graph by calling update (gcm, A) of C.

Thus, it is sufficient to implement do_call(C). All necessary transformations are performed by the grid implementation concept class. The methods get_node_grid_size() must be overriden if the standard implementation of GRID_CONCEPT is not suitable, e.g., if the algorithms assumes that each node is just one grid point (all nodes have width and height 0).

#include < AGD/GridLayoutModuleImpl.h >

Operations

GridLayoutModuleImpl< GRID_CONCEPT > implements the call() and call_grid() methods of its base classes. Furthermore, there are the following protected overridables:

void	L.do_call(GRID_CONCEPT& C)
		implements the algorithm.
void	L.get_node_grid_size(GRID_CONCEPT& C, const LayoutInterface& A)
		determines initial grid sizes of nodes. The default implementation calls C.get_node_grid_size() with the current grid coordinate mapper.
void	L.get_node_grid_size(GRID_CONCEPT& C, const GridLayout& gl)
		determines initial grid sizes of nodes. The grid sizes in gl represent the user's input. The default implementation calls C.get_node_grid_size() with gl.

Example

The following example presents a simplified version of the PlanarStraight algorithm. It requires as input a planar map and adds eventually new edges in order to make the graph biconnected. The output is a layout on the grid, where we assume that each node is represented by a single grid point. Therefore, we chose PlaneGraphCopyGridConcept as implementation concept class.

#include <AGD/GridLayoutModuleImpl.h>
#include <AGD/PlaneGraphCopyGridConcept.h>
#include <AGD/AGDModuleOption.h>
#include <AGD/AugmentationModule.h>

class PlanarStraightLayout : public GridLayoutModuleImpl<PlaneGraphCopyGridConcept> {
public:
  PlanarStraightLayout ();
  ~PlanarStraightLayout() { }

  bool size_opt() const {
    return _size_opt;
  }

  void size_opt (bool so) {
    _size_opt = so;
  }

  AGDModule *clone () const;
  AGD_DECLARE_MODULE (AugmentationModule, augmenter)

protected:
  void get_node_grid_size (PlaneGraphCopyGridConcept &C, const LayoutInterface &A) { }
  void get_node_grid_size (PlaneGraphCopyGridConcept &C, const GridLayout &gl) {
    C.set_zero_size();
  }

  void do_call (PlaneGraphCopyGridConcept &C);

private:
  bool _size_opt;
};

PlanarStraightLayout declares one optional parameter size_opt and one module option augmenter. The get_node_grid_size() methods are overridden such that the size of each node is initially a single grid point. The constructor declares the pre- and postcondition and initializes size_opt and augmenter:

#include <AGD/PlanarStraightLayout.h>
#include <AGD/PlaneGraphCopy.h>
#include <AGD/PlanAug.h>

PlanarStraightLayout::PlanarStraightLayout () : _size_opt(true)
{
  add_precondition (key::planar);
  add_precondition (key::simple);
  add_precondition (key::no_self_loops);

  add_post_rule (key::straight_line);
  add_post_rule (key::no_crossings);

  PreCond  PRE;
  PostCond POST;
  PRE [1] << key::planar << key::simple << key::no_self_loops
    << key::directed;
  POST[1] << key::planar << key::biconnected << key::simple
    << key::no_self_loops;
  augmenter.init (PRE,POST,PlanAug());
}

The clone() method returns a new object of type PlanarStraightLayout with identical options:

AGDModule *PlanarStraightLayout::clone() const
{
  PlanarStraightLayout *M = new PlanarStraightLayout;

  M->size_opt (size_opt());

  M->set_augmenter (augmenter.get());
  M->set_mapper (mapper.get());

  return M;
}

The actual computation is done by the do_call() method. Of course, we omit here the complete code of PlanarStraightLayout::do_call(). The example simply demonstrates, how the graph and the grid layout are accessed via PlaneGraphCopyGridConcept.

void PlanarStraightLayout::do_call (PlaneGraphCopyGridConcept &C)
{
  PlaneGraphCopy &G  = C.get_graph ();
  GridLayout     &gl = C.get_layout();

  ...
}