[dot] Segfault when setting nodesep to 0.3

[chtenb]

The following graph gives a segfault when doing a dot layout. (tested with windows 7)

digraph "Graph 76b00d8f-11c3-463d-ad26-29f5d68c9008" {
	graph [ nodesep=0.03 ];
	node [ shape=point ];
	subgraph "rank-target" {
		graph [rank=same];
		"A";
		"B";
		"X";
	}
	"A" -> "X";
	"B" -> "X";
}

$ cat dump.dot | ./dot.exe -Tsvg -O
Segmentation fault

When increasing the nodesep to 0.4, the following messages appear.

$ cat dump.dot | ./dot.exe -Tsvg -O
libpath/C:\Users\Chiel.tenBrinke\Projects\graphviz\lib\pathplan\shortest.c:324: triangulation failed
libpath/C:\Users\Chiel.tenBrinke\Projects\graphviz\lib\pathplan\shortest.c:207: cannot find triangle path
Warning: Unable to reclaim box space in spline routing for edge "A" -> "X". Something is probably seriously wrong.

According to http://www.graphviz.org/doc/info/attrs.html#a:nodesep, the minimum value is only 0.2.

[yarko]

...just trying this:

$ dot -Tjpg -O test.dot

on graphviz current HEAD, it doesn't segfault (on Ubuntu 16.04), but does issue the following:

$ dot -Tjpg -O test.dot 
libpath/shortest.c:324: triangulation failed
libpath/shortest.c:192: source point not in any triangle
Error: in routesplines, Pshortestpath failed
Error: lost A X edge

and generates a viable (correct?), but not interesting image.

0.2, 0.3, and 0.4 produce viable images, with no messages for me. However, with your test as supplied:

$ dot -Tpng -O test.dot 
libpath/shortest.c:324: triangulation failed
libpath/shortest.c:192: source point not in any triangle
Error: in routesplines, Pshortestpath failed
Segmentation fault (core dumped)

$ dot -Tsvg -O segfault.dot 
libpath/shortest.c:324: triangulation failed
libpath/shortest.c:192: source point not in any triangle
Error: in routesplines, Pshortestpath failed
Segmentation fault (core dumped)

Also dumping core:

• -Tdot
• -Teps
• -Tjson
• -Tpdf

... and many others;

Producing, w/ errors:

• -Tbmp
• -Ttiff

None of the above core-dumping invocations showed any trouble (produced viable output, no core) with nodesep=0.2.

[emden]

Roughly, the problem is arises because of the small size of the nodes and the small separation. There is an error in the code that generates the polygon that is used for routing the edge. The polygon is self-intersecting, hence the triangulation algorithm fails.