Avoidable Crossing, while respecting the tailport and headport

[EnisOlgac]

This seems to be a bug. The edge from (6,2) to (2,3) should be drawn left to (3,6). This would avoid the crossings.
Here is the drawing:

Here is the ".dot" file:
Proc.dot.txt

Thanks, Enis

[emden]

Technically, this isn't a bug, as dot can only promise to reduce crossings, not eliminate them. For directed acyclic graphs, minimizing crossings is NP-complete, so dot uses a heuristic. On the other hand, part of the heuristic does some local optimization, and I'm surprised it didn't catch this.

[EnisOlgac]

I called it a bug, because it was too obvious to avoid the crossing. I hope someone can enhance the heuristic.
By the way, I am the inventor of a patent, which calculates the position of a vertex of a given directed graph in three dimensional space. If the subject graph is plane, you will get a crossing free layout. The solution is algorithmic, and does not base on heuristic.

[magneticnorth]

Yes, I agree that the crossing seems to be a bug, since local optimization should detect that exchanging the virtual node for the middle of the red edge with the rectangular node labeled (3,6) that is adjacent in the same level would decrease crossings. It might be more fruitful to improve the debugging framework of the mincross phase or perform a light overhaul of its whole structure, than to chase this particular bug. About this 3D to 2D projection technique: I think you are saying that you can find a crossing-free projection. This idea was explored in the graph layout community over 15 years ago; see https://cs.brown.edu/~rt/gdhandbook/chapters/3d.pdf <https://cs.brown.edu/~rt/gdhandbook/chapters/3d.pdf> (p. 478, “Good Viewpoints”) and they studied variants of the same problem. I am not sure if this work had much practical impact so far. Stephen North

[ellson]

It does look like a bug... but if you need a work-around, removing some of the forcing elements seems to help..

Proc.gv.txt

[EnisOlgac]

As you see from the dot file, I kept the order of vertices fixed, both on x- and y-dimension. And yes, I would find a crossing free layout, if there exist one, i.e. the digraph is plane, and the rank of the head of an edge is always greater than the rank of its tail. Except for back edges, where the head has a smaller rank than the tail. Consider the simple graph:
A depth-first: top-down, left-right will give an ordering p = [a,c,b,d]. A second depth-first: in increasing order of vertex-position on p will give an ordering q = [a,b,c,d]. Well, a third depth-first on q, again in increasing order of vertex-position, will end up with p. This way depth-first becomes an identity function: df(df(p)) = p. Now, one can define the x-, and y-coordinates of a vertex on the plane, to be its relative position on the orderings p, and q, and there will be no crossings. This is true for all plane digraphs. So, the million-dollar question is to find the correct ordering of vertices to begin with.
Thanks for the link. I'll read it as soon as I can.

Enis

[EnisOlgac]

Sorry, the function I was talking about is inverse function and not identity. In other words, p and q are inverse of each other under df (depth-first), i.e. df(p) = q and df(q) = p.
Thanks to ellson. The work-around is perfectly O.K., because it respects the given position of vertices.

Enis

[EnisOlgac]

I simplified the labels of the digraph:
, and augmented nodes with x-, and y-coordinates:

If you check the dot file, you'll see that the positions of the nodes, and the drawing order of the edges are completely optimized. There is neither a need for further optimization, nor for any heuristic. Just draw as specified. These would be the properties of the edges then:

"out edges" (in order of priority of drawing):

1. Back edges (red) always show (up/up-left)
2. Cross edges (orange) always show (down/down-left)
3. Tree edges (green) always show (down/down-right)

"in edges":

1. Back edges precede tree edge
2. Tree edge precedes cross edges

This ordering can be calculated for every digraph.

ellson's work-around corrects the cross edge (8,2), and the back edge (6,2). Unfortunately, the edge (2,3) is effected too, and breaks the rule-3. I wouldn't like to be too pedantic, but respecting the order of edges could prevent crossings in future digraphs.
You are doing such a great job in rendering, so it would be great, if you can introduce an option like "draw as is", or "do not optimize".

Thanks, Enis

[emden]

I'm not understanding your approach. How do the position information and edge properties specify the drawing? In particular, the routing of the back edge 6->2 can got either to the left or the right of node 5 and satisfy the edge properties, unless by "precede" you mean an edge must be to the left of the entire other edge.

As to the node positions, they produce a fairly unattractive drawing that wastes too much space. These are common traits of layout algorithms that try to guarantee planarity or few bends or ... This is probably the reason behind Stephen's comment that such approaches haven't had much practical impact so far.

Graphviz does allow you to just use the rendering engine by running either neato -n or neato -n2. The former assumes you have supplied the node positions. It does the edge routing based on the value of the splines attribute. (Of course, this degree of freedom could still introduce edge crossings.) neato -n2 assumes you have also supplied the edge routing.

A nice compromise would be to allow the user to specify the graph layout topology (nodes ordered in ranks; edges specifying where they cross each rank) and then feed this to the dot phase that determines the actual node positions. This would produce a more aesthetic layout while honoring the given topology. I started to implement this once, but gave up when I realized how complicated it would be.

[EnisOlgac]

I think I brought some confusion to the discussion. My aim is to have a drawing, which makes the causal relationship among nodes as comprehensible as possible. Having this in mind:

• The position information is the result of a depth-first traversal of the digraph in the given edge order. Only this edge order or one of its equivalents, guarantees a crossing free layout, if one exists at all. I say this having your comment in mind, that minimizing crossings is NP-complete.
• I fully agree, that the nodes must be ordered in ranks. Though I'm not sure whether you mean both x- and y-dimension. The y-rank of a node is the number of edges on the longest path to it. The x-rank should be respected as specified, as its index in an ordered list of nodes at the same y-rank.
• I also agree that the node positions are wasting space.
• Y-positions are fixed, because for any edge the tail-node has always a y-rank which is less than the y-rank of the head-node.
• I agree, a better spacing can be achieved by moving the X-positions to the left as much as possible. This would give an overall condensed picture. Though, relaxing the position on X could break the rule, that all forks (tree-edges) fanout to the right, and all joins (cross-edges) fanout to the left. This rule helps to enhance the visibility of clusters.
• Edges have to be drawn at the shortest distance from tail to head, except for back-edges, no matter whether line or spline. Adhering to this rule will force the edges to fanout; all joins first then all forks, in the given order of edges. This is the only way that I know of, which guarantees a crossing free drawing for plane digraphs.
• Back-edges are somewhat special. They are shortcuts back along the path they belong to, so they should be kept apart from other edges. Therefor the “west-to-west” port specification.

This approach should come close to the compromise you mentioned, I hope.

What if the digraph is not plane, i.e. the edges unavoidably cross each other. One can still achieve edge-crossing in an orderly manner. I’ll try to explain what I mean in another comment.