Graphviz Issue Tracker
Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0000856graphvizNeatopublic2005-03-31 07:042011-04-28 04:03
ReporterJohn Hinsdale 
Assigned Toerg 
PrioritynormalSeveritycriticalReproducibilityalways
StatusclosedResolutionfixed 
PlatformOSx86-Linux-2.4.18OS Version
Summary0000856: Neato hanging (infinite loop / algorithm blowup)
Description



neato -Tps hangs for many minutes on a large graph
of 260 nodes. Here is a stack trace of where it
was after a few minutes of chugging:



<CD>
#0 0x4019c5f6 in wind (a={x = 281.09989489163166, y = 3135.1854025404459}, b={x = 303.93429398629945, y = 3140.6849613872182}, c=
      {x = 2302.6807007539051, y = 3198.8769581554361}) at visibility.c:76
0000001 0x4019c82b in intersect (a={x = 1569, y = 2206}, b={x = 2302.6807007539051, y = 3198.8769581554361}, c=
      {x = 281.09989489163166, y = 3135.1854025404459}, d={x = 303.93429398629945, y = 3140.6849613872182}) at visibility.c:174
0000002 0x4019cd38 in clear (pti={x = 1569, y = 2206}, ptj={x = 2302.6807007539051, y = 3198.8769581554361}, start=132, end=140, V=1356, pts=0x80d8400,
    nextPt=0x80ddcf0, prevPt=0x80e1860) at visibility.c:254
0000003 0x4019d3c9 in ptVis (conf=0x80c9de0, pp=1251, p={x = 1569, y = 2206}) at visibility.c:385
0000004 0x401980e3 in Pobspath (config=0x80c9de0, p0={x = 1091, y = 3493}, poly0=26, p1={x = 1569, y = 2206}, poly1=23, output_route=0xbfffef78)
    at cvt.c:125
0000005 0x40184b30 in getPath (e=0x107, vconfig=0x40a83120, chkPts=1, obs=0x80d0ab8, npoly=263) at neatosplines.c:491
0000006 0x40185286 in _spline_edges (g=0x804f260, SEP=1.01, splines=1) at neatosplines.c:601
0000007 0x40186254 in splineEdges (g=0x804f260, edgefn=0x40185180 <_spline_edges>, splines=1084764448) at neatosplines.c:692
0000008 0x401862be in spline_edges1 (g=0x40a83120, splines=1084764448) at neatosplines.c:705
0000009 0x40186310 in spline_edges0 (g=0x804f260) at neatosplines.c:713
0000010 0x401863b5 in spline_edges (g=0x804f260) at neatosplines.c:737
#11 0x40181208 in neato_layout (g=0x804f260) at neatoinit.c:1065
0000012 0x08048d23 in main (argc=3, argv=0xbffff334) at neato.c:182
0000013 0x401f414f in __libc_start_main () from /lib/libc.so.6
</CD>
... and here is where it was when let run a few minutes more. Perhaps
this will help tell where it gets stuck.
<CD>
#0 0x4019c741 in intersect (a={x = 933, y = 935}, b={x = 283.32712638613498, y = 4381.7904450037022}, c={x = 1019.482635, y = 2840.1799999999998},
    d={x = 1106.5173649999999, y = 2840.1799999999998}) at visibility.c:169
0000001 0x4019cc88 in clear (pti={x = 933, y = 935}, ptj={x = 283.32712638613498, y = 4381.7904450037022}, start=568, end=576, V=1356, pts=0x80d8400,
    nextPt=0x80ddcf0, prevPt=0x80e1860) at visibility.c:250
0000002 0x4019d3c9 in ptVis (conf=0x80c9de0, pp=1061, p={x = 933, y = 935}) at visibility.c:385
0000003 0x401980e3 in Pobspath (config=0x80c9de0, p0={x = 272, y = 2261}, poly0=111, p1={x = 933, y = 935}, poly1=108, output_route=0xbfffef78)
    at cvt.c:125
