Wiki source code of KLay Layered
Version 5.1 by uru on 2015/04/17 19:15
Show last authors
| author | version | line-number | content |
|---|---|---|---|
| 1 | In this tutorial you'll learn about the structure and philosophie in our main layout algorithm [[doc:KIELER.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. | ||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | = The Five Phases = | ||
| 6 | |||
| 7 | explain | ||
| 8 | |||
| 9 | = KLay Layered's Structure = | ||
| 10 | |||
| 11 | class diagram? | ||
| 12 | |||
| 13 | Intermediate processor | ||
| 14 | |||
| 15 | |||
| 16 | |||
| 17 | = Preliminaries = | ||
| 18 | |||
| 19 | [[doc:Installing Eclipse for Layout Development]] | ||
| 20 | |||
| 21 | {{excerpt-include/}} | ||
| 22 | |||
| 23 | == Getting the Source Code == | ||
| 24 | |||
| 25 | 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. | ||
| 26 | |||
| 27 | 1. Clone the [[repository>>url:http://git.rtsys.informatik.uni-kiel.de/projects/KIELER/repos/pragmatics/browse||shape="rect"]]. | ||
| 28 | 1. Import the {{code language="none"}}de.cau.cs.kieler.klay.layered{{/code}} plugin into your workspace. | ||
| 29 | |||
| 30 | |||
| 31 | |||
| 32 | = Assignment = | ||
| 33 | |||
| 34 | The goal of this assignment is to write a very simple layering algorithm. As you learnt earlier, classically the layering phase expects the input graph to be acyclic. Here however, you will configure the layout algorithm to use a {{code language="none"}}NullPhase{{/code}} 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. | ||
| 35 | |||
| 36 | {{panel title="Assignment (1)"}} | ||
| 37 | Write an intermediate processor that takes a //layered// graph as input and reverses edges such that the output graph is acyclic. Here are some hints. | ||
| 38 | |||
| 39 | The {{code language="none"}}LEdge{{/code}} offers a method {{code language="none"}}reverseEdge{{/code}} that does most of the job for you and marks the edge. The {{code language="none"}}ReversedEdgeRestorer {{/code}}will take care of 'back'-reversing such edges at the end of the algorithm. Your class should extend the {{code language="none"}}ILayoutProcessor{{/code}} interface. | ||
| 40 | |||
| 41 | {{code linenumbers="true" language="java"}} | ||
| 42 | public class EdgeDirectionEnforcer implements ILayoutProcessor { | ||
| 43 | @Override | ||
| 44 | public void process(final LGraph layeredGraph, final IKielerProgressMonitor progressMonitor) { | ||
| 45 | // for all edges ... | ||
| 46 | if (...) { | ||
| 47 | edge.reverse(layeredGraph, true); | ||
| 48 | } | ||
| 49 | } | ||
| 50 | } | ||
| 51 | {{/code}} | ||
| 52 | {{/panel}} | ||
| 53 | |||
| 54 | {{panel title="Assignment (2)"}} | ||
| 55 | 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. | ||
| 56 | |||
| 57 | The intermediate processing configuration has to include your previously created intermediate processor as well as the mentioned edge reverser. | ||
| 58 | |||
| 59 | Take care not to place two nodes in the same layer if they are connected by an edge. | ||
| 60 | |||
| 61 | {{code linenumbers="true" language="java"}} | ||
| 62 | public class RandomLayerer implements ILayoutPhase { | ||
| 63 | @Override | ||
| 64 | public IntermediateProcessingConfiguration getIntermediateProcessingConfiguration(final LGraph graph) { | ||
| 65 | return IntermediateProcessingConfiguration.createEmpty() | ||
| 66 | [ ... ] // add your desired configuration here | ||
| 67 | ; | ||
| 68 | } | ||
| 69 | |||
| 70 | @Override | ||
| 71 | public void process(final LGraph layeredGraph, final IKielerProgressMonitor progressMonitor) { | ||
| 72 | [ ... ] | ||
| 73 | } | ||
| 74 | } | ||
| 75 | {{/code}} | ||
| 76 | {{/panel}} |