Skip to Content

Changes for page KLay Layered

Last modified by Richard Kreissig on 2023/09/14 10:18
From version 25.1
edited by sskr2
on 2015/04/21 12:49
Change comment: There is no comment for this version
To version 22.1
edited by msp
on 2014/07/15 01:58
Change comment: There is no comment for this version

Summary

Details

Page properties
Author
... ... @@ -1,1 +1,1 @@
1 -XWiki.sskr2
1 +XWiki.msp
Content
... ... @@ -1,16 +1,13 @@
1 1  {{panel title="Project Overview" borderStyle="dashed"}}
2 2  Responsible:
3 3  
4 -* {{mention reference="XWiki.cds" style="FULL_NAME" anchor="XWiki-cds-cnnFJ"/}}
4 +* {{mention reference="XWiki.cds" style="FULL_NAME" anchor="XWiki-cds-wVPxS"/}}
5 5  
6 -Key Publications:
6 +Related Publications:
7 7  
8 -* 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>>url:http://www.sciencedirect.com/||shape="rect"]]. ([[pdf>>url:http://rtsys.informatik.uni-kiel.de/%7Ebiblio/downloads/papers/jvlc13.pdf||shape="rect"]] / [[bib>>url:http://rtsys.informatik.uni-kiel.de/%7Ebiblio/cgi-bin/bibcgi.cgi?key=SchulzeSvH14||shape="rect"]])
9 -
10 -Further Publications:
11 -
12 12  * 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>>url:http://link.springer.com/||shape="rect"]]. ([[pdf>>url:http://rtsys.informatik.uni-kiel.de/%7Ebiblio/downloads/papers/gd09.pdf||shape="rect"]] / [[bib>>url:http://rtsys.informatik.uni-kiel.de/%7Ebiblio/cgi-bin/bibcgi.cgi?key=SpoenemannFvH+09||shape="rect"]])
13 13  * 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>>url:http://link.springer.com/||shape="rect"]]. ([[pdf>>url:http://rtsys.informatik.uni-kiel.de/%7Ebiblio/downloads/papers/diagrams12b.pdf||shape="rect"]] / [[bib>>url:http://rtsys.informatik.uni-kiel.de/%7Ebiblio/cgi-bin/bibcgi.cgi?key=KlauskeSS+12||shape="rect"]])
10 +* 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>>url:http://www.sciencedirect.com/||shape="rect"]]. ([[pdf>>url:http://rtsys.informatik.uni-kiel.de/~~biblio/downloads/papers/jvlc13.pdf||shape="rect"]] / [[bib>>url:http://rtsys.informatik.uni-kiel.de/~~biblio/cgi-bin/bibcgi.cgi?key=SchulzeSvH14||shape="rect"]])
14 14  * 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>>url:http://rtsys.informatik.uni-kiel.de/~~biblio/downloads/papers/report-1404.pdf||shape="rect"]] / [[bib>>url:http://rtsys.informatik.uni-kiel.de/~~biblio/cgi-bin/bibcgi.cgi?key=SpoenemannSRvH14b||shape="rect"]])
15 15  
16 16  Related Theses:
... ... @@ -43,9 +43,9 @@
43 43  
44 44  The backbone of KLay Layered are its five layout phases, of which each is performing a specific part of the work necessary to layout a graph. Three of the five phases (layer assignment, crossing minimization, and node placement) go back to a paper by Sugiyama et al. They are widely used as the basis for layout algorithms, and can be found in loads of papers on the topic. A detailed description of what each layout phase does can be found [[on this page>>doc:The Five Phases]].
45 45  
46 -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 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.
43 +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 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.
47 47  
48 -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 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.
45 +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 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.
49 49  
50 50  For graphs that are not connected it is possible to execute the algorithm, i.e. the five phases with intermediate processors, separately on each connected component. The connected components processor splits an unconnected graph into multiple connected graphs and rearranges them after the layout of each component has been computed. This helps to present the components more compactly and neatly.
51 51  
... ... @@ -63,7 +63,7 @@
63 63  
64 64  [[image:attach:Layering_Dummies.png]]
65 65  
66 -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 our implementation of port support on the northern or southern side of a node.
63 +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 on the northern or southern side of a node.
67 67  
68 68  == Class Design ==
69 69  
... ... @@ -100,20 +100,4 @@
100 100  1. 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.
101 101  1. Finally, it again uses one of the IGraphImporter implementations to apply the computed layout back to the KGraph.
102 102  
103 -= Example Layouts =
104 -
105 -Below some example diagrams that were layouted with the KLay Layered algorithm.
106 -
107 -== Ptolemy Diagram ==
108 -
109 -[[image:attach:ptolemy.png]]
110 -
111 -== SCChart with Dataflow ==
112 -
113 -(% style="text-align: left;" %)
114 -[[image:attach:scchartsdataflow.png]]
115 -
116 -(% style="text-align: left;" %)
117 -== SCG ==
118 -
119 -[[image:attach:scg.png]]
100 +
Confluence.Code.ConfluencePageClass[0]
Id
... ... @@ -1,1 +1,1 @@
1 -10751775
1 +10158118
URL
... ... @@ -1,1 +1,1 @@
1 -https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/10751775/KLay Layered
1 +https://rtsys.informatik.uni-kiel.de/confluence//wiki/spaces/KIELER/pages/10158118/KLay Layered