How can I make DOT/neato graphs more compact without introducing overlap?

Question

My question is essentially the same as this one but the given answer doesn't work for me.

Here is a sample rendering (source) with

compound=true;
overlap=scalexy;
splines=true;
layout=neato;

There is some unnecessary overlap in the edges but this isn't too bad, the main problem is all the wasted space.

I tried setting sep=-0.7; and here's what happens.

The spacing is much better but now there is some overlap with the nodes. I experimented with different overlap parameters and this is the only one which gives remotely acceptable results.

I tried changing to fdp layout and setting the spring constant attribute K globally but I just got stuff like this:

The source is all straightforward a--b--c sort of stuff, no fancy tricks.

What I want is for all edges to be shortened as much as possible (up to a minimum) provided that this adjustment doesn't introduce any new overlaps, which is where sep fails completely. That doesn't seem like it should be too hard for a layout engine to do. Is it possible with the graphviz suite? I don't mind changing rendering software, but I don't want to annotate the source on a per-node or per-edge basis.

My ideal result would be to minimize the deviation in edge length, considered one node at a time, i.e. each node would have edges of equal length apart from the necessary exceptions, but that's wishful thinking. The priority is to reduce the length of each edge with the constraint that this cannot introduce overlap.

I will accept partial solutions but they must be fully automatic and open source.

How can I do this? Thanks.

Liliuokalani

Same problem. Neato seems to be the layout I want but it is mostly unconfigurable. – Caesar

Answer 1

I found https://sites.google.com/site/kuabus/programming-by-hu/graphviz-test-tool, an interactive tool for parameterizing the many options and repeatedly rendering them. I went through the full list provided by the Java application, eventually ending up with this set of attributes:

overlap=false
maxiter=99999999
damping=9999999
voro_margin=.001
start=0.1
K=1
nodesep=999999999999
labelloc=c
defaultdist=9999999
size=20,20
sep=+1
normalize=99999999
labeljust=l
outputorder=nodesfirst
concentrate=true
mindist=2
fontsize=99999999
center=true
scale=.01
inputscale=99999999
levelsgap=9999999
epsilon=0.0001

I was not able to find a parameterization of neato that made producing the desired "moderately scaled" graph possible.

Caesar

the site is not found. In the Resources | Graphviz page it says the project is abandoned – Rind

Answer 2

You should set

overlap = compress;

this should compress it at much as possible. Try sep = +1; first, and then play with values between 0 and +1 to find the optimal setting for you.

Ejaculatory

They're all overlapping like crazy, even when I try large values for sep. – Liliuokalani

What value of K are you using? – Ejaculatory

Try keeping sep=1; but diminushing the spring strength. So try K=0.3 (the default) and then gradually increase that value. – Ejaculatory

Thanks for the suggestion, I will tinker, but the programmer in me knows that shortening the sparse no-collisions image I already have without introducing new overlap is algorithmically possible. I'm afraid this answer doesn't look like it qualifies. – Liliuokalani

You're welcome. And yes, it is definitely possible! It shouldn't be overlapping, that is why I am suspecting that your K value is too small. – Ejaculatory

I've been trying sep and k in the region of 100-1000 and they seem to be having no effect whatsoever. – Liliuokalani

I'm using graph Foo { compound=true; overlap=compress; sep=-0.7; splines=true; layout=neato; and the rest is just plain nodes and edges. – Liliuokalani

k in graphviz is inversly proportional to the spring constant in physics: ẍ = - k* x so I guess that at anyhting more than 100 you basically have 0 spring force in your edges so it makes no difference. Make sure you don't put the same value for sep and k, vary them independantly. If you are putting k=1000 and positive sep and they are still overlapping like crazy I'm at a lost. Then I would keep it simple and use one of the interactive viewers to move the nodes around by hand: graphviz.org/content/resources – Ejaculatory

I am in the same boat - the majority of parameters for neato seem to have no effect at all. Only overlap, which, if true causes everything to draw on top of it, and if set to any other value causes everything to be drawn with extremely long edges between nodes. – Caesar

Answer 3

I have a graph with 50 nodes and 68 edged (sorry cannot publish the whole picture, just a fragment). Found two reasonable presets (1 and 2):

digraph {
graph[
# 1. Less overlaps but less compact.
# This is the choice for now.
layout=neato; overlap=prism; overlap_scaling=-3.5; 

# 2. More compact but some overlaps exist (may be adjusted by `sep`).
#layout=neato; overlap=voronoi; sep=-0.15; 

# The following is common.
outputorder=nodesfirst, # Will always draw edges over nodes.
splines=curved;
]
node[fontname="Helvetica",];
node[shape=box;style="filled";penwidth="0.5";width=0;height=0;margin="0.05,0.05"];
edge[label=" ";color="#000080";penwidth="0.5";arrowhead="open";arrowsize="0.7";];
. . .
}

Neptunium