New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

graph autolayout testing #53

Closed
forresto opened this Issue Dec 11, 2013 · 62 comments

Comments

Projects
None yet
8 participants
@forresto
Copy link
Member

forresto commented Dec 11, 2013

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

photobooth-noflo
noflo manual

yed-manual
yed manual

yed-organic
yed organic

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

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

@forresto

This comment has been minimized.

Copy link
Member

forresto commented Dec 11, 2013

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.

animate


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

This comment has been minimized.

Copy link
Member

forresto commented Dec 11, 2013

yeah, grouping is nice

photobooth-octi-ltr
l2r

photobooth-octi
t2b

@d4tocchini

This comment has been minimized.

Copy link
Contributor

d4tocchini commented Dec 11, 2013

+1

@forresto

This comment has been minimized.

Copy link
Member

forresto commented Dec 12, 2013

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 👎)

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

This comment has been minimized.

Copy link
Member

forresto commented Dec 12, 2013

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

@forresto

This comment has been minimized.

Copy link
Member

forresto commented Dec 12, 2013

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

@forresto

This comment has been minimized.

Copy link
Member

forresto commented Dec 13, 2013

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

This comment has been minimized.

Copy link
Member

forresto commented Dec 13, 2013

dagre seems like a good starting place. They might be working on grouping: dagrejs/dagre#13

Will ask about ports

@forresto

This comment has been minimized.

Copy link
Member

forresto commented Dec 13, 2013

@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.

ptolemy

@automata

This comment has been minimized.

Copy link
Member

automata commented Dec 13, 2013

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

This comment has been minimized.

Copy link
Member

forresto commented Dec 13, 2013

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

This comment has been minimized.

Copy link
Member

forresto commented Jan 8, 2014

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

@automata

This comment has been minimized.

Copy link
Member

automata commented Jan 10, 2014

First tests using KIELER/KLay service.

Original noflo graph:

captura de tela 2014-01-08 as 17 06 16

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

captura de tela 2014-01-08 as 17 05 32

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

captura de tela 2014-01-08 as 17 06 50

@automata

This comment has been minimized.

Copy link
Member

automata commented Jan 10, 2014

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

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

captura de tela 2014-01-10 as 15 37 38

@automata

This comment has been minimized.

@automata

This comment has been minimized.

Copy link
Member

automata commented Jan 10, 2014

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

kielerui

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

This comment has been minimized.

Copy link
Member

automata commented Jan 11, 2014

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

captura de tela 2014-01-10 as 23 01 32

Next step: groups/layers.

@automata

This comment has been minimized.

Copy link
Member

automata commented Jan 11, 2014

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

captura de tela 2014-01-11 as 02 18 50

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

@forresto

This comment has been minimized.

Copy link
Member

forresto commented Jan 11, 2014

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

screen shot 2014-01-11 at 1 02 04 pm

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

This comment has been minimized.

Copy link

spoenemann commented Jan 11, 2014

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

This comment has been minimized.

Copy link
Member

automata commented Jan 11, 2014

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

captura de tela 2014-01-11 as 13 04 46

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

This comment has been minimized.

Copy link
Member

automata commented Jan 11, 2014

@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

This comment has been minimized.

Copy link

spoenemann commented Jan 13, 2014

@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

This comment has been minimized.

Copy link
Member

automata commented Jan 16, 2014

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

captura de tela 2014-01-16 as 09 02 21

I'll try to implement FIXED_POS port constraint next.

@bergie

This comment has been minimized.

Copy link
Member

bergie commented Jan 30, 2014

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:

screenshot 2014-01-30 at 16 36 04

(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:

t2bwiq3

@automata

This comment has been minimized.

Copy link
Member

automata commented Jan 30, 2014

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.

captura de tela 2014-01-30 as 13 54 30

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

This comment has been minimized.

Copy link
Member

automata commented Feb 13, 2014

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):

fast

@bergie bergie added the enhancement label Mar 9, 2014

@automata

This comment has been minimized.

Copy link
Member

automata commented Mar 13, 2014

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

This comment has been minimized.

Copy link
Member

forresto commented Mar 13, 2014

Another center of graph layout research at monash:

