Changes for page KLay Layered

Last modified by Richard Kreissig on 2023/09/14 09:07
<
From version < 13.1 >
edited by uru
on 2015/04/22 12:17
To version < 4.1 >
edited by uru
on 2015/04/17 18:29
>
Change comment: There is no comment for this version

Summary

Details

Page properties
Content
... ... @@ -1,5 +1,19 @@
1 -In this tutorial you'll learn about the structure and philosophy 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.
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 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 +
3 3  = Preliminaries =
4 4  
5 5  [[doc:Installing Eclipse for Layout Development]]
... ... @@ -13,99 +13,26 @@
13 13  1. Clone the [[repository>>url:http://git.rtsys.informatik.uni-kiel.de/projects/KIELER/repos/pragmatics/browse||shape="rect"]].
14 14  1. Import the {{code language="none"}}de.cau.cs.kieler.klay.layered{{/code}} plugin into your workspace.
15 15  
16 -= Getting to Know KLay Layered =
30 +
17 17  
18 -1. Familiarize yourself with the general idea and architecture of the layout algorithm by reading its [[documentation>>doc:KIELER.KLay Layered]]. You should know about terms like //dummy nodes//, //intermediate processors//, and //phases//.
19 -1. With this knowledge, browse the code and try to identify the packages and classes that relate to the phases of KLay Layered.
20 -1. Understand the differences between the {{code language="none"}}KGraph{{/code}} and {{code language="none"}}LGraph{{/code}} and explore how to use the {{code language="none"}}LGraph{{/code}}. As noted in KLay Layered's documentation the {{code language="none"}}LGraph{{/code}} 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.
21 -[[image:attach:lgraph.png]]
22 -
23 23  = Assignment =
24 24  
25 -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:
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.
26 26  
27 -1. Configure the layout algorithm to use a {{code language="none"}}NullPhase{{/code}} for cycle breaking,
28 -1. Layer the possibly cyclic graph in a fashion as you like, and
29 -1. Use an intermediate processor to reverse edges (if required) such that subsequent phases are guaranteed to work with an acyclic graph.
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.
30 30  
31 -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.
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"}}EdgeReversalRestorer{{/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.
32 32  
33 -{{panel title="Assignment (b)"}}
34 -Create a layout phase called
35 -
36 -{{code language="none"}}
37 -NullPhase
38 -{{/code}}
39 -
40 - that does nothing but can be used as a cycle breaking strategy. You have to add it to the 
41 -
42 -{{code language="none"}}
43 -CycleBreakingStrategy
44 -{{/code}}
45 -
46 - enumeration.
41 +CODE
47 47  {{/panel}}
48 48  
49 -{{panel title="Assignment (b)"}}
50 -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.
51 -
52 -The {{code language="none"}}LEdge{{/code}} offers a method {{code language="none"}}reverseEdge{{/code}} that does parts of the job for you and marks the edge such that the {{code language="none"}}ReversedEdgeRestorer {{/code}}will take care of 'back'-reversing the edge at the end of the algorithm. Your class should extend the {{code language="none"}}ILayoutProcessor{{/code}} interface.
53 -
54 -{{code linenumbers="true" language="java"}}
55 -public class EdgeDirectionEnforcer implements ILayoutProcessor {
56 - @Override
57 - public void process(final LGraph layeredGraph, final IKielerProgressMonitor progressMonitor) {
58 - // for all edges ...
59 - if (...) {
60 - edge.reverse(layeredGraph, true);
61 - }
62 - }
63 -}
64 -{{/code}}
65 -{{/panel}}
66 -
67 -{{panel title="Assignment (c)"}}
44 +{{panel title="Assignment (2)"}}
68 68  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.
69 69  
70 -The intermediate processing configuration has to include your previously created intermediate processor as well as the existing {{code language="none"}}ReversedEdgeRestorer{{/code}}. The {{code language="none"}}IntermediateProcessorStrategy{{/code}} can help you to find the phase after which to execute the {{code language="none"}}ReversedEdgeRestorer{{/code}}.
47 +The intermediate processing configuration has to include your previously created intermediate processor as well as the mentioned edge reverser.
71 71  
72 -Take care not to place two nodes in the same layer if they are connected by an edge.
49 +CODE
73 73  
74 -{{code linenumbers="true" language="java"}}
75 -public class RandomLayerer implements ILayoutPhase {
76 - @Override
77 - public IntermediateProcessingConfiguration getIntermediateProcessingConfiguration(final LGraph graph) {
78 - return IntermediateProcessingConfiguration.createEmpty()
79 - [ ... ] // add your desired configuration here
80 - ;
81 - }
82 -
83 - @Override
84 - public void process(final LGraph layeredGraph, final IKielerProgressMonitor progressMonitor) {
85 - [ ... ]
86 - }
87 -}
88 -{{/code}}
89 -{{/panel}}
90 -
91 -{{tip}}
92 -Use {{code language="none"}}node.setLayer(layerX);{{/code}} to add assign a layer to a node. Internally, the node will be added to the layer's list of nodes.
93 -
94 -Don't forget to let the switch statements in the {{code language="none"}}LayeringStrategy{{/code}} and {{code language="none"}}IntermediateProcessorStrategy{{/code}} enumerations know about the new classes.
95 -
96 -The layout options you definitely need are {{code language="none"}}de.cau.cs.kieler.klay.layered.cycleBreaking{{/code}} and {{code language="none"}}de.cau.cs.kieler.klay.layered.nodePlace{{/code}}.
97 -{{/tip}}
98 -
99 99  
100 -
101 -
102 -
103 -
104 -
105 -
106 -
107 -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.
108 -
109 -
110 -
111 -[[image:attach:rand.jpg]][[image:attach:klay.jpg]]
52 +{{/panel}}
Confluence.Code.ConfluencePageClass[0]
Id
... ... @@ -1,1 +1,1 @@
1 -10751782
1 +10751726
URL
... ... @@ -1,1 +1,1 @@
1 -https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/TUT/pages/10751782/KLay Layered
1 +https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/TUT/pages/10751726/KLay Layered

Navigation

Quick Links

KIELER on GitHub
RTSYS Homepage