Overlapping nodes and cut off graph, even though overlap is set to false

This code generates overlapping nodes and cut off graph, even though I have set overlap=false. Why is that?

I get an overlap-free layout when I run graphviz neato.

What command line, OS, and version of Graphviz are you using?

I’m on Windows 11. The command is simply neato -Tpng .\test.gv -O

Here is the full output of neato -v:

neato - graphviz version 2.49.1 (20210923.0004)
libdir = "C:\Program Files\Graphviz\bin"
Activated plugin library: gvplugin_neato_layout.dll
Using layout: neato:neato_layout
Activated plugin library: gvplugin_core.dll
Using render: dot:core
Using device: dot:dot:core
The plugin configuration file:
        C:\Program Files\Graphviz\bin\config6
                was successfully loaded.
    render      :  cairo dot dot_json fig gdiplus json json0 map mp pic pov ps svg tk vml xdot xdot_json
    layout      :  circo dot fdp neato nop nop1 nop2 osage patchwork sfdp twopi
    textlayout  :  textlayout
    device      :  bmp canon cmap cmapx cmapx_np dot dot_json emf emfplus eps fig gif gv imap imap_np ismap jpe jpeg jpg json json0 metafile mp pdf pic plain plain-ext png pov ps ps2 svg tif tiff tk vml xdot xdot1.2 xdot1.4 xdot_json
    loadimage   :  (lib) bmp eps gif jpe jpeg jpg png ps svg

Oh oh! Works fine on my Linux system, but overlaps on Windows.
It gives a font warning on Windows, but I’m doubtful that that is the primary problem.

(neato.exe:29384): Pango-WARNING **: couldn't load font "SVN-Avo Not-Rotated 14", falling back to "Sans Not-Rotated 14", expect ugly output.  

Here is Windows result after removing all font-related specifications:

Here is Linux result with no changes to input:

It seems likely that the Windows executable was built without libANN, that is needed by the overlap removal phase. We have had some problems in the past, as libANN is not a very popular library, and the rest of the world has moved to other implementations of an Approximate Nearest Neighbors algorithm library. None have exactly the same API as the one we’re using, so modifications will be required. I’m certain had some discussions about this problem, either in forums, or over in gitlab issues, but now I can’t find it.

I created issue 2266 - Windows executable was built without libANN (#2266) · Issues · graphviz / graphviz · GitLab
Somewhere we should also document this problem & maybe suggest work-around(s)

There’s a fairly recent message in PyPi pykdtree · PyPI mentioning that a header file is missing for building libANN in Windows-64 and is available in … anaconda. I spent 5 or 10 minutes looking for a credible provider to download libANN for win64 (trying various synonyms like Windows 64 and Windows x64) and it was fruitless.

I spent 5 or 10 minutes looking for a credible provider to download libANN for win64 (trying various synonyms like Windows 64 and Windows x64) and it was fruitless.

What is the goal here? The libANN source is available at Index of /releases/libann/. Someone with a Windows machine simply needs to build a version of this on x86-64 Windows for the Windows dependencies repo. Maybe I’ve been unclear about this in past discussions? The solution is trivial. But it requires a Windows machine, something the majority of maintainers do not have.

I don’t think its related to libANN - the layouts are working fine in the WASM version and I don’t include the ANN sources…

Graphviz Quick Test / Gordon Smith / Observable (observablehq.com)

You’re right, it’s mingle that needs libANN. I’m confusing libANN with GTS, the GNU Triangulated Surface library. GTS is needed for overlap removal in neato and similar layout programs. I wonder if its missing in the win64 build environment that we use.

I think GTS is only used in smyrna?

Needed to construct the Delaunay triangulation of node positions to preserve the overall layout shape while removing overlaps, as described in a study by Gansner and Hu, http://yifanhu.net/PUB/overlap.pdf

Interesting - FWIW I am not building with GTS or Triangle currently, sounds like I should be…

Adding Triangle support is easy enough, GTS looks like it would be a pain as it has quite a few dependencies (glib pcre etc.) all of which need to be recompiled with a wasm target…
If anyone has an example where Triangle should improve the layout, I would like to do a side by side compare to see the difference (curious now).

Ah if it’s not libANN’s absence but rather GTS’ absence, this makes more sense. GTS does not appear enabled in any of our Windows CI environments (not in the Windows dependency repository, nor installed via Chocolatey, nor installed for MinGW, nor installed for Cygwin). Curiously the Smyrna Visual Studio files unconditionally claim to have GTS, but I suspect this does nothing because all the HAVE_GTS-guarded code is outside Smyrna itself.

There were a series a MRs trying to resolve this a while back.¹ We knocked them back for reasons that boiled down to not wanting to copy-paste the GTS source code into the Graphviz repository. This reason still stands. While I can appreciate wanting a triangulation-enabled build of Graphviz on Windows, we can’t afford to vendor and compile GTS. Our Windows CI builds are right on the Gitlab limits, and this would almost certainly push them over. As I said at the time, the correct solution to this problem is to propose a GTS package for inclusion in Chocolatey.² Then we can install this prebuilt in CI and the Chocolatey Graphviz package can declare a dependency on this.

¹ !2216, !2234, !2236, !2329
² Or whatever happens to be the in-vogue package manager of the day for Windows. We predominantly use Chocolatey in CI, but Gitlab provide a variety of Windows package managers pre-installed. I can’t seem to find the docs page that lists them all right now.

FWIW - GTS is available in the “vcpkg” package manager, which seems to be the most comprehensive package manager for windows (but only for c/c++ libraries, not for applications). It has the added benefit of also being compatible with OSX / Linux etc. - assuming the package in question supports those environments.

The main downside (from a CI point of view) is that it builds all the libraries (and their dependencies) from scratch, but it does support caching these built libs in a variety of ways.

Back to the OPs issue: The WASM version appears to be rendering the graph as expected and it does not include ANN, GTS or Triangle currently:

Graphviz Quick Test (v5.0.1) / Gordon Smith / Observable (observablehq.com)

Neither GTS nor triangle.[ch] is necessary, but they are useful for various special features such as overlap removal. From a functional point of view, either works fine. We can’t recommend using triangle.[ch] as it is not covered by the Graphviz license, but if someone wants to build using it, we can’t stop them. :grinning:

I thought at one time we noted both possibilities on the (old) web site, but I can’t find any reference to the triangle option now.

Maybe this is a silly question, but do we really expect people to copy triangle.[ch] into the source tree prior to compiling? The build system still supports this, but I’m not aware of anyone using this (including all our CI tasks). With a modern toolchain, I’m not aware of any benefits of this approach compared to simply linking against libgts with LTO enabled.

Perhaps not, but it has been done. Certainly if you have easy access to GTS, it would be silly, but a previous comment in this thread noted that using GTS could be a pain. If you have a package manager to bring in GTS easily, that’s the way to go.