Dot is slow for a medium-sized input (<2kloc)
Steps to reproduce
I generated some medium-to-large sized graphs with a tool I am working on. For most graphs dot takes <10 seconds to layout them. There's one specific situation that takes a lot more time (and its not a lot bigger really). I don't know if this is expected (maybe layouting costs grow cubically or something like that) or if I'm a lucky person that found an interesting edgecase.
Hope this report can help!
Expected Behaviour
Rendering should take 40 seconds at most? I don't really know...
Actual Behaviour
Rendering takes more than three minutes.
OS Version
Linux running on WSL
Graphviz Version
dot - graphviz version 2.43.0 (0)
libdir = "/usr/lib/x86_64-linux-gnu/graphviz"
Activated plugin library: libgvplugin_dot_layout.so.6
Using layout: dot:dot_layout
Activated plugin library: libgvplugin_core.so.6
Using render: dot:core
Using device: dot:dot:core
The plugin configuration file:
/usr/lib/x86_64-linux-gnu/graphviz/config6a
was successfully loaded.
render : cairo dot dot_json fig gd json json0 map mp pic pov ps svg tk visio vml vrml xdot xdot_json
layout : circo dot fdp neato nop nop1 nop2 osage patchwork sfdp twopi
textlayout : textlayout
device : canon cmap cmapx cmapx_np dot dot_json eps fig gd gd2 gif gv imap imap_np ismap jpe jpeg jpg json json0 mp pdf pic plain plain-ext png pov ps ps2 svg svgz tk vdx vml vmlz vrml wbmp webp x11 xdot xdot1.2 xdot1.4 xdot_json xlib
loadimage : (lib) eps gd gd2 gif jpe jpeg jpg png ps svg webp xbm
Additional info
Repro file attachedrepro.dot