Diagrams and Layout - KLay Layered

Page / - last modified by uru on 2015/04/20 21:31

KLay Layered

last modified by uru

on 2015/04/20 21:31

Table of Contents

Preliminaries

Getting the Source Code

Getting to Know KLay Layered

Assignment

In this tutorial you'll learn about the structure and philosophy in our main layout algorithm KLay Layered. It is based on an idea that became known as Sugiyama-style layout, where the task to layout a graph is split into multiple subsequent steps with the goal to emphasize direction, i.e. let as many edges point into the same direction as possible.

Preliminaries

Installing Eclipse for Layout Development

Getting the Source Code

Additionally, we need to get our hands on the actual source code of KLay Layered. You can find it in the pragmatics repository in our Stash.

Clone the repository.

Import the de.cau.cs.kieler.klay.layered plugin into your workspace.

Getting to Know KLay Layered

Familiarize yourself with the general idea and architecture of the layout algorithm by reading its documentation. You should know about terms like dummy nodes, intermediate processors, and phases.

With this knowledge, browse the code and try to identify the packages and classes that relate to the phases of KLay Layered.

Understand the differences between the KGraph and LGraph and explore how to use the LGraph. As noted in KLay Layered's documentation the LGraph is a lightweight version that is specifically tailored to serve as a data structure for layer-based layout. The following class diagram contains just about all the information you require for the assignment.

Assignment

The goal of this assignment is to write a very simple layering algorithm. As you probably already know, classically the layering phase (phase 2) expects the input graph to be acyclic. Here however, you will:

Configure the layout algorithm to use a NullPhase for cycle breaking,

Layer the possibly cyclic graph in a fashion as you like, and

Use an intermediate processor to reverse edges (if required) such that subsequent phases are guaranteed to work with an acyclic graph.

Don't hesitate to switch between the tasks and don't be afraid of exceptions or errors during debugging. When you use your layering phase without the intermediate processors the rest of KLay Layered will most likely complain (for cyclic input graphs). In other words, the following two assignments only work combined and not alone.

Assignment (a)
Create a layout phase called

NullPhase

that does nothing and can be used as a cycle breaking strategy. Hint: It has to implement the

ILayoutPhase

interface and has to be added to the

CycleBreakingStrategy

enumeration.

Assignment (b)

Write an intermediate processor that takes a layered graph (i.e. the result of assigment 2) as input and reverses edges such that the output graph is acyclic. Here are some hints.

The LEdge offers a method reverseEdge that does parts of the job for you and marks the edge such that the ReversedEdgeRestorer will take care of 'back'-reversing the edge at the end of the algorithm. Your class should extend the ILayoutProcessor interface.

public class EdgeDirectionEnforcer implements ILayoutProcessor {
@Override
public void process(final LGraph layeredGraph, final IKielerProgressMonitor progressMonitor) {
// for all edges ...
if (...) {
edge.reverse(layeredGraph, true);
}
}
}

Assignment (c)

Write a layer assignment algorithm that assigns nodes of a possibly cyclic input graph to layers. The only requirement is that you don't assign layers randomly.

The intermediate processing configuration has to include your previously created intermediate processor as well as the existing ReversedEdgeRestorer. The IntermediateProcessorStrategy can help you to find the phase after which to execute the ReversedEdgeRestorer.

Take care not to place two nodes in the same layer if they are connected by an edge.

public class RandomLayerer implements ILayoutPhase {
@Override
public IntermediateProcessingConfiguration getIntermediateProcessingConfiguration(final LGraph graph) {
return IntermediateProcessingConfiguration.createEmpty()
[ ... ] // add your desired configuration here
;
}
@Override
public void process(final LGraph layeredGraph, final IKielerProgressMonitor progressMonitor) {
[ ... ]
}
}

Use node.setLayer(layerX); to add assign a layer to a node. Internally, the node will be added to the layer's list of nodes.

Don't forget to let the switch statements in the LayeringStrategy and IntermediateProcessorStrategy enumerations know about the new classes.

The layout options you definitely need are de.cau.cs.kieler.klay.layered.cycleBreaking and de.cau.cs.kieler.klay.layered.nodePlace.

A result might look like this. The default strategies of KLay Layered try to achieve short edges and a low number of reversed edges. The left screenshot shows the result of a random layerer and is obviously inferior to the result seen in the right screenshot.