In DOT graph, how to move cluster and prevent lines crossing needlessly?

Question

I'm using Graphviz to generate this diagram:

The output is not optimal. An XZ line needlessly crosses an XY line; I would expect Y to be above X. I've tried many options from the doco but to no avail. This is the kind of output I am expecting:

How can I get Graphviz to produce better optimised diagrams?

NOTE: I'd like to automate the generation of similar diagrams so solutions specific to the scenario above (eg. invisible edges from X0 -> Y1, Y11 -> X03 or whatnot) wont help. I'm looking for a way to be able to generically trust things like:

• A-X-B will be a straight line.
• Y will be above A-X-B if it doesn't interact with Z.
• X->Y->X wont needlessly cause large gaps between X nodes.

---

The dot file content is:

digraph G {
  rankdir=LR

  subgraph cluster_x {
    node [style=filled,color=green]
    "X.0" -> "X.0.1" -> "X.0.2" -> "X.0.3" -> "X.0.4"
  }

  subgraph cluster_y {
    node [style=filled,color=lightblue]
    "Y.1" -> "Y.1.1"
  }

  subgraph cluster_z {
    node [style=filled,color=crimson]
    "Z.1" -> "Z.1.1"
    "Z.2"
  }

  A -> "X.0"
  "X.0.1" -> "Y.1"
  "X.0.1" -> "Z.2"
  "X.0.2" -> "Z.1"
  "Y.1.1" -> "X.0.2"
  "Z.1.1" -> "X.0.4"
  "Z.2" -> "Z.1.1"
  "X.0.4" -> B
}

Answer 1

It's nontrivial. We are open to volunteers to help with layout algorithms. Emden Gansner and I made a big start on a complete overhaul of dot (with cleaner data structures for subgraphs and long edges, and use sifting for mincross) but we didn't finish. We wrote new level assignment cpde that I think Emden back-hacked into the old dot layout engine. it is probably a few months of effort if someone wants to pick it up and take it further. Contact us at graphviz.org

In general constraint machines (like dot) can be a little brittle. Either they get the right solution on their own, or maybe you can add a few tweaks but as soon as the input changes even a little, the tweaks break everything and it's no good. Because of the serial nature of the layout passes, it is hard for example to favor a different level assignment in order to reduce crossings later. There might be some work in the Graph Drawing conference if someone wants to look it up and implement it.

Stephen North