graph autolayout testing

[forresto]

advantages:

• no need to tweak everything when editing middle of graph
• different views (ltr, ttb) for different people working in the same graph
• reasonable default view when opening any FBP or graph without node position metadata
• encourages grouping (~> code comments)
• collapse groups (~> code folding)

disadvantages:

• control

---

testing with yed's built-in algorithms on the photobooth graph

noflo manual

yed manual

yed organic

yed hierarchical ungrouped, left-to-right, octilinear edge

yed hierarchical grouped, top-to-bottom, othographic edge

[forresto]

Hierarchical graphs make the most sense. Keeping the hierarchy in one direction (east or south) takes up a little more space than the manual version (which i made east and south), but might be a little easier to follow?

Grouping is a nice feature, I was doing that manually a bit.

Octilinear edges make the graph a little bigger, but I like the look.

My favorite part of yed is the animation when you change the layout.

---

Conclusion:

• We don't have to reinvent the wheel.
• I'd really appreciate not having to fiddle with the graph on every change.
• Concise motion would help keep you oriented in the graph.
• Grouping gives you more control when you want it.

[forresto]

yeah, grouping is nice

l2r

t2b

[d4tocchini]

+1

[forresto]

http://docs.yworks.com/yfiles/doc/developers-guide/incremental_hierarchical_layouter.html

"yfiles for html" http://live.yworks.com/yfiles-for-html/1.1/demos/Complete/demo.yfiles.graph.incrementalhierarchicgrouping/index.html

(closed source :thumbsdown:)

As a yFiles for HTML licensee, you can use yFiles for HTML in an open source project with the following restrictions:

• yFiles functionality needs to be encapsulated in a separate module with an interface that is specific for your application and is pretty thin. It is not allowed to create or publish a wrapper component that allows third parties to use your application or the yFiles module as a (partial) replacement of yFiles.
• Before distributing this yFiles module, you'd need to run it through a shrinker/source code obfuscater that we do ship with yFiles

... So, the equivalent of a closed-source dll. I think we could conform to these requirements, since we just need to pass in a graph and get back the layout. Could be a webworker and a minified version of the algos we need.

[forresto]

There is also http://mdaines.github.io/viz.js/example.html , emscriptened from Graphviz.

[forresto]

and force-directed 3d :smile: https://github.com/davidpiegza/Graph-Visualization (algo) (o/t)

[forresto]

this research paper covers the bases: http://rtsys.informatik.uni-kiel.de/~biblio/downloads/theses/msp-dt.pdf

If the input is an arbitrary directed graph, the main phases of the algorithm are the following.

1. Cycle removal: Break directed cycles by reversing some edges, while keeping the number of reversed edges as low as possible. In the final drawing the reversed edges are restored again, so that they point against the predominant direction of flow.
2. Layer assignment: Create a minimal set of layers L1; : : : ; Lk and assign a layer to each vertex such that for all edges (u; v) the assigned layers Li of u and Lj of v satisfy i < j. This is possible because after the first phase the graph is acyclic. Another way of expressing this problem is that of finding a topological numbering t for which max t(V ) is minimal.
3. Crossing reduction: Find an ordering of the vertices of each layer that minimizes the number of edge crossings.
4. Determine exact positions of all vertices inside their corresponding layers. The vertices must not overlap each other, the ordering from the previous phase must be respected and the position of each vertex must be well-balanced with respect to its neighbors. We will call this crosswise placement.
5. Edge routing: Determine bend points for each edge and the exact distance between subsequent layers, which we will call lengthwise placement.

2014 paper from same folks: http://rtsys.informatik.uni-kiel.de/~biblio/downloads/papers/jvlc13.pdf

The actual .java code: https://git.rtsys.informatik.uni-kiel.de/projects/KIELER/repos/pragmatics/browse/plugins/de.cau.cs.kieler.klay.layered/src/de/cau/cs/kieler/klay/layered

[forresto]

dagre seems like a good starting place. They might be working on grouping: https://github.com/cpettitt/dagre/issues/13

Will ask about ports

[forresto]

@franchi82's research paper's algos have been developed in KIELER Layout Algorithms

Some documentation is available here:

http://rtsys.informatik.uni-kiel.de/confluence/display/KIELER/KLay+Layered

"KLay Layered" supports several kinds of port constraints. See it in action here: http://rtsys.informatik.uni-kiel.de/~kieler/videos/ptolemyViewer/PtolemyViewerHQ.html

I like the inline collapsing of groups / subgraphs.

[automata]

Here at Physics Dept. we are used to Gephi to do graph and complex network visualizations. It has a nice collection of layouts:

https://gephi.org/

NetworkX (Python) and JSNetworkX (a JS port) also have interesting layouts that could be util:

http://networkx.github.io/ http://felix-kling.de/JSNetworkX/

[forresto]

It looks like those are force-directed, which seem less suited for dataflow, since dataflow graphs are inherently directional.

KIELER / KLay Layered seems the most promising open option now. Maybe plugging their port constraint algos into dagre. Dagre seems like a good foundation for the rest of the constraints.

