Two Layer Crossing Minimization ( TwoLayerCrossMin )

Baseclasses

Definition

Modules of type TwoLayerCrossMin perform a two layer crossing minimization in a node hierarchy H, that is, the nodes of a graph G on a layer L, called the changeable layer, are reordered according to a neighbored layer of L, called the fixed layer, in order to reduce the number of edge crossings between these two layers.

These modules can be used in a process, which iteratively performs two layer crossing minimization between two neighbored layers in order to reduce the total number of edge crossings in the hierarchy. For efficiency reasons, the class TwoLayerCrossMin contains two notification methods init() and cleanup(). A user must first call the init() method with the graph G and the node hierarchy H. Then, the call() method can be called several times with layers belonging to H. Finally, the cleanup() method should be called to free resources.

Input and Output Parameters

input parameters:	hierarchy	in_hierarchy=1
	layer	in_layer=2
output parameter:	layer	out_layer=1

The integer constants in_hierarchy, in_layer and out_layer denote the positions in the input and output parameter lists. The values can be used to reference the desired parameter when setting the pre- and postcondition.

Implementing Two Layer Crossing Minimization Modules

An implementation of a two layer crossing minimization module must override the method call(G,L), which gets as input a graph G and a layer L. The class Layer provides methods to access the fixed and changeable layer, and to manipulate the order of the nodes on the changeable layer. The method init(G,H) can be overridden to allocate or initialize internal data structures, and the method cleanup() can be overridden to free resources allocated by init().

#include < AGD/TwoLayerCrossMin.h >

Initialization

TwoLayerCrossMin

M

initializes a two layer crossing minimization module.

Operations

Standard Interface

bool	M.check(const leda_graph& G, const Layer& L, AgdKey& p)
		returns true if G satisfies the precondition of M. Otherwise, false is returned and p contains a property that is not satisfied.
void	M.init(const leda_graph& G, const Hierarchy& H)
		must be called before the crossing minimization. Can be used by derived classes in order to allocate and initialize data structures.
void	M.call(const leda_graph& G, Layer& L)
		implements the module call for graph G. Reorders the nodes on layer L.
void	M.cleanup()	must be called after the crossing minimization. Can be used by derived classes in order to free resources allocated by init().

Example

We perform one top-down traversal of the crossing minimization method used in the Sugiyama algorithm. First, we build a hierarchy of our input graph G. Then, we initialize the two layer crossing minimization module minimizer. We must tell the hierarchy the direction of the crossing minimization (in this case downward), and the current changeable layer. This determines also the fixed layer (in this case i - 1). We call the two layer crossing minimization for all but the first layer. Finally, we must call cleanup() of minimizer in order to free resources.

#include <AGD/TwoLayerCrossMin.h>
#include <AGD/LongestPathRanking.h>
#include <AGD/Hierarchy.h>
#include <AGD/GraphCopy.h>

void minimize_top_down(graph &G, TwoLayerCrossMin &minimizer)
{
  node_array<int> rank(G);

  // assign a non-negative level to each node in G
  LongestPathRanking().call(G,rank);

  // build the hierarchy
  GraphCopy GC(G);
  Hierarchy H(GC,rank);

  // initialize crossing minimization
  minimizer.init(GC,H);

  // perform one top-down traversal
  H.direction(Hierarchy::downward);
  for (int i = 1; i < H.number_of_layers(); i++) {
    H.set_changeable_layer(i);
    minimizer.call(G,H[i]);
  }

  // free resources
  minimizer.cleanup();
}