Regarding graphviz's "orthogonal" edge routing

aanastasiou · November 22, 2023, 3:56pm

This is probably the n^{th} time this question is asked here, but having browsed previous responses, I could not confirm exactly what I am after.

Consider the following simple graph:

digraph{
    rankdir=TB
    node [shape=box]
    a -> b
    a -> c
    b -> c
    b -> d
    c -> d
    c -> e
    d -> a
}

If we pass it through dot we get a very nice depiction of it.

There are only two “problems” with it:

In certain domains, the spline routing is not really attractive (visually).
The edges do not depart from the same point on a given node.

Would it be possible to confirm (or -quite happily- refute) that as things stand these two characteristics are incompatible?

I can have edges start from the same point on each box like this…

…but, when I choose orthogonal edges by splines="ortho", all hell breaks loose and in a way that seems “irreparable”. That is, neither splines=false works (because then the edges are simply straight and go over nodes), neither putting the edges in the sametail, samehead group works.

If it is not possible to do orthogonal routing and have the edges start and end at a particular port on two given nodes, is it possible to at least have the edges not “invade” the node’s shape?

steveroush · November 22, 2023, 6:14pm

Yes, splines=ortho fails miserably if ports are specified (see
spline = ortho produces unexpected output with ports (#1415) · Issues · graphviz / graphviz · GitLab).
splines=ortho does OK if ports are not specified (see below) - node placement usually works but the port chosen by “ortho” is not always “best” and the edge route is sometimes “suboptimal”.
Your input without ports:

digraph{
    splines="ortho"
    rankdir=TB
    node [shape=box]
    a -> b
    a -> c
    b -> c
    b -> d
    c -> d
    c -> e
    d -> a
}

Giving:
alterTest99a

erg · November 24, 2023, 5:41pm

Orthogonal routing works well for vanilla graphs. However, various important features can’t be handled. These include ports, compass points, and edge labels. I spent a lot of time trying to handle these but could never figure out how to tweak the code. Other orthogonal routing algorithms didn’t seem to help either. I view this as a major hole in the Graphviz code base and would love someone to tackle this, even if it involved tossing out the current algorithm entirely.

On a related point, I know there is a bug in the orthogonal code where a count determined analytically seems to undercount. This can be patched by using a gross overcount but it would be nice to figure out why the “provably” correct analytic count gives the wrong answer. Unlike the previous problem, this one can probably be handled by just sitting down and giving it some thought.

aanastasiou · November 27, 2023, 5:05pm

Great, thank you. At least it’s confirmed

aanastasiou · November 27, 2023, 5:43pm

Hello @erg and thank you for the overview.

I am not familiar with graphviz’s codebase and neither other orthogonal routing algorithms.

All of my experience with routing is from a piece of software I wrote some years ago to visualise the way different digital signal processing blocks get connected in a given “circuit”.

From this limited viewpoint, I feel that fixing the start and stop “conditions” of departure and arrival tend to make the problem easier. Therefore, to me it sounds a bit “strange” that ports, compass points and edge labels are difficult to handle. But again, I may be thinking of low order and size graphs and not all of the details surrounding graphviz.

What I used to do is this:

The algorithm is given two points A,B that have to be connected with straight lines.
In my case, almost always, A was a black box’ output port and B was another black box’ input port. My operators always had N inputs but only 1 output and therefore, appeared fixed on the left (inputs) and right (outputs) side of a given black box. But this does not really matter. It is possible to work out compass point directions given the relative positions of A,B. The bottom line is that there is a way by which it is possible to determine the start and stop points of an orthogonal edge.
Since the routing was “from an output to an input”, my departure was always “from east (on A) to west (on B)”. The lines were drawn with a succession of DrawHorizontal, DrawVertical operations.
Suppose that we only have two black boxes U,V connected with an edge. U’s output feeds V’s input and U precedes V (in layout). The first DrawHorizontal operation would try to put a line from U.x to V.x and the subsequent DrawVertical operation would try to put a line from the intermediate point that was formed by the preceding DrawHorizontal to V.y.
If nothing is in the way this results in a very straightforward orthogonal routing between U,V by first trying to “bring” the x point from the one of the output to the one of the input and then do the same “transition” for the y point.
If after a given DrawHorizontal, DrawVertical a line segment was going though another black box (let’s call it Q), then the line would be drawn to the periphery of Q, stop there and re-trigger an orthogonal connection from that intermediate point to its final destination.

(I am glossing over a couple of constants that the system used. For example, how far the line stops from an intersecting box before it re-triggers a connection but these are details).

For me, this was a simple enough scheme that resulted in reasonable routings. It was even straightforward to “guess” where I should draw a bus based on the proximity of nearby vertical or horizontal edges.

I did not handle node layout because the user could re-position each black box separately on the user interface.

I will post a screenshot once I get the dependencies for that project re-instated.

If this sounds simple enough and potentially useful for someone with enough knowledge of the graphviz codebase to produce an example, then, please, give it a go.