Re: [graphviz-interest] dot output depends on the order of nodes in the source

You are correct that input order of nodes and edges can affect the 
layout. The obvious reason is that the nodes and edges are stored in 
lists, which are then used to traverse the graph via depth-first search, 
etc. There are various practical reasons for this, some being features, 
some being limitations of the code.

1. In many cases, users write the graph in a natural order for the 
domain. Graphviz uses this order because that best fits the graph 
without requiring the user to provide the many constraints explicitly. 
Indeed, one has to be careful which optimizations are pursued. For 
example, all cycles have to be broken. One could try to reduce the 
number of edges flipped to achieve this, and people have worked out some 
nice heuristics, but doing this can cause the natural source nodes of a 
graph to be buried inside the layout.

2. Dot uses a simple collection of steps: reduce the total rank length, 
reduce the number of edge crossings between ranks, produce a compact 
final drawing that tries to shorten and straighten edges between ranks 
that works fairly well for a large collection of typical input graphs. 
No other optimizations are used. One could add more optimizations, but 
at the cost of increased complexity and possible conflicts with current 
optimizations. We often are asked why we don't draw the graph without 
edge crossings if it is planar. We don't because real-world graphs are 
rarely planar, and a planar layout would often require punting on the 
directionality constraint (a->b  means b occurs below a), or producing a 
less compact and less symmetric drawing.

3. Dot could do a better job of handling flat edges. Indeed, I don't 
think dot counts flat edge crossings during crossing minimization. This 
is definitely an area that could be improved while fitting naturally in 
the dot model. Your case is more complex. What should be optimized? The 
most natural answer is the total flat edge length. For your graph, there 
are no problems, but it is easy to extend your graph so that reducing 
the total flat edge length would introduce more edge crossings. So then 
one has to decide how to balance these two measures. If keeping edge 
crossings low is important, does one look at all layouts with a minimum 
of crossings and pick the one with the least flat edge length? Pick a 
layout with minimum crossings and attempt to modify it to reduce flat 
edge length while keeping the crossing count fixed? It starts getting messy.

Of course, we are always willing to accept contributions to the code.

      Emden

On 04/04/17 07:35, Anton Shepelev wrote:
> Hello, all
>
> Is  it correct that the result of dot depends on the
> order in which nodes are introduced?
>
> The following program:
>
> digraph G {
>     graph [dpi=96]
>
>     rankdir = LR
>
>     Export
>     Condition2
>
>     Export->GetBaseDoc
>
>     Condition2->Export
>
>     Condition2->CheckA
>     Condition1->CheckA
>     Condition1->CheckB
>     Condition2->CheckB
>
>     {
>        rank=same
>        Export
>        Condition2
>        Condition1
>     }
> }
>
> produces this output:
>
>          https://urldefense.proofpoint.com/v2/url?u=https-3A__r31.imgup.net_call-2D21f3d.png&d=DwICAg&c=LFYZ-o9_HUMeMTSQicvjIg&r=xTP9WvTdKb0ExEpJt26Gk78mnvO7k30KWj9PaePy7aZwx4MmNzMLhJV4yUhpeMDg&m=63mucJ6kCotRlhl86QbRAMm1yg6tp-5YAs6d8-Ip6iU&s=2quBE7UvjtrtJJ3RPs0w2HA3W7kWkIFKiUKEj4XJhrI&e=
>
> whereas revering the nodes Export and Condition2  in
> the beginning:
>
>     Condition2
>     Export
>
> causes them to be reveresed to the output also:
>
>          https://urldefense.proofpoint.com/v2/url?u=https-3A__j07.imgup.net_call-2D2d968.png&d=DwICAg&c=LFYZ-o9_HUMeMTSQicvjIg&r=xTP9WvTdKb0ExEpJt26Gk78mnvO7k30KWj9PaePy7aZwx4MmNzMLhJV4yUhpeMDg&m=63mucJ6kCotRlhl86QbRAMm1yg6tp-5YAs6d8-Ip6iU&s=TlGIY3CPf0l3pBoRcB8yTbG6mnC03qA5OhWZX3SWLoo&e=
>
> This  latter  arrangement  should seem more optimal,
> because the edge Condition2->Export is straight  and
> much  shorter.   Why does not dot find this solution
> in both cases?
>

_______________________________________________
[email protected]
http://lists.research.att.com/mailman/listinfo/graphviz-interest