Wiki source code of Layout Algorithms

Last modified by Richard Kreissig on 2023/09/14 09:07
Show last authors
1 Welcome to this tutorial! We will work our way through installing a proper Eclipse setup and developing a first very basic layout algorithm. The layout algorithm will integrate with [[ELK>>url:https://github.com/eclipse/elk/wiki||shape="rect"]] (Eclipse Layout Kernel), our very own framework that connects graphical editors with layout algorithms. Once you're finished, you should be able to write layout algorithms for ELK. And you should have a running Eclipse-based application that should look something like this:
2
3 [[image:attach:example.jpg]]
4
5
6
7 {{toc/}}
8
9 = Preliminaries =
10
11 There's a few things to do before we dive into the tutorial itself. For example, to do Eclipse programming, you will have to get your hands on an Eclipse installation first. Read through the following sections to get ready for the tutorial tasks.
12
13 == Required Software ==
14
15 [[doc:KIELER.Development.Tutorials.Other.Installing Eclipse for Layout Development.WebHome]]
16
17
18
19 == Finding Documentation ==
20
21 [[doc:KIELER.Development.Tutorials.Other.Finding Documentation.WebHome]]
22
23
24
25 = Developing Your First Layout Algorithm =
26
27 Now that the preliminaries are out of the way, it's time to develop your first layout algorithm! It will, however, be a very simple one. This tutorial focuses on creating Eclipse plug-ins and on learning how to develop with ELK.
28
29 == Adding a New Plug-in ==
30
31 We need to create a new plug-in to implement the layout algorithm in. Switch back to the Java or Plug-in Development perspective and follow these steps:
32
33 1. Click //File// > //New// > //Other...// > //Plug-in Development// > //Plug-in Project//.
34 1. Enter {{code language="none"}}de.cau.cs.kieler.simplelayout{{/code}} as the project name. Click //Next//.
35 1. Set the execution environment to //JavaSE-1.8//. (do this for all plug-ins that you create!)
36 1. Uncheck all checkboxes in the //Options// group and click //Finish//.
37 1. If Eclipse asks you whether the //Plug-in Development// perspective should be opened, choose either //Yes// or //No//. It doesn't make much of a difference anyway.
38
39 == Writing the Layout Algorithm ==
40
41 When writing our layout algorithm, we are going to need to be able to access code defined in several other plug-ins. To do that, we need to add dependencies to those plug-ins:
42
43 1. In your new plug-in, open the file {{code language="none"}}META-INF/MANIFEST.MF{{/code}}. The plug-in manifest editor will open. Open its //Dependencies// tab.
44 1. Add dependencies to the following plug-ins:
45 1*. {{code language="none"}}org.eclipse.elk.core{{/code}}
46 1*. {{code language="none"}}org.eclipse.elk.graph{{/code}}
47 1. Save the editor.
48
49 Layout algorithms interface with ELK by means of a layout provider class that has to be created and registered with KIML.
50
51 1. Right-click the source folder of your plug-in and click //New// > //Class//.
52 1. Set the package to {{code language="none"}}de.cau.cs.kieler.simplelayout{{/code}}{{code language="none"}}{{/code}}, enter {{code language="none"}}SimpleLayoutProvider{{/code}} as the class name, and select {{code language="none"}}org.eclipse.elk.core.AbstractLayoutProvider{{/code}} as the superclass. (This will only be available through the //Browse// dialog if you have saved the plug-in manifest editor; if you haven't, Eclipse won't know about the new dependencies yet.)
53 1. Select //Generate comments// and click //Finish//.
54
55 Implement the layout provider class:
56
57 1. (((
58 Add the following constants:
59
60 {{code language="java"}}
61 /** default value for spacing between nodes. */
62 private static final float DEFAULT_SPACING = 15.0f;
63 {{/code}}
64 )))
65 1. (((
66 Use the following code as the skeleton of the {{code language="none"}}layout(...){{/code}} method:
67
68 {{code language="java"}}
69 progressMonitor.begin("Simple layouter", 1);
70 KShapeLayout parentLayout = layoutGraph.getData(KShapeLayout.class);
71
72 float objectSpacing = parentLayout.getProperty(CoreOptions.SPACING_NODE);
73 if (objectSpacing < 0) {
74 objectSpacing = DEFAULT_SPACING;
75 }
76
77 float borderSpacing = parentLayout.getProperty(CoreOptions.SPACING_BORDER);
78 if (borderSpacing < 0) {
79 borderSpacing = DEFAULT_SPACING;
80 }
81
82 // TODO: Insert actual layout code.
83
84 progressMonitor.done();
85 {{/code}}
86 )))
87 1. Press //CTRL+SHIFT+O// or select //Source > Organize Imports// from the context menu to add all required imports.
88 1. It is now time to write the code that places the nodes.Your code should place them next to each other in a row, as seen in the screenshot at the beginning of the tutorial.
89
90 {{info title="Tips"}}
91 The following tips might come in handy...
92
93 * Read the documentation of the [[KGraph>>doc:KIELER.KGraph Meta Model]] and [[KLayoutData>>doc:KIELER.KLayoutData Meta Model]] meta models. The input to the layout algorithm is a {{code language="none"}}KNode{{/code}} that has child {{code language="none"}}KNode{{/code}}s for every node in the graph. Iterate over these nodes by iterating over the {{code language="none"}}getChildren(){{/code}} list of the {{code language="none"}}parentNode{{/code}} argument.
94 * (((
95 Retrieve the size of a node and set its position later using the following code:
96
97 {{code language="java"}}
98 KShapeLayout nodeLayout = node.getData(KShapeLayout.class);
99
100 // Retrieving the size
101 float width = nodeLayout.getWidth();
102 float height = nodeLayout.getHeight();
103
104 // Setting the position
105 nodeLayout.setXpos(x);
106 nodeLayout.setYpos(y);
107 {{/code}}
108 )))
109 * {{code language="none"}}objectSpacing{{/code}}is the spacing to be left between each pair of nodes.
110 * {{code language="none"}}borderSpacing{{/code}}is the spacing to be left to the borders of the drawing. The top left node's coordinates must therefore be at least {{code language="none"}}(borderSpacing, borderSpacing){{/code}}.
111 * At the end of the method, set the width and height of {{code language="none"}}parentLayout{{/code}} such that it is large enough to hold the whole drawing, including borders.
112 * A complete layout algorithm will of course also route the edges between the nodes. Ignore that for now – you will do this at a later step.
113 {{/info}}
114
115
116 Before you can test your layout code, you will have to register your new layout provider with ELK.
117
118 1. Right-click the {{code language="none"}}de.cau.cs.kieler.simplelayout{{/code}}{{code language="none"}}{{/code}} package and select //New > File.//
119 1. Create a file// simple.elkm //and double click it to open it.
120 1. When asked whether you want to add the //Xtext nature//, select //yes//.
121 1. (((
122 The file is used to specify meta information for your layout algorithm. For this, copy the following code snippet into your editor:
123
124 {{code language="java"}}
125 package de.cau.cs.kieler.simplelayout
126
127 bundle {
128 label "Simple Layout Algoritms"
129 metadataClass SimpleMetaDataProvider
130 }
131
132 algorithm simple(SimpleLayoutProvider) {
133 label "Simple Test Layouter"
134 metadataClass SimpleOptions
135
136  supports org.eclipse.elk.spacing.border
137 supports org.eclipse.elk.spacing.node
138 }
139 {{/code}}
140 )))
141 1. You still have to register the file with Eclipse. Open the {{code language="none"}}META-INF/MANIFEST.MF{{/code}} file again and switch to the //Extensions// tab.
142 1. Add an extension for {{code language="none"}}org.eclipse.elk.core.layoutProviders{{/code}}.
143 1. Right-click the extension and click //New// > //provider//.
144 1. Set the class to your bundle's meta data provider class name (use the browse button and enter {{code language="none"}}SimpleMetaDataProvider{{/code}}). Note that {{code language="none"}}SimpleMetaDataProvider{{/code}} is automatically generated from the //.elkm// file you created. Its name is specified by the {{code language="none"}}metadataClass{{/code}} keyword in the {{code language="none"}}bundle{{/code}} section. What is also created is the {{code language="none"}}SimpleOptions{{/code}} class, which contains everything you need to access layout options from within your layout algorithm.
145 1. Save the editor
146 1. Your workspace should look similar to this
147 [[image:attach:1.png]]
148
149 We will now have to add a new run configuration that will start an Eclipse instance with your layout code loaded into the application, ready to be used.
150
151 1. Click //Run// > //Debug Configurations...//
152 1. Right-click //Eclipse Application// and click //New//. Set the configuration's name to {{code language="none"}}Layout Test{{/code}}.
153 1. In the //Arguments// tab, make sure the the program arguments include {{code language="none"}}-debug{{/code}} and {{code language="none"}}-consoleLog{{/code}}.
154 1. On the //Plug-ins// tab, set //Launch with// to //plug-ins selected below only//.
155 11. Click //Deselect All//.
156 11. Check the //Workspace// item in the tree.
157 11. Check the following plugins under //Target Platform// are checked:
158 11*. {{code language="none"}}de.cau.cs.kieler.kgraph.text.ui{{/code}}
159 11*. {{code language="none"}}de.cau.cs.kieler.klighd.xtext{{/code}}
160 11*. {{code language="none"}}org.eclipse.ui.ide.application{{/code}}
161 11*.
162
163 {{{org.eclipse.platform}}}
164
165 1.
166 11. Click //Add Required Plug-ins//. Press it twice (just to be sure!).
167 1. Click //Apply// to save your changes and then //Debug// to start an Eclipse instance to test with.
168
169 Test the layouter in your new Eclipse instance:
170
171 1. Click //New// > //Project...// > //General// > //Project// and set the project name to something like {{code language="none"}}Test{{/code}}.
172 1. Right-click the new project and click //New// > //Other > KGraph > Random KGraph//. Enter a meaningful name and click //Finish//.
173 1. Open the .kgt file. To show up the Diagram vie, select //Window// > //Show View// > Other... > Other > Diagram
174 1. Open the //Layout// view through //Window// > //Show View// > //Other...// > //Eclipse Diagram Layout// > //Layout//. Move the view somewhere such that you can see the view and the diagram simultaneously.
175 1. Chose your //Simple Test Layouter// in the //Layout Algorithm// section of the //Layout View//. (If the //Layout// //View// shows no properties, click the white background in the //Diagram View// once.)
176 1. You should see something similar to this
177 [[image:attach:layout.jpg]]
178
179 Once you're satisfied with your node placement code, it's time to take care of edge routing.
180
181 1. (((
182 Add a new method that will implement the edge routing using the following skeleton code:
183
184 {{code language="java"}}
185 /**
186 * Routes the edges connecting the nodes in the given graph.
187 *
188 * @param parentNode the graph whose edges to route.
189 * @param yStart y coordinate of the start of the edge routing area.
190 * @param objectSpacing the object spacing.
191 * @return height used for edge routing.
192 */
193 private float routeEdges(final KNode parentNode, final float yStart, final float objectSpacing) {
194 // TODO: Implement edge routing
195
196 return 0;
197 }
198 {{/code}}
199 )))
200 1. Add a call to {{code language="none"}}routeEdges(...){{/code}} in your {{code language="none"}}doLayout(...){{/code}} method and implement the latter.
201
202 {{info title="Tips"}}
203 Here's a few tips for implementing the edge routing:
204
205 * Each edge shall be drawn with three orthogonal line segments: one vertical segment below the start node, one vertical segment below the target node, and a horizontal segment that connects the two.
206 * The horizontal segments of two different edges shall not have the same y-coordinate. Two neighboring horizontal segments shall be placed at a distance of objectSpacing.
207 * See the screenshot at the top of the tutorial for an example.
208 * Find the edges in a graph by calling {{code language="none"}}getOutgoingEdges(){{/code}} or {{code language="none"}}getIncomingEdges(){{/code}} on the nodes.
209 * (((
210 You can add bend points to edges through the edge's edge layout:
211
212 {{code language="java"}}
213 KEdgeLayout edgeLayout = edge.getData(KEdgeLayout.class);
214 KPoint bendPoint = KLayoutDataFactory.eINSTANCE.createKPoint();
215 edgeLayout.getBendPoints().add(bendPoint);
216 {{/code}}
217 )))
218 * You will want to clear the list of bend points of each edge layout before adding bend points to it. This will remove all bend points the edge had prior to invoking your layout algorithm.
219 * Set the values of the points returned by {{code language="none"}}getSourcePoint(){{/code}} and {{code language="none"}}getTargetPoint(){{/code}} according to the positions where an edge leaves its source node and reaches its target node.
220 * If you want, you can improve the edge routing code by allowing horizontal segments to share the same y-coordinate if that doesn't make them overlap. Your goal could be to produce an edge routing that uses as little space as possible.
221 * (((
222 If that's not enough yet: can you find a way to find an order of the horizontal segments such that as few edge crossings as possible are produced?
223 )))
224
225 {{warning}}
226 The drawing framework does something //intelligent//. Or at least it thinks it is intelligent. When the source point or target point of an edge does not touch the boundary of a node, it moves them such that they touch the boundary. This can be confusing when you calculate and specify positions in the code that are not reflected in the diagram you see.
227 {{/warning}}
228 {{/info}}
229
230 Once you're done implementing the edge routing code, test it by running your debug configuration again, as before.
231
232
233 (% style="display: none;" %)
234 (((
235 257
236 )))

Navigation

Quick Links

KIELER on GitHub
RTSYS Homepage