@automata experimented with webcola (physical constraints); doesn't seem like an improvement:
captura de tela 2014-03-13 as 23 16 53

@bergie

This comment has been minimized.

Copy link
Member

bergie commented May 24, 2014

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:

screenshot 2014-05-24 at 05 42 36

@forresto

This comment has been minimized.

Copy link
Member

forresto commented May 24, 2014

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

forresto added a commit to flowhub/the-graph that referenced this issue May 25, 2014

@forresto

This comment has been minimized.

Copy link
Member

forresto commented May 25, 2014

screen shot 2014-05-25 at 2 21 24 pm

@bergie

This comment has been minimized.

Copy link
Member

bergie commented May 26, 2014

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

screenshot 2014-05-26 at 23 25 56

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

screenshot 2014-05-26 at 23 31 16

@automata

This comment has been minimized.

Copy link
Member

automata commented May 28, 2014

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

captura de tela 2014-05-27 as 22 40 51

... now we have:

captura de tela 2014-05-28 as 11 32 43

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

comp_autolayout

However, in loopback cases we still need improvements:

comp2

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

captura de tela 2014-05-27 as 23 57 41

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

This comment has been minimized.

Copy link
Member

bergie commented May 28, 2014

@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

This comment has been minimized.

Copy link

paulyoung commented Jun 13, 2014

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

@forresto

This comment has been minimized.

Copy link
Member

forresto commented Jun 13, 2014

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

@forresto forresto closed this Jun 13, 2014

@paulyoung

This comment has been minimized.

Copy link

paulyoung commented Jun 13, 2014

Fixed broken link in my comment.

@LowLevelMahn

This comment has been minimized.

@forresto

This comment has been minimized.

Copy link
Member

forresto commented Aug 27, 2018

@LowLevelMahn is that what's implemented in https://github.com/OpenKieler/elkjs ? KLay is deprecated in favor of ELK now.

@LowLevelMahn

This comment has been minimized.

Copy link

LowLevelMahn commented Aug 27, 2018

is that what's implemented in https://github.com/OpenKieler/elkjs

i can't find any relation/comparison to the CoDaFlow algorithm - different poeple involved, but also Kiel University - i don't know

KLay is deprecated in favor of ELK now.

saw that on the Klay Github page

@spoenemann

This comment has been minimized.

Copy link

spoenemann commented Aug 28, 2018

@uruuru, can you shed some light here?

@uruuru

This comment has been minimized.

Copy link

uruuru commented Aug 28, 2018

@LowLevelMahn

This comment has been minimized.

Copy link

LowLevelMahn commented Aug 29, 2018

cola.js is WebCola?

The parts that address further requirements for
dataflow-like diagrams are not included in any release.

why - never reached a usable state?

@uruuru

This comment has been minimized.

Copy link

uruuru commented Aug 29, 2018

@LowLevelMahn

This comment has been minimized.

Copy link

LowLevelMahn commented Aug 29, 2018

The implementation was in Java using customized c++ libraries of the stress
layout. We simply couldn't see a release strategy that seemed sensible and
maintainable for us.

so the layout algorithm is good but not good enough to invest more time in finding a proper release strategy or port the C++ parts to Java - to become part of ELK in the end?

@forresto

This comment has been minimized.

Copy link
Member

forresto commented Aug 29, 2018

@LowLevelMahn chill. Open source maintainers are under no obligation to do anything that isn't in their own interest. They published a paper and didn't feel like porting it to ELK. Somebody else can do that, or make a new library.

@LowLevelMahn

This comment has been minimized.

Copy link

LowLevelMahn commented Aug 29, 2018

@forresto
sorry it wasn't my intention to sound harsh in any way

@uruuru
would it make sense to port the c++ code to java? or does codaflow never fully get out of the proof of concept phase?

@uruuru

This comment has been minimized.

Copy link

uruuru commented Aug 29, 2018

@LowLevelMahn

This comment has been minimized.

Copy link

LowLevelMahn commented Aug 30, 2018

what about releasing it "as is" on github as a (small) first step - with your last comment as README.md :)
so people like me reading the paper/slides about CoDaFlow can find some related material

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment