Graphviz Issue Tracker
Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0000600graphvizDotpublic2006-08-23 20:432011-04-28 04:03
ReporterErik Saesarensen 
Assigned Togviz 
PrioritynormalSeverityminorReproducibilityalways
StatusacknowledgedResolutionopen 
PlatformOS*-*-OS Version
Summary0000600: Layout problem with unconstraining edges
Description



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:
<CD>
   "constraint=false causes an edge to be ignored for rank assignment."
</CD>
whereas weights influence the later cross-reduction phase.
Hence, zeroing the weights is a bug.
Steps To Reproduce

digraph Foo {
   A []; B[]; C[];
   X[];
   A -> B -> C;
   A -> C;

   edge [constraint="false"];
   C -> X -> A;
}
TagsNo tags attached.
AUXILLARY-FILES
DATE-FIXED
FIX-COMMENT 
In dot_init_edge() in dotinit.c, around line 50, disabling the if statement
<CD>
    if (nonconstraint_edge(e)) {
        ED_xpenalty(e) = 0;
        ED_weight(e) = 0;
    }
</CD>
makes the problem go away... at least for my examples.
I don't know if th
FORMER-ID1002
INPUT-FILE
OUTPUT-FILEhttp://www.graphviz.org/bugs/b1002.png [^]
STATUS-COMMENT*
VERSION     2.8
Attached Files

- Relationships

-  Notes
There are no notes attached to this issue.

- Issue History
Date Modified Username Field Change
2011-04-28 04:03 user1 New Issue
2011-04-28 04:03 user1 Assigned To => user1


MantisBT 1.2.5[^]
Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker