Eclipse Community Forums: GEF » [Zest] Layout implementations and node overlapping

Help

Home

Home » Eclipse Projects » GEF » [Zest] Layout implementations and node overlapping

Show: Today's Messages :: Show Polls :: Message Navigator

[Zest] Layout implementations and node overlapping [message #1714742]

Mon, 16 November 2015 10:50

Christoph Broeter

Messages: 30
Registered: July 2015

Member

Hey Folks.

My aim is to use several different graph layouts on a planar graph. And maybe you can help me to find a good layout or two. The layouts should satisfy following criteria:

• No node overlapping
• No edge crossing
• Optimal use of the canvas space.
• Minimal space between nodes.

Currently I've investigated these layouts: BoxLayout, GridLayout, TreeLayout, SpringLayout, SugiyamaLayout (Not working at all), RadialLayout, SpaceTreeLayout(also not working)

With following results:

BoxLayout
• Node overlapping
• Edge crossing
• Nodes are drawn over each other in a vertical orientation
index.php/fa/23952/0/

GridLayout:
• Node overlapping
• Edge crossing
• Nodes are randomly drawn in a grid based style.
index.php/fa/23953/0/

TreeLayout:
• No Node overlapping
• Kind of less Edge crossing
• The nodes are separated into Subtrees which will be orientated vertically on the canvas. Node space is kind of minimal, but since the tree is oriented only vertical the complete space of the canvas is not used properly.
index.php/fa/23956/0/

SpringLayout
• Node overlapping
• Edge crossing
• Nodes are randomly drawn on the canvas. And tied together by using a force related layout. The canvas space is used properly but several node overlappings and crossings.
index.php/fa/23955/0/

SugiyamaLayout
(Not working at all)

RadialLayout
• Node overlapping
• less Edge crossing
• Canvas space is used properly
index.php/fa/23954/0/

SpaceTreeLayout
(Not working at all)

I've also tryed Graphvis to layout the graph.
It is doing a nice job, but I don't like the static implementation.
Layout wise I really like the implementation of yWork's yED. But I can not afford a license. If some of you know which implementations they are using, I would appreciate it. They seem well rounded and well organized.
Maybe there is an other layout library out there which you can recommend and which could be used while using zest for representation.

Attachment: box.PNG
(Size: 10.67KB, Downloaded 2041 times)
Attachment: Grid.PNG
(Size: 127.85KB, Downloaded 2242 times)
Attachment: radial.PNG
(Size: 99.94KB, Downloaded 2467 times)
Attachment: spring.PNG
(Size: 104.84KB, Downloaded 2197 times)
Attachment: tree.PNG
(Size: 18.86KB, Downloaded 1962 times)

[Updated on: Mon, 16 November 2015 12:10]

Report message to a moderator

Re: [Zest] Layout implementations and node overlapping [message #1714753 is a reply to message #1714742]

Mon, 16 November 2015 12:12

Zoltan Ujhelyi

Messages: 392
Registered: July 2015

Senior Member

Hi,

the folks at the ELK project (https://projects.eclipse.org/projects/modeling.elk), formerly known as Kieler (http://www.rtsys.informatik.uni-kiel.de/en/research/kieler/) also provides some layouts. It is/was being planned to made compatible with GEF4/Zest, but in general it should be possible to wrap their algorithms as needed.

Cheers,
Zoltán

Report message to a moderator

Re: [Zest] Layout implementations and node overlapping [message #1714756 is a reply to message #1714753]

Mon, 16 November 2015 12:30

Christoph Broeter

Messages: 30
Registered: July 2015

Member

Zoltan Ujhelyi wrote on Mon, 16 November 2015 12:12

Hi,
.....
It is/was being planned to made compatible with GEF4/Zest, but in general it should be possible to wrap their algorithms as needed.

Cheers,
Zoltán

This is nice! I'll definitely take a look into KIELER. Maybe i could use the algorithms for offline work.

Report message to a moderator

Re: [Zest] Layout implementations and node overlapping [message #1714849 is a reply to message #1714756]

Tue, 17 November 2015 09:35

Christoph Broeter

Messages: 30
Registered: July 2015

Member

Is there somewhere some example code for using the layout mechanism of ELK?

Report message to a moderator

Re: [Zest] Layout implementations and node overlapping [message #1714871 is a reply to message #1714849]

Tue, 17 November 2015 11:58

Alexander Nyssen

Messages: 244
Registered: July 2009
Location: Lünen

Senior Member

We are in communication with the ELK-committers to make an integration with GEF4 Layout feasible (see bug #440098). We have decided to postpone this until the ELK project is properly created at eclipse.

Can you provide details on why the Sugiyama algorithm does not work at all (or rather create respective bugs to let us now)?

Report message to a moderator

Re: [Zest] Layout implementations and node overlapping [message #1714898 is a reply to message #1714871]

Tue, 17 November 2015 15:08

Christoph Broeter

Messages: 30
Registered: July 2015

Member

We are talking about org.eclipse.gef4.layout.algorithms.SugiyamaLayoutAlgorithm;

Currently an exception is thrown in the LayoutSelectionListener which is listening on an instance of org.eclipse.swt.widgets.Combo.

Exception in thread "JavaFX Application Thread" java.lang.RuntimeException: Graphical tree exceeds maximum depth of 10! (Graph not directed? Cycles?)
	at org.eclipse.gef4.layout.algorithms.SugiyamaLayoutAlgorithm$SimpleLayerProvider.calculateLayers(SugiyamaLayoutAlgorithm.java:1044)
	at org.eclipse.gef4.layout.algorithms.SugiyamaLayoutAlgorithm.applyLayout(SugiyamaLayoutAlgorithm.java:1151)
	at org.eclipse.gef4.layout.AbstractLayoutContext.applyStaticLayout(AbstractLayoutContext.java:128)
	at org.eclipse.gef4.zest.fx.behaviors.LayoutContextBehavior.applyStaticLayout(LayoutContextBehavior.java:173)
	at org.eclipse.gef4.zest.fx.behaviors.LayoutContextBehavior.onHostPropertyChange(LayoutContextBehavior.java:231)
	at org.eclipse.gef4.zest.fx.behaviors.LayoutContextBehavior$4.propertyChange(LayoutContextBehavior.java:80)
	at java.beans.PropertyChangeSupport.fire(Unknown Source)
	at java.beans.PropertyChangeSupport.firePropertyChange(Unknown Source)
	at java.beans.PropertyChangeSupport.firePropertyChange(Unknown Source)
	at java.beans.PropertyChangeSupport.firePropertyChange(Unknown Source)
	at org.eclipse.gef4.zest.fx.parts.GraphContentPart.doActivate(GraphContentPart.java:110)
	at org.eclipse.gef4.mvc.parts.AbstractVisualPart.activate(AbstractVisualPart.java:106)
	at org.eclipse.gef4.mvc.parts.AbstractVisualPart.addChild(AbstractVisualPart.java:199)
	at org.eclipse.gef4.mvc.behaviors.ContentBehavior.synchronizeContentChildren(ContentBehavior.java:300)
	at org.eclipse.gef4.mvc.behaviors.ContentBehavior.propertyChange(ContentBehavior.java:148)
	at java.beans.PropertyChangeSupport.fire(Unknown Source)
	at java.beans.PropertyChangeSupport.firePropertyChange(Unknown Source)
	at java.beans.PropertyChangeSupport.firePropertyChange(Unknown Source)
	at org.eclipse.gef4.mvc.models.ContentModel.setContents(ContentModel.java:48)
	at org.eclipse.gef4.zest.fx.ui.jface.ZestContentViewer.refresh(ZestContentViewer.java:442)
	at org.eclipse.gef4.zest.fx.ui.jface.ZestContentViewer.inputChanged(ZestContentViewer.java:434)
	at org.eclipse.jface.viewers.ContentViewer.setInput(ContentViewer.java:292)
	at com.project.zest.styleprovider.layout.listener.LayoutSelectionListener.widgetSelected(LayoutSelectionListener.java:97)
	at org.eclipse.swt.widgets.TypedListener.handleEvent(TypedListener.java:248)
	at org.eclipse.swt.widgets.EventTable.sendEvent(EventTable.java:84)
	at org.eclipse.swt.widgets.Display.sendEvent(Display.java:4362)
	at org.eclipse.swt.widgets.Widget.sendEvent(Widget.java:1113)
	at org.eclipse.swt.widgets.Display.runDeferredEvents(Display.java:4180)
	at org.eclipse.swt.widgets.Display.readAndDispatch(Display.java:3769)
	at com.project.zest.AGraPlan.showGraph(AGraPlan.java:105)
	at com.project.zest.AGraPlan.analyzeFiles(AGraPlan.java:67)
	at com.project.zest.AGraPlan.main(AGraPlan.java:185)

The layoutAlgorithm is initialized in the following way:

ZestContentViewer viewer = new ZestContentViewer(new UMLComponentModule());
viewer.createControl(c, SWT.NONE);
viewer.setContentProvider(new UMLGraphContentProvider(graph));
viewer.setLabelProvider(new UMLGraphStyleProvider());
SugiyamaLayoutAlgorithm sla = new SugiyamaLayoutAlgorithm();
viewer.setLayoutAlgorithm(sla);
viewer.setInput(new Object());<--Exception is thrown here

As for me, I am very new to the this topic of zest and layouting graphs.
Therefore i might have missed something important in the initialization of the algorithm. Sad

[Updated on: Tue, 17 November 2015 15:17]

Report message to a moderator

Re: [Zest] Layout implementations and node overlapping [message #1715152 is a reply to message #1714898]

Thu, 19 November 2015 16:10

Matthias Wienand

Messages: 230
Registered: March 2015

Senior Member

Hi Christoph,

actually, you can pass a LayerProvider into the constructor of SugiyamaLayoutAlgorithm. The default LayerProvider is the SugiyamaLayoutAlgorithm.SimpleLayerProvider, which is restricted to a maximum number of 10 layers (MAX_LAYERS). You can try to use the SugiyamaLayoutAlgorithm.DSFLayerProvider instead as follows:

new SugiyamaLayoutAlgorithm(Direction.VERTICAL, new SugiyamaLayoutAlgorithm.DSFLayerProvider()

If the DSFLayerProvider is not sufficient, you can also implement a custom LayerProvider.

Best regards,
Matthias

[Updated on: Thu, 19 November 2015 16:10]

Report message to a moderator

Re: [Zest] Layout implementations and node overlapping [message #1715581 is a reply to message #1715152]

Tue, 24 November 2015 13:14

Christoph Broeter

Messages: 30
Registered: July 2015

Member

Thanks that helped.
Now the SugiyamaAlgorithm is working.
index.php/fa/24064/0/

But I am not satisfied with the result of the Algorithms.
The graph is planar. This is not taken into account in the algorithms, since every layout has some crossings. For instance the Springlayout has a lot of crossings and node overlappings. As seen in:
index.php/fa/24065/0/

.
There might also be a lot of misunderstanding from my side.
I hope you can help me to find at least one nice looking layout.

This is another layout of the same graph created by GraphVis(PDP) and its the one which is currently the most satisfying layout.
index.php/fa/24066/0/

Attachment: sugi.PNG
(Size: 54.88KB, Downloaded 1989 times)
Attachment: spring.PNG
(Size: 114.17KB, Downloaded 2219 times)
Attachment: pdp.PNG
(Size: 75.67KB, Downloaded 2184 times)

[Updated on: Tue, 24 November 2015 13:42]

Report message to a moderator

Re: [Zest] Layout implementations and node overlapping [message #1715619 is a reply to message #1715581]

Tue, 24 November 2015 17:20

Alexander Nyssen

Messages: 244
Registered: July 2009
Location: Lünen

Senior Member

Looks like it could make sense to calculate some strongly connected components up front, and to layout these individually (and use a separate algorithm for the overall layout). The GEF4 layout algorithms do not reflect such a functionality. However, it could be something that makes sense to offer as part of Zest, where it would fit in nicely with the currently not very useful hiding-functionality. I have opened https://bugs.eclipse.org/bugs/show_bug.cgi?id=482932 to keep track of this. We can continue any discussion there.

Report message to a moderator

Re: [Zest] Layout implementations and node overlapping [message #1717713 is a reply to message #1715619]

Wed, 16 December 2015 09:39

Christoph Broeter

Messages: 30
Registered: July 2015

Member

Hey again, I am trying to understand what is told.
A component is strongly connected if every vertex there is a directed path in that component from the vertex to every other vertex in that component.
Therefore the graph is not strongly connected. As per my analysis there are no strongly connected components rather than the single nodes.
But I am guessing that you are trying to say: "It might be helpful to calculate connected components" , "lay them out as a first step" and "use an shift mechanic to layout the connected components" to get an overall layout.

Report message to a moderator

Re: [Zest] Layout implementations and node overlapping [message #1717741 is a reply to message #1717713]

Wed, 16 December 2015 12:56

Christoph Broeter

Messages: 30
Registered: July 2015

Member

To show some deficits of the layouts. I've used a simple, planar, directed and connected graph as an example.

Tree
index.php/fa/24342/0/

Spring

Sugiyama

Radial

as you can see, all layouts except the sugiyama layout do have edge crossings for this instance.

Attachment: tree.PNG
(Size: 14.32KB, Downloaded 1923 times)
Attachment: spring.PNG
(Size: 48.24KB, Downloaded 2353 times)
Attachment: sugi.PNG
(Size: 25.96KB, Downloaded 2116 times)
Attachment: radial.PNG
(Size: 33.91KB, Downloaded 2100 times)

[Updated on: Wed, 16 December 2015 12:58]

Report message to a moderator

Re: [Zest] Layout implementations and node overlapping [message #1719690 is a reply to message #1717741]

Mon, 11 January 2016 13:31

Christoph Broeter

Messages: 30
Registered: July 2015

Member

Hello I am back from vacation and will answer as soon as possible.

Offtopic Question: Is there some way to create sunburst diagramms like visuals by using GEF or some other SWT library/framework ?

Report message to a moderator