does dot layout optimization work not perfect

With the following code I get a graph where the line from b04 to a18 crosses the whole graph and the nodes following the node a18 are printed on the right side but they would perfectly fit on the left side, avoiding one crossing and making the line b04 to a18 much shorter. (see attached example). Can this be considered as a bug in the dot layout engine or is there an other explanation for this behaviour? Are there any parameters to change this behaviour of dot?

Graph {
a01 -- b01
a02 -- b01
b01 -- a03
b01 -- a04
b01 -- a05
a03 -- b02
a06 -- b02
a07 -- b03
a08 -- b03
b03 -- a06
b02 -- a09
a10 -- b04
a11 -- b04
b04 -- a08
a05 -- b05
a12 -- b05
b05 -- a13
b05 -- a14
b05 -- a15
a16 -- b06
a17 -- b06
b06 -- a12
b04 -- a18
a18 -- b07
a19 -- b07
b07 -- a20
a20 -- b08
b08 -- a21
a22 -- b08
a23 -- b09
a24 -- b09
b09 -- a16
a04 -- b10
a25 -- b10
b10 -- a26
a27 -- b11
a28 -- b11
b11-- a25
}

 

AttachmentSize
example.jpg63.11 KB

does dot layout optimization

Minimizing the number of crossings is computationally very expensive, so most dot-like layouts use some heuristic that tries various things for a while and then quits. As heuristics, you can usually find some graph that can defeat them. So this isn't a bug but a known limitation, trading speed for layout quality.
 
Dot does provide the mclimit parameter which can induce more attempts to reduce crossings but heuristics can get stuck in certain configurations.
 
The various algorithms in dot are sensitive to the graph's input order (this is a feature). When dot constructs the initial ordering of nodes in ranks, it will start with the first vertex a01. As a look at the output suggests, this will probably cause a layout that will be hard to untangle. If you move edges so that the graphs starts like
 
Graph {
a10 -- b04
a11 -- b04
b04 -- a18
a18 -- b07
a19 -- b07
b04 -- a08
a01 -- b01
 
you get a better starting order and the unnecessary crossing is gone.

mclimit and maxiter don't help :-(

Thank you for the explanation. Yesterday in the evening I discovered the attributes mclimit and maxiter in the dot documentation. I hoped that they would solve my question but they didn't. I increased these parameters up to values of 10000 without eliminating the additional crossing. When I start dot from command line with the -v parameter it is visible that dot increases the effort to remove crossings but without success. It seems indeed that the algorithm is stuck, as you wrote. I there any hope to get better results with higher values?

Changing the order of my nodes and edges is not so easy in my real world problem. What I have shown in my first posting is only a simplified example. I have records in a database that are connected somehow and I wrote a script to generate a dot input file from those records. When I want to eliminate additional crossings I have to do same preprocessing to optimize the order of the records in the database output. I hoped that dot would do this optimization for me.

Recent comments