Graphviz Issue Tracker
Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0002202graphvizNeatopublic2012-02-22 07:562012-02-28 09:50
Reporterdavideyre 
Assigned Toerg 
PrioritynormalSeveritymajorReproducibilityalways
StatusclosedResolutionno change required 
Platformos xOS10.7OS Version
Summary0002202: edge lengths not followed in minimum spanning tree
Descriptionusing the neato algorithm specified edge lengths are not followed, even when there is no reason not to keep to specified length, i.e. the graph is a minimum spanning tree
Steps To Reproduceusing this dot file as test.dot:


graph {

    node [
        fixedsize=True,
        setlinewidth=1,
        shape=circle,
        style=filled,
        width="0.4"
    ];

    "A";
    "B";
    "C";
    "D";
    "E";
    "F";
    "G";
    
    "A" -- "B" [label=8,
        len="0.8"];
        
    "A" -- "C" [label=10,
        len="1"];

    "A" -- "D" [label=15,
        len="1.5"];

    "B" -- "E" [label=20,
        len="2"];
        
    "E" -- "F" [label=10,
        len="1"];
        
    "E" -- "G" [label=10,
        len="1"];
}


run neato -K neato -o test.eps -Tpdf test.dot

the output has edges that do not follow the lengths provided, however there is nothing in the graph to constrain the lengths of the edges as the graph is a minimum spanning tree
TagsNo tags attached.
AUXILLARY-FILES
DATE-FIXED
FIX-COMMENT
FORMER-ID
INPUT-FILE
OUTPUT-FILE
STATUS-COMMENT
VERSION2.28 and most recent build
Attached Files

- Relationships

-  Notes
User avatar (0000190)
erg (administrator)
2012-02-22 14:40

Could you provide your output or a more detailed explanation of what you find incorrect? When I run neato on your graph, I get
 A -- B in 0.8 out 0.835184
 A -- C in 1 out 1.053456
 A -- D in 1.5 out 1.611601
 B -- E in 2 out 2.154346
 E -- F in 1 out 1.039899
 E -- G in 1 out 1.048008
showing the desired and actual lengths. This looks pretty good to me.

Keep in mind that the layout algorithm is optimizing over all pairs of nodes. Thus, it is also trying to place F a distance 2 from G, a distance 3 from B, etc. Except for certain special graphs, it will be impossible to satisfy all of the distance constraints.

If the edge lengths are particularly important, you should increase the weight attribute of the edges, say edge[weight=1000]. This will make these constraints more important. At present, we have not encoded the default solver to use edge weights, so you will need to run neato -Gmode=KK to get the effect.
User avatar (0000193)
davideyre (reporter)
2012-02-27 06:40

thank you. i had been aiming to try and increase the precision to be able to draw the visible edges to scale, so even a 5-10% error in the simple example shown, or more in more complex examples was causing a problem. i had tried the edge weights, but had not appreciated the need to change the mode - having done this i get very acceptable results, even with more complex graphs. thank you.

in case anyone else reads this in future - the edge weights of 1000 work well, increasing the number of iterations has helped with the layout of more complex graphs with the weights - e.g. graph[maxiter=10000]

- Issue History
Date Modified Username Field Change
2012-02-22 07:56 davideyre New Issue
2012-02-22 14:40 erg Note Added: 0000190
2012-02-27 06:40 davideyre Note Added: 0000193
2012-02-28 09:50 erg Assigned To => erg
2012-02-28 09:50 erg Status new => closed
2012-02-28 09:50 erg Resolution open => no change required


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