0000004 0x40184b30 in getPath (e=0x107, vconfig=0x4071b53b, chkPts=1, obs=0x80d0ab8, npoly=263) at neatosplines.c:491
0000005 0x40185286 in _spline_edges (g=0x804f260, SEP=1.01, splines=1) at neatosplines.c:601
0000006 0x40186254 in splineEdges (g=0x804f260, edgefn=0x40185180 <_spline_edges>, splines=1081193787) at neatosplines.c:692
0000007 0x401862be in spline_edges1 (g=0x4071b53b, splines=1081193787) at neatosplines.c:705
0000008 0x40186310 in spline_edges0 (g=0x804f260) at neatosplines.c:713
0000009 0x401863b5 in spline_edges (g=0x804f260) at neatosplines.c:737
0000010 0x40181208 in neato_layout (g=0x804f260) at neatoinit.c:1065
#11 0x08048d23 in main (argc=3, argv=0xbffff334) at neato.c:182
0000012 0x401f414f in __libc_start_main () from /lib/libc.so.6
</CD>



Run with -v, we get
<CD>
neato: fontname=Times-Roman fontpath=[internal times]
Scanning graph _neato_cc0, 3 nodes
model 0 smart_init 0 iterations 200 tol 0.000100
convert graph: 3 nodes 0.00 sec
Calculating shortest paths: 0.00 sec
Setting initial positions: 0.00 sec
Setting up stress function: 0.00 sec
Solving model: 0.792 0.032 0.011 0.006 0.003 0.002 0.002 0.001 0.001 0.001
0.001 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
0.000 0.000 0.000 0.000 0.000 0.000 0.000
final e = 0.000103 132 iterations 0.00 sec
Adjusting nodes using yx orthogonal constraints
Scanning graph _neato_cc1, 232 nodes
model 0 smart_init 0 iterations 200 tol 0.000100
convert graph: 232 nodes 0.00 sec
Calculating shortest paths: 0.01 sec
Setting initial positions: 0.00 sec
Setting up stress function: 0.00 sec
Solving model: 19740.697 5336.329 4794.954 4380.841 4023.649 3731.698 3503.658 3370.388 3287.848 3229.188
3184.500 3148.486 3117.025 3093.477 3073.529 3056.804 3043.101 3031.821 3023.717 3017.326
3012.027 3008.065 3004.380 3000.659 2997.231 2993.734 2989.964 2985.927 2981.348 2976.803
2972.350 2967.543 2962.546 2957.637 2952.409 2944.838 2934.371 2920.918 2911.808 2904.745



