Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Panel
borderStyledashed
titleProject Overview
borderStyledashed

Responsible:

Related

Key Publications:

  • Christoph Daniel Schulze, Miro Spönemann, and Reinhard von Hanxleden. Drawing layered graphs with port constraints. Journal of Visual Languages and Computing, Special Issue on on Diagram Aesthetics and Layout, 25(2):89–106, 2014. The original publication is available at www.sciencedirect.com. (pdfbib)

Further Publications:

  • Miro Spönemann, Hauke Fuhrmann, Reinhard von Hanxleden, and Petra Mutzel. Port constraints in hierarchical layout of data flow diagrams. In Proceedings of the 17th International Symposium on Graph Drawing (GD’09), volume 5849 of LNCS, pages 135–146, Springer, 2010. The original publication is available at link.springer.com. (pdf / bib)
  • Lars Kristian Klauske, Christoph Daniel Schulze, Miro Spönemann, and Reinhard von Hanxleden. Improved layout for data flow diagrams with port constraints. In Proceedings of the 7th International Conference on Diagrammatic Representation and Inference (DIAGRAMS’12), volume 7352 of LNAI, pages 65–79, Springer, 2012. The original publication is available at link.springer.com. (pdfbib)
  • Miro Spönemann, Christoph Daniel Schulze, Ulf Rüegg, and Reinhard von Hanxleden. Drawing layered hypergraphs. Technical Report 1404, Christian-Albrechts-Universität zu Kiel, Department of Computer Science, April 2014. (pdf / bib)

Related Theses:

  • Miro Spönemann, On the automatic layout of data flow diagrams, March 2009 (pdf)
  • Philipp Döhring, Algorithmen zur Layerzuweisung, September 2010 (pdf)
  • Christoph Daniel Schulze, Optimizing automatic layout for data flow diagrams, July 2011 (pdf)
  • Insa Fuhrmann, Layout of compound graphs, February 2012 (pdf)
  • John Julian Carstens, Node and label placement in a layered layout algorithm, September 2012 (pdf)
  • Katja Petrat, Erweiterung und Implementierung eines Knotenplatzierungsalgorithmus, March 2014 (pdf)

KLay Layered is a layer-based layout algorithm mainly intended for diagrams with an inherent data flow direction. This page describes its general architecture, while child pages discuss the different phases, its intermediate processors, and other specialized topics.

...

Table of Contents
maxLevel2

Excerpt Include
Downloads - KIELER Layout Algorithms
Downloads - KIELER Layout Algorithms

Architecture

To get an idea of how KLay Layered is structured, take a look at the diagram below. The algorithm basically consists of four components: layout phases, intermediate processors, a connected components processor, and an interface to the outside world. Let's briefly look at what each component does before delving into the gritty details.

...

Intermediate processors are less prevalent. In fact, they are one of our contributions to the world of layout algorithms. The idea here is that we want KLay Layered to be as generic as possible, supporting different kinds of diagrams, laid out in different kinds of ways . (as long as the layout is based on layers). Thus, we are well motivated to keep the layout phases as simple as possible. To adapt the algorithm to different needs, we then introduced small processors between the main layout phases . (the space between two layout phases is called a slot) One . One processor can appear in different slots, and one slot can be occupied by more than one processor. Processors usually modify the graph to be laid out in ways that allow the main phases to solve problems they wouldn't solve otherwise. That's an abstract enough explanation for it to mean anything and nothing at once, so let's take a look at a short example.

The task of phase 2 is to produce a layering of the graph. The result is that each node is assigned to a layer in a way that edges always point to a node in a higher layer. However, later phases may require the layering to be proper.  (a layering is said to be proper if two nodes being connected by an edge are assigned to neighboring layers). Instead of modifying the layerer to check if a proper layering is needed, we introduced an intermediate processors processor that turns a layering into a proper layering. Phases that need a proper layering can then just indicate that they want that processor to be placed in one of the slots.

...

In KLay Layered, we make extensive use of dummy nodes to reduce complex and very specific problems such that we can solve them using our general phases. One example is how we have implemented support for ports our implementation of port support on the northern or southern side of a node.

...

  1. Using one of the IGraphImporter implementations, it imports the KGraph to be laid out into KLay Layered's LGraph format. Which implementation is used depends on whether the algorithm has to compute a layout for all hierarchy levels at one once (compound layout) or not.
  2. Since the algorithm's configuration depends on the graph to be laid out, the LayeredLayoutProvider now has to decide which ILayoutPhase implementations to use for each of the five layout phases (this is specified with the different phase strategy enumerations). Once that is decided, each ILayoutPhase is queried for an IntermediateProcessingConfiguration, which describes – using the LayoutProcessorStrategy – the ILayoutProcessors it needs in each of the intermediate processing slots. The outcome of this step is a list of ILayoutProcessor instances that constitute the concrete layout algorithm.
  3. Next, the imported graph is split into its connected components using the ComponentsProcessor. The processor does the work of splitting the graph into its connected components.
  4. The main step: executing the algorithm (the list of ILayoutProcessor instances, as you will certainly remember) on each connected component.
  5. With a layout computed for each connected component, the ComponentsProcessor is invoked again to join them together. The processor can use one of two implementations of the AbstractGraphPlacer class: SimpleRowGraphPlacer simply places the connected components in rows, trying to adhere to the required aspect ratio. The ComponentGroupGraphPlacer is more sophisticated and tries to work around problems with connected components processing in compound nodes.
  6. Finally, it again uses one of the IGraphImporter implementations to apply the computed layout back to the KGraph.

Example Layouts

Below some example diagrams that were layouted with the KLay Layered algorithm.

...

 

Ptolemy Diagram

Ptolemy DiagramImage Added

SCChart with Dataflow

Image Added

SCG

Image Added