[forresto]

Current plan of action: See if KLay works for us with:

• KLay as a service: http://rtsys.informatik.uni-kiel.de/confluence/display/KIELER/HTTP-based+Service
• + SVG prototype: https://github.com/forresto/prototyping/issues/2

[automata]

First tests using KIELER/KLay service.

Original noflo graph:

Using KIELER/Klay layered algorithm (direction: TOP-DOWN):

Using KIELER/Klay layered algorithm (direction: LEFT-RIGHT):

[automata]

Prototyping at http://automata.github.io/prototyping/react.

We really need to specify groups as well pointed in https://github.com/the-grid/the-graph/issues/43 before applying layout algorithms. They should deal with group creation as pointed by @forresto. Otherwise:

[automata]

The supported layout options for KIELER/Klay Layered algorithm: http://layout.rtsys.informatik.uni-kiel.de:9444/Providedlayout.html?algorithm=de.cau.cs.kieler.klay.layered.

Better explained at http://rtsys.informatik.uni-kiel.de/confluence/display/KIELER/KLay+Layered+Layout+Options

[automata]

Now we can tweak some KIELER/Klay Layered parameters at http://automata.github.io/prototyping/react

Some important parameters/properties I'm discovering from KIELER Java implementation of Klay Layered algo: https://github.com/automata/prototyping/wiki/Important-Klay-Layered-Layout-Options-(Properties)

[automata]

Ports (constraint) are now considered by the KIELER/Klay service. Yielding a better layout:

Next step: groups/layers.

[automata]