final e = 2898.533844 200 iterations 3.49 sec
Adjusting nodes using yx orthogonal constraints
network simplex: 225 nodes 9931 edges 0 iter 0.09 sec
network simplex: 229 nodes 602 edges 0 iter 0.00 sec
Scanning graph _neato_cc2, 2 nodes
model 0 smart_init 0 iterations 200 tol 0.000100
convert graph: 2 nodes 0.00 sec
Calculating shortest paths: 0.00 sec
Setting initial positions: 0.00 sec
Setting up stress function: 0.00 sec
Solving model: 0.039
final e = 0.000000 2 iterations 0.00 sec
Adjusting nodes using yx orthogonal constraints
network simplex: 2 nodes 1 edges 0 iter 0.00 sec
network simplex: 2 nodes 1 edges 0 iter 0.00 sec
Scanning graph _neato_cc3, 4 nodes
model 0 smart_init 0 iterations 200 tol 0.000100
convert graph: 4 nodes 0.00 sec
Calculating shortest paths: 0.00 sec
Setting initial positions: 0.00 sec
Setting up stress function: 0.00 sec
Solving model: 1.779 1.202 1.191 1.036 0.079 0.019 0.008 0.004 0.003 0.002
0.001 0.001 0.001 0.001 0.001 0.000 0.000 0.000 0.000 0.000
0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
0.000 0.000 0.000
final e = 0.000097 164 iterations 0.00 sec
Adjusting nodes using yx orthogonal constraints
network simplex: 4 nodes 4 edges 0 iter 0.00 sec
network simplex: 4 nodes 4 edges 0 iter 0.00 sec
Scanning graph _neato_cc4, 3 nodes
model 0 smart_init 0 iterations 200 tol 0.000100
convert graph: 3 nodes 0.00 sec
Calculating shortest paths: 0.00 sec
Setting initial positions: 0.00 sec
Setting up stress function: 0.00 sec
Solving model: 0.751 0.043 0.013 0.006 0.004 0.002 0.002 0.001 0.001 0.001
0.001 0.001 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
0.000 0.000 0.000 0.000 0.000 0.000 0.000
final e = 0.000103 134 iterations 0.01 sec
Adjusting nodes using yx orthogonal constraints
Scanning graph _neato_cc5, 2 nodes
model 0 smart_init 0 iterations 200 tol 0.000100
convert graph: 2 nodes 0.00 sec
Calculating shortest paths: 0.00 sec
Setting initial positions: 0.00 sec
Setting up stress function: 0.00 sec
Solving model: 0.039
final e = 0.000000 2 iterations 0.00 sec
Adjusting nodes using yx orthogonal constraints
network simplex: 2 nodes 1 edges 0 iter 0.00 sec
network simplex: 2 nodes 1 edges 0 iter 0.00 sec
Scanning graph _neato_cc6, 3 nodes
model 0 smart_init 0 iterations 200 tol 0.000100
convert graph: 3 nodes 0.00 sec
Calculating shortest paths: 0.00 sec
Setting initial positions: 0.00 sec
Setting up stress function: 0.00 sec
Solving model: 0.792 0.032 0.011 0.006 0.003 0.002 0.002 0.001 0.001 0.001
0.001 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
0.000 0.000 0.000 0.000 0.000 0.000 0.000
final e = 0.000103 132 iterations 0.00 sec
Adjusting nodes using yx orthogonal constraints
Scanning graph _neato_cc7, 2 nodes
model 0 smart_init 0 iterations 200 tol 0.000100
convert graph: 2 nodes 0.00 sec
Calculating shortest paths: 0.00 sec
Setting initial positions: 0.00 sec
Setting up stress function: 0.00 sec
Solving model: 0.039
final e = 0.000000 2 iterations 0.00 sec
Adjusting nodes using yx orthogonal constraints
network simplex: 2 nodes 1 edges 0 iter 0.00 sec
network simplex: 2 nodes 1 edges 0 iter 0.00 sec
Scanning graph _neato_cc8, 4 nodes
model 0 smart_init 0 iterations 200 tol 0.000100
convert graph: 4 nodes 0.00 sec
Calculating shortest paths: 0.00 sec
Setting initial positions: 0.00 sec
Setting up stress function: 0.00 sec
Solving model: 1.779 1.202 1.191 1.036 0.079 0.019 0.008 0.004 0.003 0.002
0.001 0.001 0.001 0.001 0.001 0.000 0.000 0.000 0.000 0.000
0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
0.000 0.000 0.000
final e = 0.000097 164 iterations 0.00 sec
Adjusting nodes using yx orthogonal constraints
network simplex: 4 nodes 4 edges 0 iter 0.00 sec
network simplex: 4 nodes 4 edges 0 iter 0.00 sec
Scanning graph _neato_cc9, 2 nodes
model 0 smart_init 0 iterations 200 tol 0.000100
convert graph: 2 nodes 0.00 sec
Calculating shortest paths: 0.00 sec
Setting initial positions: 0.00 sec
Setting up stress function: 0.00 sec
Solving model: 0.039
final e = 0.000000 2 iterations 0.00 sec
Adjusting nodes using yx orthogonal constraints
Scanning graph _neato_cc10, 3 nodes
model 0 smart_init 0 iterations 200 tol 0.000100
convert graph: 3 nodes 0.00 sec
Calculating shortest paths: 0.00 sec
Setting initial positions: 0.00 sec
Setting up stress function: 0.00 sec
Solving model: 0.792 0.032 0.011 0.006 0.003 0.002 0.002 0.001 0.001 0.001
0.001 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
0.000 0.000 0.000 0.000 0.000 0.000 0.000
final e = 0.000103 132 iterations 0.00 sec
Adjusting nodes using yx orthogonal constraints
Scanning graph _neato_cc11, 3 nodes
model 0 smart_init 0 iterations 200 tol 0.000100
convert graph: 3 nodes 0.00 sec
Calculating shortest paths: 0.00 sec
Setting initial positions: 0.00 sec
Setting up stress function: 0.00 sec
Solving model: 0.792 0.032 0.011 0.006 0.003 0.002 0.002 0.001 0.001 0.001
0.001 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
0.000 0.000 0.000 0.000 0.000 0.000 0.000
final e = 0.000103 132 iterations 0.00 sec
Adjusting nodes using yx orthogonal constraints
step size = 104
</CD>
TagsNo tags attached.
AUXILLARY-FILES
DATE-FIXED
FIX-COMMENT
FORMER-ID670
INPUT-FILEhttp://www.graphviz.org/bugs/b670.dot [^]
OUTPUT-FILE
STATUS-COMMENTFixed (7 April 2005)
VERSION     2.2
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 => erg


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