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 
PlatformOS*-*-OS Version
Summary0000600: Layout problem with unconstraining edges

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.
Steps To Reproduce

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

   edge [constraint="false"];
   C -> X -> A;
TagsNo tags attached.
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 th
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