Plug a graph drawing framework into GraphEdit, for automatic layout and routing

[umarcor]

Describe the project you are working on:

The main mechanic of a tool I'm prototyping is an schematic editor. There is a logical problem/puzzle that needs to be solved by combining pre-existing blocks/modules with given functionality and inputs/outputs.

Hence, the use case has virtually no difference compared to any other usage of GraphEdit, including the Visual Editor in godot.

Several in-progress PRs apply to GraphEdit (godotengine/godot#37227, godotengine/godot#40043, godotengine/godot#40322), but none of them conflicts with this request from a feature point of view. However, code conflicts might exist.

Describe the problem or limitation you are having in your project:

In complex schematic diagrams, laying all the blocks in a left to write flow is inneficient. The vertical space can be better used by laying the blocks in several rows (a grid). Furthermore, clustering can significantly aid in providing an easy to understand layout/graph.

However, current connections are splines or bezier curves. As a result, feedback connections (the ones going from right to left) are drawn below the blocks/nodes/modules. On the other hand, clustering seems not to be supported.

Describe the feature / enhancement and how it helps to overcome the problem or limitation:

Many libraries exist for automatic layout and routing of diagrams, since it is a complex task that has been throroughly studied. The proposal is to pick one that is compatible with godot, in terms of licensing. Then, provide some acceptable defaults/presets in GraphEdit class/node.

Describe how your proposal will work, with code, pseudocode, mockups, and/or diagrams:

In the following references, multiple layout algorithms are shown:

• https://ogdf.uos.de/wp-content/uploads/2019/04/ogdf.pdf
• http://rtsys.informatik.uni-kiel.de/%7Ebiblio/downloads/theses/msp-dt.pdf

From godot's user's point of view, there would be 1 or 2 options added to the 'GraphEdit' section of the 'Inspector', just below current 'Use Snap' or 'Zoom':

• Layout: algorithm used to position the nodes in the graph. Defaults to 'unset' or 'manual'.
• Router: algorithm used to draw the connections between nodes in the graph. Defaults to 'unset', 'splines' or 'bezier'.

Optionally, clustering would be supported. I believe a new node class would need to be written. From the usage perspective, users/developers/players would select a group of GraphNodes and would click an option to "Create cluster". There are two possible types of clusters:

• Transparent: a box is drawn in the diagram, but connections are not changed.
• Node/entity: ports are added to the cluster for each ingoing or outgoing connection; then existing connections are broken/split, for making them pass through the ports of the cluster.

If this enhancement will not be used often, can it be worked around with a few lines of script?:

My main concern is routing of connections. I believe it is currently not possible to override how connections are drawn by GraphEdit. I assume that rewriting the class from scratch might be needed.

Regarding layout algorithms, there is #1253 where implementing 6 different algorithms is proposed. Should any of those be significantly different from the ones available in existing libraries, I wonder whether contributing them there might be a better long-term approach.

I think that clustering is NOT a priority. I mentioned it because it is thoroughly covered in some of the references, and it would come handy. Nevertheless, I believe that improving routing and layout are the relevant enhancements, in that order.

Is there a reason why this should be core and not an add-on in the asset library?:

Having a "nice" schematic editor combined with godot's engine and assets is an unvaluable framework for gamification of all kinds of subjects. Schematic graphs/diagrams are used in many areas of engineering for communicating knowledge between programmers/designers and other developers. With GraphEdit, most of the functionality is already there. The only missing feature for working with large/complex graphs to be pleasing is a well-thought layout and routing solution.

Hence, it might be possible to duplicate GraphEdit, should making godot dependent on any external library be unacceptable. Otherwise, I believe that all the current users of GraphEdit would benefit from the enhancement being built-in.

Ref #506 #593 #1159

OGDF

OGDF is a long going open source project developed by several international research groups. It stands both for Open Graph Drawing Framework (the original name) and Open Graph algorithms and Data structures Framework.

OGDF is a self-contained C++ library for graph algorithms, in particular for (but not restricted to) automatic graph drawing. It offers sophisticated algorithms and data structures to use within your own applications or scientific projects.

• ogdf.uos.de
• github.com/ogdf/ogdf
• https://ogdf.github.io/doc/ogdf/index.html

d3-hwschematic

Regarding minimization of crossings, "see On the Automatic Layout of Data Flow Diagrams by Miro Spönemann, referenced in ghdl/ghdl#111:363395770 by @Nic30 (see Nic30/d3-hwschematic). See also Nic30/d3-wave and (RTL) Schematic view" (from f4pga/ideas/issues/41).

[umarcor]

Our best practices for engine contributors recommend not to use complex canned solutions for simple problems.

I'm sorry to disagree, but describing automatic layout and routing of dataflow diagrams as a "simple problem" feels like a not-very-thought point. I believe this is the kind of feature where using an external solution (simple or complex) is a better approach than reinventing the wheel.

Of course, your are entitled not to support any kind of automatic layout and routing, precisely because it is a complex problem.

Either way, the library's license makes it unsuitable for inclusion in Godot, so I'll close this. It can still be implemented as a third-party effort. We don't want to link the Godot editor (or worse, exported projects) to any (L)GPL-licensed libraries as we want it to remain usable under MIT terms, without any third-party libraries encumbering this.

This is a fair point. On the one hand, exceptions exist, as the reference shows. On the other hand, I think that other (maybe simpler) similar projects with different licensing requirements can be evaluated.

The point about using an external solid project instead of a custom solution still holds. Moreover, the main point in this issue (providing alternative routing options selectable in the GUI) remains too. Hence, I would like this issue to be reopened and unarchived. I will remove explicit references to OGDF in the title and in the main body.

PS: Please do not mass-mention people in proposals.

Please, do explain it in the README. "It is up to you to draw interest in your proposed feature" lead me to think that it was, indeed, recommended.

[fire]

Looking at the license, despite how great the library is if the library requires the entire project to be relicensed to be GPL / LGPL it won't be accepted sadly.

I think there's an EPL license library from Eclipse, but is in Java. Keep the community posted if you find any good candidates.

[Edited]

I am a contributor to the #1253 proposal.

[Nic30]

ELK, OGDF, adaptagrams, etc. are libraries which can generate a layout of layered graphs. Result of each one of them is mostly suboptimal. Each library has hundreds of parameters which can tune the process up. ELK in default configuration has eta 40 layout generation steps responsible for specific situations which may appear.

I mean it is very complex task.

I would recommend to use JNI or transpile ELK to c++ directly, because there is a little choice left.
This would be very ugly solution, definitely. But it was done for javascript version of ELK and it is frequently used now and it works reliably. (ELK API is json like, that is why it is easy to do such a things.)

[umarcor]

Otherwise, there's not much point in reopening it just yet.

My point is that it is precisely useful for gathering users interested in finding a suitable candidate or ad-hoc solution for automatic routing and/or layout. That has been commented/referenced directly or indirectly in over a dozen issues already.

It's considered good nettiquette to only ping people if you actually need to 🙂

I believe I had to. All of them were (and I assume still are) interested in a solution that modifies how connections are currently handled in GraphEdit. Some of them were/are concerned about the slot/port terminology, which translates directly to what an external tool needs to be given. Others have already proposed or reacted to ad-hoc solutions.

Most contributors are volunteers and may already be watching this repository anyway.

ccing was not meant for reading, but for asking a reaction/comment. There was an explicit criteria for asking those people, and not other.

[Lexpartizan]

Yes, I am interested in making working with slots and ports much more transparent, clear and easy. Since I want to make a graphNode with a configurable number of outputs and I need an exact match between slots and ports. Of course, it would be possible to circumvent or solve this problem with user code, but such functionality should be by default, as I think the Ports and slots should be uniquely linked. It's good that You let me know about this proposal.

[TheDuriel]

I'm fully in support of adding a library with a compatible license, and thus giving graphedit a much needed refresh.

(And yeah, the list of people pinged is rather spot on)

[fire]

Please see if the implementation suits your needs #1253

[fire]

Fixed by: #1253