🚧 Generating an automatic Graph layout

[emmenlau]

I'm under the impression that QuickQanava currently does not do any automatic graph layout, is that correct? Or did I overlook something?

I've found that there are some Javascript libraries around that could be a cool combination with QuickQanava for this task. For example https://github.com/dagrejs/dagre is MIT licensed, and does only do layout, no rendering. So it should fit very well with QML and QuickQanava. The getting started example is almost trivial: https://github.com/dagrejs/dagre/wiki#using-dagre

Would that be something that can be considered? I may be able to help with such an (optional) integration, if that is something worthwhile for QuickQanava?

Or what is your overall take on the subject?

[cneben]

Hi @emmenlau sorry again for the answer delay, currently having too much work for serious open source contributions.

QuickQanava initially include c++ tree layout algorithm and a custom "force-spring" implementation (10 years ago!). I remove that code because:

• It was synchronous and there is no trivial strategy to execute it in a separate thread (locking or inefficient full graph copy)
• Adding locking on nodes x/y/width/height properties has significant cost even for users not interested in auto-layout.

I have more and more interest for auto-layout recently especially for force spring and tree layout algorithms (not necessarily an "online/progressive" version) for a private use-case, so we might consider putting effort in it.

Have you actually tried to import and use a packaged version of Dagre from QML ?

[emmenlau]

Thanks for the thumbs-up, @cneben !

I have not tried using Dagre from QML yet, but I'm very interested in that. In the past, I did use some pure Javascript libraries from QML, and in the cases that I tried, it was quite easy to get something up and running. However I think I will not have time this or next week.

Let me know if you will take a look, and otherwise I'll go for it sooner or later...

[emmenlau]

I have been considering this for a bit more, and here are my thoughts so far. I think adding Dagre as a javascript library is most likely not too hard, and neigher should be using Dagre to generate a graph layout.

I would assume that the main effort is in integrating the automatic graph layout together with manual graph layout in a sensible way. I.e. some relevant questions:

• Should the automatic layout only be triggered with some manual action, like a button click or key press? This would be important to avoid messing up a manual layout that the user wants to preserve.
  • What is sensible for example when adding new nodes? Should they be placed using automatic layout? But this may mess up the current (manual) graph layout completely, hard to predict...
• It may be helpful to combine automatic layout with Qt animations, so that nodes are moved to new positions, rather than jumping to new positions. Otherwise it can be quite hard for the user to see what is going on...

Just my two cents...

[emmenlau]

Just a small update on this: We tried using dagre in QML, but failed, due to the newer Javascript version that is not fully supported by the QML engine. See dagrejs/dagre#450 for more info.

If you know a bit more about Javascript, it would be very interesting if this can be made to work...

[cneben]

I will have a look, but transpiling seems like the good strategy.

I've added a new "layouts" sample, it should be considered as an experimentation for now, but i am already using the (synchronous) tree layout algorithm in production.

In fact, porting "Force Atlas2" or "Spring force" layouts from Js is quite easy, but a lot of glue code is necessary to do it asynchronously and control the "refresh rate" of the QML scene graph, since there is no other options than copying an array of laid out item coordinates.

I will give Dagre a try, but my first option is still a full c++ implementation.

[emmenlau]

I will have a look, but transpiling seems like the good strategy.

It would be super awesome if you have a bit of knowledge there! We added transpiling based on recommendations from ChatGPT, but without real insight into what we're doing :-)

I've added a new "layouts" sample, it should be considered as an experimentation for now, but i am already using the (synchronous) tree layout algorithm in production.

In fact, porting "Force Atlas2" or "Spring force" layouts from Js is quite easy, but a lot of glue code is necessary to do it asynchronously and control the "refresh rate" of the QML scene graph, since there is no other options than copying an array of laid out item coordinates.

I will give Dagre a try, but my first option is still a full c++ implementation.

Awesome! A full c++ implementation is certainly great! In case that may be interesting for you, I've been using https://github.com/bigno78/drag as a BSD-licensed C++ layouting library so far, and it also gives quite ok-isch results.

In my humble opinion, having dagre as an option would be mostly for completeness sake - dagre is well maintained, quite mature, and provides many existing layouts, so it is certainly a very powerful base. If specific algorithms exist in c++ (with improved runtime, strict typing, static code checks, etc...), all the better!

[cneben]

Could you communicate about your preferred use case ? Are you talking about laying out an undirected graph (such as social network graph) or is it about laying out some kind of "directed flow graph" with horizontal / vertical constrains ?

[emmenlau]

Our use case are unweighted directed flow graphs, that represent data flow in a data analysis application.

The final result, that the user constructs, should always be an acyclic graph. But during construction, users may add cycles, and we have not decided if cycles are allowed in the UI (but highlighted as a problem), or if cycles is forbidden alltogether.