Graph autolayout

[bergie]

Currently graph editing can be a bit fiddly, as you need to play a lot with the positioning of nodes to make the graphs look nice.

A lot of this could be automated by the work done in the CS community on various autolayout algorithms, and especially the ones intended for solving metro map layouts, as mentioned in my post on NoFlo UI

[d4tocchini]

The proverbial can of worms.

There are many flavors of "autolayout". We've talked a lot about subway map style layouts, and there's the more traditional flowchart perspective. We need to accommodate several layout possibilities so the best naturally emerges through the crucible of use.

To confound matters, it all needs to be interactive. But, how do we balance auto-layouts with user intervention? This paper on GLIDE, an interactive constraint-based editor for drawing small- & medium-sized graphs, seems to at least capture the nomenclature of the problem.

As for subway map style graphs, here are some cool papers:

• The Metro Map Layout Problem
• @bergie the link from your Noflo UI post about Automatic Generation of Transit Maps has a ton in it
• Metro Map Layout Using Multicriteria Optimization
• Line Crossing Minimization on Metro Maps

[forresto]

I like how it looks with a simple horizontal / 45° limitation.

To code that, I was trying to make something more general, but ended up with https://github.com/meemoo/dataflow/commit/b807a035bd9410a4d7cc70f405beba1e01ffb473

With this simpler implementation we could keep track of which vertical and horizontal segments (cable tracks) are occupied, then shift the control points over if needed.

[bergie]

@forresto that is a great start! The 45° limitation certainly brings this closer to subway maps and circuit boards in how it looks.

For autolayouts there are two things:

• Positioning of nodes (including snap to grid)
• Drawing of the connectors to minimize intersections

@jpaulm solved this by making the control points of connectors also manual in DrawFBP. But the more we can automate here the better. Programmers using FBP should be able to spend their time thinking about the logic of the graph, not the looks of it ;-)

[d4tocchini]

For the positioning of the nodes, if we go with a Constraint-Based solution, which we should, we just need to succinctly describe a system of rules / constraints that does what we want, that's the hardest part, thereafter we choose our constraint solver(s). Cassowary would be the solver of choice if we can describe the system in terms of linear weighted inequality statements that might sound like:

x of every node should STRONGLY be GREATER THAN 150 plus the x of inport connected nodes;

By using weighted expressions, or "hierarchal constraints", the system can de described in a much more fluid natural way. Such is the beauty of Constraint Programming, worry about the what not the how b/c the how is too hardcore =)

@bergie we can start using the Cassowary stuff we were working on for this, even the CCSS parser would help. We just need to setup a playground for us to experiment in... After we update the CommandArray let's do this!

The layout pass for node topology would iterate through each node and add constraints, the solver would then solve and spit out the positions. By using Cassowary's Weights, Strengths and edivVars we handle interactive manipulation like GLIDE.

[forresto]

Auto edges and auto nodes are should be considered separately. I think that auto edge routing should be on by default, but nodes should stay where you put them (or snap to grid). Then you could select some or all nodes and tell them to clean up.

[bergie]

@forresto fully agreed, by default nodes should be where you put them, but maybe with a bit of snap-to-grid.

But node autolayout would also be useful for situations where you start with a graph without locations (for example, one defined in FBP language)

[kallekarkkainen]

I've worked on a DSVL like this before, and during that time I implemented one of the tree layout algorithms for the automated node positioning. I had two edge models (bezier and 90deg), and with those the tree layout worked really nice. One of the best features there was that multiple applications of the button always gave predictable results, which might not be true in all algorithms. That said, I've not implemented Cassowary, and can state nothing factual about the constraint system. The compsci and programming reddits have had some interesting details about older aesthetic tree layout algorithms, as well as links to some research from the '90s. I can say, that implementing one of those algorithms is a breeze, quick to get going.

Here's a link to a screenshot of what I did back in 2010 (some of the text is in finnish, sorry). That stuff was used to analyze the assets and risks for some energy companies. It's a development screenshot, so it's not really polished. In this picture we have a sub tree from a larger set, where some time series are prepared for further calculation.

[bergie]

Here is also some interesting stuff (in Finnish): https://github.com/i-tu/Kandi/blob/master/kandi.pdf?raw=true

[kallekarkkainen]

the last sentence before summary is very true:

it is doubtful that a person could produce as clear a picture with such a complex graph.

That was my experience creating those complex layered calculation and behavior patterns. It got messy quite quickly, and adding extra things later tended to completely change how the graph should be laid out.