We have groups (converted to KIELER KGraph's subgraphs):

Lots of lost space. I think we should add more groups in this 'photobooth graph' to really take advantage of the autolayout algorithm.

[forresto]

That doesn't seem right... I'd think that they would end up in one layer, sorted like this:

Is there a mechanism to indicate whether a group is collapsed or expanded? Or do you just send a pruned graph?

The rest is looking good. I'll add grouping UI next, or you can try by hand from this image.

[spoenemann]

The edges that cross group boundaries are not considered unless the option "de.cau.cs.kieler.layoutHierarchy" is set to "true" for the top-level node (LayoutOptions.LAYOUT_HIERARCHY). However, the grouped layouts won't look as good as those from yFiles, since we are using a much simpler method for hierarchical layout, leading to a lot of unnecessary crossings.

[automata]

@franchi82 thank you for the tip, it seems better now (is that edge crossing expected?):

Do we have to specify the group node's edges/port appropriately @franchi82? As pointed here in the third example:

{
  id: "root",  // root node
  children: [{
    id: "n1",  // node n1
    labels: [ { text: "n1" } ],
    // node n1 has fixed port constraints
    properties: {de.cau.cs.kieler.portConstraints: "FIXED_SIDE"},
    width: 100, 
    height: 100,
    ports: [{
      id: "p1",
      width: 10,
      height: 10,
      // port p1 should be located on the north side
      properties: {de.cau.cs.kieler.portSide: "NORTH"}
    }]
  },{
    id: "n2",  // node n2
    labels: [ { text: "n2" } ],
    properties: {de.cau.cs.kieler.portConstraints: "FIXED_SIDE"},
    width: 100,
    height: 50,
    ports: [{
      id: "p2",
      width: 10,
      height: 10,
      properties: {de.cau.cs.kieler.portSide: "SOUTH"}
    }]
  }],
  // children end
  edges: [{
    id: "e1",  // edge n1 -> n2
    source: "n1",
    target: "n2",
    sourcePort: "p1", // p1 -> p2
    targetPort: "p2"
  }]
}

[automata]

@forresto I don't know if there is some way to collapse the groups. Maybe we can force that setting "de.cau.cs.kieler.layoutHierarchy" to false? Yes, I'll try to specify more groups, thank you for the ref.

[spoenemann]

@automata the group itself does not require any ports if the layoutHierarchy option is active. Ports should be declared for the end points of connections. I recommend setting "de.cau.cs.kieler.portConstraints" to FIXED_ORDER for each node that has connections, and declaring both the "de.cau.cs.kieler.portSide" and "de.cau.cs.kieler.portIndex" options for each port. The latter must be set to an integer value such that the ports of a node are indexed in clockwise order, i.e. first east-side ports top-down, then west-side ports bottom-up. Alternatively to these two port options you can give each port a specific position relative to the node's top left corner and set "de.cau.cs.kieler.portConstraints" to FIXED_POS.

[automata]

@franchi82 thank you for all these valuable suggestions! Using LONGEST_PATH as nodeLayering results in a really nice layout now:

I'll try to implement FIXED_POS port constraint next.

[bergie]

Here is a complex graph from the NoFlo-based window manager @djdeath is building. Good test for the autolayout: https://raw.github.com/djdeath/noflo-clutter/master/graphs/ResizeWindowConstrained.fbp

As you can see, this demonstrates why we really need to implement edge routing:

(visualized using http://noflojs.org/visualize/ which is a snapshot of the work from @automata)

The same graph using the dagre algorithm in the graph editor by @alfa256:

[automata]

It is really an interesting example, thank you @bergie. I'm attaching a zoom-out version of the graph to make it easy to compare with dagre algorithm: it is interesting to see similarities between the two approaches.

KLay implements edge routing (I imagine @franchi82 can explain it better to us) but we do not have the bending points already implemented on our prototype. I agree we should go for it ASAP.

[automata]

Thanks to the help from an amazing team behind KIELER/KLay (Ulf, Florian, Chris, @franchi82) we have the JS binding to KLay (KlayGWT) working with our prototype.

It is not totally done (e.g. groups are not working yet). However, it layouts fast our example graph (each time the UI values change, the layout algorithm is applied to the entire graph again):

[automata]

Updated noflo/visualize to use KlayGWT, forked on http://automata.github.io/visualize/. Without group support we have the following layout for the test FBP:

[bergie]

@automata I'm getting these errors occasionally

[bergie]

@automata it seems GWT is not compatible with Chrome Packaged Apps:

We need to rebuild Klay with GWT 2.5.1

http://stackoverflow.com/questions/12123178/can-not-make-gwt-application-work-as-chrome-packaged-app-probably-due-to-csp

[automata]

Reported to Klay responsible Ulf Rueegg. I'll try to generate a build myself.

I have to investigate the TypeError, maybe it is related with the absence of klayinit() call.

[automata]

@bergie Ulf informed that Klay is already built using GWT 2.6.0. He is inspecting the use of document.write() by Klay.

[automata]

@bergie Ulf updated Klay using a different linker. I updated klay-js Bower component. Can you please rebuild noflo-ui using klay-js 0.0.2? It should solve the problem.

[bergie]

@automata that caused a new problem:

[automata]

@bergie I updated klay-js (v0.0.3) with the last changes from Ulf, can you please try again? If it doesn't work, I can reproduce it myself.

[bergie]

@automata still the same error

[automata]

@bergie can you confirm the error using klay-js 005?

[forresto]

Looks much better when I put the stray nodes in group:

before

after

Points to a bug or weakness of KLay: groups occupy a whole layer, pushing the singles far out.

I think it isn't a showstopper. Within groups, layout looks quite good. In this kind of situation, encouraging more groups = more code comments (map legends).

---

KLay issue http://rtsys.informatik.uni-kiel.de/jira/browse/KIPRA-1402?jql=project%20%3D%20KIPRA

[automata]

Other issues of interest on KLayJS:

• Chrome Packaged Apps: http://rtsys.informatik.uni-kiel.de/jira/browse/KIPRA-1397
• Snap to grid: http://rtsys.informatik.uni-kiel.de/jira/browse/KIPRA-1401
• Force nodes to stay in specific layers: http://rtsys.informatik.uni-kiel.de/jira/browse/KIPRA-1400
• Expose edge routing step: http://rtsys.informatik.uni-kiel.de/jira/browse/KIPRA-1403

[automata]

Got autolayout working for Chrome Packaged Apps with a workaround: we should copy the NNNN.cache.jsand clear.cache.gif files to the same directory of app.html. There's a warning about the use of eval by GWT but it works, as described. Should we consider to use it again?

[forresto]

Another center of graph layout research at monash:

• http://marvl.infotech.monash.edu.au/software/
• web port (typescript) http://marvl.infotech.monash.edu/webcola/
• grid snap http://youtu.be/b7nV8dvAlIc
• emscripten-ported libavoid.js https://github.com/worklez/avoid.js (3mb)

@automata experimented with webcola (physical constraints); doesn't seem like an improvement:

[bergie]

Implementing the circular Flux pattern shows that we clearly need edge routing.

Views ---> (actions) ----> Dispatcher ---> (registered callback) ---> Stores -------+
Ʌ                                                                                   |
|                                                                                   V
+-- (Controller-Views "change" event handlers) ---- (Stores emit "change" events) --+

Now it looks quite messy with the edge transmitting events from React to the NoFlo dispatcher:

[forresto]

Shorter loopbacks look better. I could tweak the edge drawing to use the distance to influence the control points.

[forresto]

[bergie]

@forresto that already makes it somewhat clearer to look at, but it would really be great if edges "avoided" other nodes

Can of course be made to look a bit clearer by slight graph reorg:

[automata]

With klay-js 0.0.8 we have some improvements on edge crossing on situations like:

... now we have:

The following is a comparative between the old auto layout (top row) and the new one (bottom row) using our example graphs:

However, in loopback cases we still need improvements:

We should expect more improvement with ORTHOGONAL edge crossing (we are using POLYLINE now):

But as well noted by @forresto we couldn't use snap-to-grid anymore because of the fixed position of bending points on edges.

[bergie]

@automata great! Would be awesome to get the config right for the looping connections too. And would be nice to add a little bit of space between groups so they don't overlap

[paulyoung]

Came across this and wanted to share in case there was anything useful involved: https://github.com/dhotson/springy

[forresto]

One thing nice from that demo is the animation. I'm going to revisit that once I move the-graph from SVG to canvas.

[paulyoung]

Fixed broken link in my comment.