Number: 1002
Title: Layout problem with unconstraining edges
Submitter: Erik Søe Sørensen
Date: Wed Aug 23 20:43:10 2006
Subsys: Dot
Version: 2.8
System: *-*-
Severity: minor
Problem:
Edges with "constraint=false" seem have layout problems - in some cases, non-crossing paths are overlooked in favour of crossing paths. In the actual example graph for which I noticed this, a 3-crossing path was chosen over a simpler non-crossing path for the same node layout - which can't be right. A 4-node graph with the same clear problem (one unconstraining edge crosses another edge, even though there is a non-crossing solution with the same node placement) is attached.

After looking into the paper describing the overall algorithm used in dot, I got a hypothesis for the cause: That the virtual nodes on the long, unconstraining edge are not taken into account in the min-cross phase. From the code, that is indeed the case: those edges are given weights of zero (always).

But as far as I've understood, the 'constraint' attribute should just affect the ranking phase:


   "constraint=false causes an edge to be ignored for rank assignment."
whereas weights influence the later cross-reduction phase. Hence, zeroing the weights is a bug.
Input:
digraph Foo {
   A []; B[]; C[];
   X[];
   A -> B -> C;
   A -> C;

   edge [constraint="false"];
   C -> X -> A;
}
Output file: b1002.png
Fix:
In dot_init_edge() in dotinit.c, around line 50, disabling the if statement

    if (nonconstraint_edge(e)) {
        ED_xpenalty(e) = 0;
        ED_weight(e) = 0;
    }
makes the problem go away... at least for my examples. I don't know if that code should be completely removed - not knowing the code, and not being an experienced user of dot, I don't know if it serves a purpose in some cases - but it should at least be reconsidered, as it is clearly not always benign.
Owner: *
Status: *