Skip Menu |

This queue is for tickets about the Graph-Easy CPAN distribution.

Report information
The Basics
Id: 35184
Status: open
Worked: 5 min
Priority: 0/
Queue: Graph-Easy

People
Owner: TELS [...] cpan.org
Requestors: whatever [...] davidnicol.com
Cc:
AdminCc:

Bug Information
Severity: Important
Broken in: 0.62
Fixed in: (no value)



I load a 749-edge graph and try to output it as_txt, and it hangs. I tried setting timeout(0) but that just kept the default, so I set timeout(1000000) and timed the run. Cygperl under windows XP, 1.6GHz Pentium with 512M RAM. Have not yet tried other formats. This is what I got instead of a busy ascii-art output: Can't use an undefined value as an ARRAY reference at /usr/lib/perl5/site_perl/5.8/Graph/Easy/Layout/Scout.pm line 1031. real 22m9.797s user 21m29.484s sys 0m0.190s Attached is my graph, with non-structural information removed.
Subject: AliasedGraph.txt
[ aa ] -> [ab] [ aa ] -> [ab] [ ae ] -> [af] [ ag ] -> [af] [ ag ] -> [aj] [ ag ] -> [aj] [ ag ] -> [an] [ ao ] -> [ap] [ ao ] -> [ar] [ ao ] -> [ar] [ ao ] -> [ar] [ ao ] -> [ax] [ ao ] -> [az] [ ao ] -> [ar] [ bc ] -> [bd] [ bc ] -> [bf] [ bc ] -> [bh] [ bc ] -> [bj] [ bc ] -> [bl] [ bc ] -> [bn] [ bc ] -> [bp] [ bc ] -> [br] [ bc ] -> [bt] [ bc ] -> [bt] [ bw ] -> [bx] [ bw ] -> [bx] [ bw ] -> [bx] [ bw ] -> [cd] [ bw ] -> [cf] [ bw ] -> [cf] [ bw ] -> [cd] [ bw ] -> [cl] [ bw ] -> [cn] [ bw ] -> [cp] [ bw ] -> [cr] [ bw ] -> [cl] [ bw ] -> [cv] [ bw ] -> [cx] [ bw ] -> [cz] [ bw ] -> [cf] [ bw ] -> [cl] [ de ] -> [df] [ de ] -> [dh] [ de ] -> [dh] [ dk ] -> [dl] [ dk ] -> [dh] [ do ] -> [dp] [ do ] -> [ar] [ do ] -> [dt] [ do ] -> [ar] [ do ] -> [ar] [ do ] -> [ar] [ do ] -> [eb] [ do ] -> [ed] [ do ] -> [ef] [ do ] -> [ef] [ do ] -> [ar] [ do ] -> [el] [ do ] -> [eb] [ do ] -> [ep] [ do ] -> [er] [ do ] -> [et] [ do ] -> [eb] [ do ] -> [ex] [ do ] -> [dt] [ do ] -> [fb] [ do ] -> [fd] [ do ] -> [dt] [ do ] -> [fh] [ do ] -> [fj] [ do ] -> [fl] [ do ] -> [fn] [ do ] -> [fp] [ do ] -> [fr] [ do ] -> [ft] [ do ] -> [ft] [ do ] -> [ft] [ do ] -> [fz] [ do ] -> [gb] [ do ] -> [gd] [ do ] -> [gf] [ do ] -> [gh] [ do ] -> [gj] [ do ] -> [gl] [ do ] -> [gn] [ do ] -> [bn] [ do ] -> [cl] [ do ] -> [cl] [ do ] -> [bj] [ do ] -> [br] [ do ] -> [gz] [ do ] -> [ar] [ hc ] -> [hd] [ hc ] -> [ar] [ hc ] -> [hh] [ hc ] -> [ar] [ hc ] -> [hl] [ hc ] -> [hn] [ hc ] -> [hp] [ hc ] -> [ar] [ hc ] -> [eb] [ hc ] -> [hv] [ hc ] -> [hx] [ hc ] -> [hz] [ hc ] -> [ib] [ hc ] -> [hv] [ hc ] -> [if] [ hc ] -> [ih] [ hc ] -> [ij] [ hc ] -> [il] [ hc ] -> [in] [ hc ] -> [hv] [ hc ] -> [ir] [ hc ] -> [hv] [ hc ] -> [iv] [ hc ] -> [hv] [ hc ] -> [iz] [ hc ] -> [jb] [ hc ] -> [jd] [ hc ] -> [jf] [ hc ] -> [jh] [ hc ] -> [jj] [ hc ] -> [jl] [ hc ] -> [jn] [ hc ] -> [jp] [ hc ] -> [jr] [ hc ] -> [jt] [ hc ] -> [hv] [ hc ] -> [ar] [ hc ] -> [eb] [ hc ] -> [cf] [ hc ] -> [bn] [ hc ] -> [kf] [ hc ] -> [cl] [ hc ] -> [cl] [ hc ] -> [cl] [ hc ] -> [cl] [ hc ] -> [gz] [ hc ] -> [hh] [ hc ] -> [ar] [ ku ] -> [kv] [ ku ] -> [ar] [ ku ] -> [dt] [ ku ] -> [ar] [ ku ] -> [ar] [ ku ] -> [cn] [ ku ] -> [ar] [ ku ] -> [eb] [ ku ] -> [ed] [ ku ] -> [ef] [ ku ] -> [ef] [ ku ] -> [ar] [ ku ] -> [el] [ ku ] -> [eb] [ ku ] -> [ep] [ ku ] -> [er] [ ku ] -> [eb] [ ku ] -> [ex] [ ku ] -> [dt] [ ku ] -> [fb] [ ku ] -> [fd] [ ku ] -> [dt] [ ku ] -> [fh] [ ku ] -> [fj] [ ku ] -> [fl] [ ku ] -> [fn] [ ku ] -> [fp] [ ku ] -> [fr] [ ku ] -> [mz] [ ku ] -> [ft] [ ku ] -> [ft] [ ku ] -> [ft] [ ku ] -> [fz] [ ku ] -> [gd] [ ku ] -> [gh] [ ku ] -> [bt] [ ku ] -> [bt] [ ku ] -> [gj] [ ku ] -> [gn] [ ku ] -> [cl] [ ku ] -> [bj] [ ku ] -> [br] [ ku ] -> [gz] [ ku ] -> [ar] [ oe ] -> [of] [ oe ] -> [af] [ oi ] -> [af] [ oi ] -> [ol] [ om ] -> [bt] [ om ] -> [bt] [ om ] -> [bt] [ om ] -> [ot] [ om ] -> [ot] [ om ] -> [ot] [ om ] -> [bt] [ om ] -> [bt] [ om ] -> [pd] [ om ] -> [bt] [ om ] -> [bt] [ om ] -> [bt] [ om ] -> [bt] [ om ] -> [pn] [ om ] -> [pn] [ om ] -> [pn] [ om ] -> [pn] [ om ] -> [bt] [ pw ] -> [px] [ pw ] -> [px] [ pw ] -> [qb] [ qc ] -> [qd] [ qc ] -> [ab] [ qg ] -> [qh] [ qi ] -> [qj] [ qi ] -> [ql] [ qm ] -> [qj] [ qm ] -> [ql] [ qq ] -> [qr] [ qq ] -> [ql] [ qq ] -> [qr] [ qq ] -> [qr] [ qq ] -> [qr] [ qq ] -> [qr] [ rc ] -> [qj] [ rc ] -> [ql] [ rg ] -> [rh] [ rg ] -> [rh] [ rg ] -> [qj] [ rg ] -> [ql] [ rg ] -> [rp] [ rg ] -> [rp] [ rg ] -> [rh] [ rg ] -> [rh] [ rg ] -> [rh] [ rg ] -> [rz] [ rg ] -> [rz] [ rg ] -> [rz] [ rg ] -> [sf] [ rg ] -> [sf] [ rg ] -> [sf] [ rg ] -> [rp] [ sm ] -> [qj] [ sm ] -> [ql] [ sm ] -> [rh] [ ss ] -> [qj] [ ss ] -> [ql] [ sw ] -> [qj] [ sw ] -> [ql] [ ta ] -> [qj] [ ta ] -> [ql] [ te ] -> [qj] [ te ] -> [ql] [ te ] -> [tj] [ tk ] -> [qj] [ tk ] -> [ql] [ to ] -> [qj] [ to ] -> [ql] [ ts ] -> [qj] [ ts ] -> [ql] [ tw ] -> [qj] [ tw ] -> [ql] [ ua ] -> [qj] [ ua ] -> [ql] [ ue ] -> [qj] [ ue ] -> [ql] [ ue ] -> [uj] [ ue ] -> [ul] [ ue ] -> [un] [ ue ] -> [un] [ uq ] -> [ue] [ uq ] -> [ue] [ uq ] -> [qj] [ uq ] -> [ue] [ uq ] -> [ql] [ uq ] -> [vb] [ vc ] -> [qj] [ vc ] -> [ql] [ vg ] -> [vh] [ vg ] -> [vh] [ vg ] -> [qj] [ vg ] -> [ql] [ vg ] -> [vh] [ vg ] -> [vh] [ vg ] -> [vh] [ vg ] -> [vh] [ vg ] -> [vh] [ vg ] -> [vh] [ vg ] -> [vh] [ vg ] -> [vh] [ vg ] -> [vh] [ vg ] -> [wh] [ wi ] -> [qj] [ wi ] -> [bt] [ wi ] -> [ql] [ wi ] -> [wp] [ wi ] -> [wr] [ ws ] -> [af] [ ws ] -> [wv] [ ww ] -> [qj] [ ww ] -> [ql] [ ww ] -> [xb] [ ww ] -> [xb] [ ww ] -> [xb] [ ww ] -> [xb] [ ww ] -> [xb] [ ww ] -> [xb] [ ww ] -> [xb] [ ww ] -> [xb] [ ww ] -> [xb] [ ww ] -> [xb] [ ww ] -> [xb] [ ww ] -> [xb] [ ww ] -> [xz] [ ww ] -> [xb] [ ww ] -> [xz] [ ww ] -> [xz] [ ww ] -> [xb] [ ww ] -> [yj] [ ww ] -> [bt] [ ym ] -> [vg] [ ym ] -> [yp] [ ym ] -> [yp] [ ym ] -> [qj] [ ym ] -> [ql] [ ym ] -> [yp] [ ym ] -> [yp] [ ym ] -> [yp] [ ym ] -> [yp] [ ym ] -> [yp] [ ym ] -> [yp] [ ym ] -> [yp] [ ym ] -> [yp] [ ym ] -> [yp] [ ym ] -> [yp] [ zq ] -> [zr] [ zq ] -> [qj] [ zq ] -> [ql] [ zw ] -> [af] [ zw ] -> [zz] [ zw ] -> [zz] [ zw ] -> [aad] [ zw ] -> [aad] [ aag ] -> [qj] [ aag ] -> [ql] [ aak ] -> [aal] [ aam ] -> [aan] [ aam ] -> [aap] [ aam ] -> [aar] [ aam ] -> [aat] [ aam ] -> [aav] [ aam ] -> [aax] [ aam ] -> [aaz] [ aam ] -> [abb] [ aam ] -> [abd] [ of ] -> [abf] [ of ] -> [abh] [ of ] -> [abj] [ abk ] -> [zw] [ abm ] -> [af] [ abm ] -> [ae] [ abm ] -> [ae] [ abs ] -> [abt] [ abs ] -> [abt] [ abs ] -> [abx] [ abs ] -> [abx] [ aca ] -> [qd] [ aca ] -> [ab] [ ab ] -> [af] [ ab ] -> [ach] [ af ] -> [acj] [ ack ] -> [ax] [ acm ] -> [bf] [ acm ] -> [bf] [ acm ] -> [bf] [ acs ] -> [bh] [ acs ] -> [acv] [ acs ] -> [acv] [ acy ] -> [bj] [ acy ] -> [bj] [ acy ] -> [bj] [ ade ] -> [bl] [ ade ] -> [bl] [ adi ] -> [bn] [ adi ] -> [bn] [ adi ] -> [bn] [ ado ] -> [bp] [ ado ] -> [bd] [ ado ] -> [adt] [ ado ] -> [cl] [ adw ] -> [br] [ adw ] -> [br] [ adw ] -> [br] [ cf ] -> [cn] [ cn ] -> [cd] [ cn ] -> [cd] [ aei ] -> [cp] [ aei ] -> [acj] [ aei ] -> [cn] [ aei ] -> [cn] [ aeq ] -> [cr] [ aes ] -> [cv] [ aes ] -> [bx] [ aew ] -> [cx] [ aew ] -> [cx] [ afa ] -> [acj] [ cz ] -> [acj] [ afe ] -> [dh] [ afg ] -> [dt] [ afg ] -> [gn] [ afg ] -> [ar] [ afg ] -> [dt] [ afg ] -> [ar] [ afg ] -> [ar] [ afg ] -> [ar] [ afg ] -> [ar] [ afg ] -> [afx] [ afg ] -> [eb] [ afg ] -> [el] [ afg ] -> [eb] [ afg ] -> [ep] [ afg ] -> [er] [ afg ] -> [eb] [ afg ] -> [ex] [ afg ] -> [dt] [ afg ] -> [fb] [ afg ] -> [fd] [ afg ] -> [dt] [ afg ] -> [fh] [ afg ] -> [fj] [ afg ] -> [fl] [ afg ] -> [fn] [ afg ] -> [fp] [ afg ] -> [fr] [ afg ] -> [ahh] [ afg ] -> [ahj] [ afg ] -> [ahl] [ afg ] -> [ft] [ afg ] -> [fz] [ afg ] -> [gd] [ afg ] -> [aht] [ afg ] -> [ahv] [ afg ] -> [gh] [ afg ] -> [gj] [ afg ] -> [gl] [ afg ] -> [aid] [ afg ] -> [gn] [ afg ] -> [cl] [ afg ] -> [bj] [ afg ] -> [gz] [ afg ] -> [gz] [ afg ] -> [aip] [ afg ] -> [ar] [ ais ] -> [af] [ ais ] -> [aiv] [ eb ] -> [af] [ eb ] -> [aiv] [ aja ] -> [az] [ aja ] -> [ef] [ aja ] -> [ef] [ aja ] -> [az] [ ed ] -> [az] [ ed ] -> [ef] [ ed ] -> [ef] [ ed ] -> [az] [ ajq ] -> [el] [ ajs ] -> [ep] [ aju ] -> [er] [ ajw ] -> [et] [ ajy ] -> [fb] [ fd ] -> [bt] [ akc ] -> [bt] [ akc ] -> [akf] [ akc ] -> [fd] [ aki ] -> [fh] [ fj ] -> [dt] [ akm ] -> [fj] [ akm ] -> [dt] [ fl ] -> [dt] [ aks ] -> [fl] [ aks ] -> [dt] [ akw ] -> [fn] [ aky ] -> [fp] [ aky ] -> [dt] [ fp ] -> [dt] [ ale ] -> [fr] [ alg ] -> [ahl] [ ft ] -> [ahl] [ ft ] -> [ahl] [ ft ] -> [ahl] [ ft ] -> [ahj] [ ft ] -> [dt] [ fz ] -> [ahh] [ alu ] -> [fz] [ alu ] -> [ahh] [ aly ] -> [gb] [ ama ] -> [amb] [ amc ] -> [gf] [ ame ] -> [gh] [ amg ] -> [gj] [ gl ] -> [amj] [ amk ] -> [gl] [ amk ] -> [gl] [ amk ] -> [amj] [ amk ] -> [gl] [ amk ] -> [gl] [ amk ] -> [gl] [ amw ] -> [gl] [ amw ] -> [gl] [ amw ] -> [anb] [ amw ] -> [anb] [ amw ] -> [anb] [ amw ] -> [gl] [ ani ] -> [gn] [ ank ] -> [gz] [ ank ] -> [gz] [ gz ] -> [af] [ anq ] -> [hh] [ anq ] -> [hh] [ anq ] -> [jn] [ anq ] -> [il] [ anq ] -> [ar] [ anq ] -> [hh] [ anq ] -> [ar] [ anq ] -> [hl] [ anq ] -> [hn] [ anq ] -> [ar] [ anq ] -> [eb] [ anq ] -> [hv] [ anq ] -> [if] [ anq ] -> [ih] [ anq ] -> [ih] [ anq ] -> [aov] [ anq ] -> [hv] [ anq ] -> [ir] [ anq ] -> [il] [ anq ] -> [hv] [ anq ] -> [hz] [ anq ] -> [hv] [ anq ] -> [hv] [ anq ] -> [hv] [ anq ] -> [iz] [ anq ] -> [jb] [ anq ] -> [jd] [ anq ] -> [jf] [ anq ] -> [jh] [ anq ] -> [jj] [ anq ] -> [jn] [ anq ] -> [jp] [ anq ] -> [jr] [ anq ] -> [ar] [ anq ] -> [eb] [ anq ] -> [aqj] [ anq ] -> [cl] [ anq ] -> [aip] [ anq ] -> [hh] [ anq ] -> [ar] [ aqs ] -> [hl] [ aqu ] -> [hn] [ aqw ] -> [hp] [ aqy ] -> [hv] [ aqy ] -> [hv] [ arc ] -> [hx] [ are ] -> [hz] [ are ] -> [hh] [ hz ] -> [hh] [ ark ] -> [ib] [ arm ] -> [if] [ aro ] -> [ij] [ arq ] -> [il] [ ars ] -> [in] [ aru ] -> [ir] [ arw ] -> [iv] [ ary ] -> [iz] [ asa ] -> [jb] [ asa ] -> [hh] [ jb ] -> [hh] [ asg ] -> [jd] [ asg ] -> [hh] [ jd ] -> [hh] [ asm ] -> [jf] [ jf ] -> [asp] [ asq ] -> [jh] [ ass ] -> [jj] [ asu ] -> [jl] [ asw ] -> [jn] [ asw ] -> [asz] [ ata ] -> [atb] [ atc ] -> [jp] [ ate ] -> [atf] [ atg ] -> [ath] [ ati ] -> [jr] [ ati ] -> [jp] [ jr ] -> [jp] [ ato ] -> [jt] [ atq ] -> [kf] [ atq ] -> [adt] [ atu ] -> [mz] [ pd ] -> [af] [ qj ] -> [acj] [ qj ] -> [aiv] [ qj ] -> [aud] [ qj ] -> [aud] [ qj ] -> [aiv] [ ql ] -> [af] [ qr ] -> [aul] [ qr ] -> [ql] [ auo ] -> [rh] [ auo ] -> [vh] [ auo ] -> [aut] [ auo ] -> [ql] [ rh ] -> [vh] [ rh ] -> [aut] [ rh ] -> [ql] [ rp ] -> [avd] [ rp ] -> [qj] [ rp ] -> [ql] [ tj ] -> [qj] [ tj ] -> [ql] [ vb ] -> [qj] [ vb ] -> [ql] [ vb ] -> [ul] [ vh ] -> [vg] [ vh ] -> [vg] [ vh ] -> [avx] [ vh ] -> [ql] [ wh ] -> [vg] [ wh ] -> [vg] [ wh ] -> [aut] [ wh ] -> [ql] [ wp ] -> [bt] [ wr ] -> [qj] [ wr ] -> [ql] [ wr ] -> [awp] [ xz ] -> [vg] [ xz ] -> [vg] [ xz ] -> [qj] [ xz ] -> [ql] [ yj ] -> [af] [ yj ] -> [axb] [ yj ] -> [axb] [ yj ] -> [axb] [ yj ] -> [axh] [ yj ] -> [axh] [ yj ] -> [axh] [ yj ] -> [axn] [ yj ] -> [axn] [ yj ] -> [axn] [ yp ] -> [avx] [ yp ] -> [ql] [ aad ] -> [acj] [ aad ] -> [acj] [ aad ] -> [acj] [ aad ] -> [acj] [ aal ] -> [af] [ aal ] -> [ayh] [ aan ] -> [ayj] [ aap ] -> [ayl] [ aap ] -> [awp] [ aap ] -> [awp] [ aar ] -> [ayj] [ aat ] -> [ayt] [ aat ] -> [awp] [ aat ] -> [awp] [ aav ] -> [ayj] [ aax ] -> [azb] [ aax ] -> [awp] [ aax ] -> [awp] [ aaz ] -> [af] [ aaz ] -> [bt] [ aaz ] -> [bt] [ abb ] -> [af] [ abb ] -> [bt] [ abb ] -> [bt] [ abd ] -> [bt] [ abd ] -> [bt] [ abd ] -> [azx] [ abd ] -> [azz] [ abh ] -> [af] [ abh ] -> [bt] [ abh ] -> [bt] [ abj ] -> [af] [ abj ] -> [bt] [ abj ] -> [bt] [ bam ] -> [abx] [ bam ] -> [abx] [ bam ] -> [acj] [ bam ] -> [acj] [ abx ] -> [acj] [ abx ] -> [acj] [ ach ] -> [acj] [ ach ] -> [acj] [ ach ] -> [acj] [ bbe ] -> [gz] [ bbe ] -> [gz] [ bbe ] -> [gz] [ bbk ] -> [adt] [ bbk ] -> [adt] [ bbk ] -> [adt] [ bbq ] -> [afx] [ bbs ] -> [ahh] [ bbu ] -> [ahj] [ bbu ] -> [ahh] [ ahj ] -> [ahh] [ bca ] -> [ahl] [ bcc ] -> [aht] [ bcc ] -> [dt] [ bcc ] -> [gl] [ bci ] -> [ahv] [ bck ] -> [aid] [ bck ] -> [bcn] [ bco ] -> [fd] [ bco ] -> [bt] [ bcs ] -> [amb] [ bcs ] -> [gd] [ bcs ] -> [gd] [ bcs ] -> [amb] [ bda ] -> [aov] [ bda ] -> [aov] [ bda ] -> [bdf] [ aov ] -> [bdf] [ bdi ] -> [aqj] [ bdi ] -> [acj] [ bdm ] -> [bdn] [ bdo ] -> [asz] [ aul ] -> [qj] [ aul ] -> [acj] [ aul ] -> [aiv] [ aul ] -> [aud] [ aul ] -> [aud] [ aul ] -> [aiv] [ aut ] -> [acj] [ aut ] -> [aiv] [ aut ] -> [aud] [ aut ] -> [aud] [ aut ] -> [aiv] [ avd ] -> [qj] [ avd ] -> [ql] [ avx ] -> [qj] [ avx ] -> [acj] [ avx ] -> [aiv] [ avx ] -> [aud] [ avx ] -> [aud] [ avx ] -> [aiv] [ axb ] -> [bfd] [ axb ] -> [bff] [ axb ] -> [bff] [ axh ] -> [bff] [ axn ] -> [acj] [ axn ] -> [acj] [ ayl ] -> [bfp] [ bff ] -> [bfd]
On Fri Apr 18 10:27:03 2008, DAVIDNICO wrote: Show quoted text
> I load a 749-edge graph and try to output it as_txt, and it hangs.
sorry that is incorrect. as_txt works, as does the graphviz format. html format hangs; svg format is hung right now. Layouter is hanging. What should I start throwing overboard to lighten my balloon? Redundant edges?
Subject: Re: [rt.cpan.org #35184] Layouter hangs on 749-edge graph
Date: Fri, 18 Apr 2008 18:29:30 +0200
To: bug-Graph-Easy [...] rt.cpan.org
From: Tels <nospam-abuse [...] bloodgate.com>
On Friday 18 April 2008 17:11:37 David Nicol via RT wrote: Show quoted text
> Queue: Graph-Easy > Ticket <URL: http://rt.cpan.org/Ticket/Display.html?id=35184 > > > On Fri Apr 18 10:27:03 2008, DAVIDNICO wrote:
> > I load a 749-edge graph and try to output it as_txt, and it hangs.
> > sorry that is incorrect. as_txt works, as does the graphviz format. > html format hangs; svg format is hung right now. Layouter is hanging. > What should I start throwing overboard to lighten my balloon? > Redundant edges?
I think the graph is just way too complex for my simple layouter. However, it will provide a nice testcse for debugging, maybe the hang is a true hang (aka endless loop) instead of just a veeery long computation time. I'll have a look at the weekend. To get a sense of the layout, you can run it through: graph-easy mygraph.txt --png (nees grapviz installed) and look at the resulting mygraph.png file to see how Graphviz renders it. All the best, Tels -- Signed on Fri Apr 18 18:27:50 2008 with key 0x93B84C15. View my photo gallery: http://bloodgate.com/photos PGP key on http://bloodgate.com/tels.asc or per email. "My other computer is your Windows box." -- Dr. Brad (19034) on 2004-08-13 at /.
Download (untitled)
application/pgp-signature 481b

Message body not shown because it is not plain text.

Subject: Re: [rt.cpan.org #35184]
Date: Sat, 19 Apr 2008 00:04:11 +0200
To: bug-Graph-Easy [...] rt.cpan.org
From: Tels <nospam-abuse [...] bloodgate.com>
On Friday 18 April 2008 17:11:37 David Nicol via RT wrote: Show quoted text
> Queue: Graph-Easy > Ticket <URL: http://rt.cpan.org/Ticket/Display.html?id=35184 > > > On Fri Apr 18 10:27:03 2008, DAVIDNICO wrote:
> > I load a 749-edge graph and try to output it as_txt, and it hangs.
> > sorry that is incorrect. as_txt works, as does the graphviz format. > html format hangs; svg format is hung right now. Layouter is hanging. > What should I start throwing overboard to lighten my balloon? > Redundant edges?
I see the following errors during layout: # Done 212 nodes and 296 edges. # step 514: action trace 'do' => 'gb' # Finding path from do to gb # src: 118, 0 dst: 2, 296 # A* from 118,0 to 2,296 Use of uninitialized value in concatenation (.) or string at lib/Graph/Easy/Layout/Scout.pm line 1120. Use of uninitialized value in concatenation (.) or string at lib/Graph/Easy/Layout/Scout.pm line 1120. # adding open pos 118,-1 (414 = 1 + 0 + 413) at (,) Use of uninitialized value in concatenation (.) or string at lib/Graph/Easy/Layout/Scout.pm line 1120. Use of uninitialized value in concatenation (.) or string at lib/Graph/Easy/Layout/Scout.pm line 1120. # adding open pos 119,-1 (415.001 = 1 + 0.001 + 414) at (,) Turns out this was only some problem with the debugging output, fixed it and also improved the debugging output. The real bug eludes me so far - sorry this can take some more time :) Thank you for your report! All the best, Tels -- Signed on Fri Apr 18 23:54:12 2008 with key 0x93B84C15. Get one of my photo posters: http://bloodgate.com/posters PGP key on http://bloodgate.com/tels.asc or per email. "Un bon mot ne prouve rien." -- Voltaire
Download (untitled)
application/pgp-signature 481b

Message body not shown because it is not plain text.

Subject: Re: [rt.cpan.org #35184] Layouter hangs on 749-edge graph
Date: Sat, 19 Apr 2008 14:54:29 +0200
To: bug-Graph-Easy [...] rt.cpan.org
From: Tels <nospam-abuse [...] bloodgate.com>
Moin, On Friday 18 April 2008 17:11:37 David Nicol via RT wrote: Show quoted text
> Queue: Graph-Easy > Ticket <URL: http://rt.cpan.org/Ticket/Display.html?id=35184 > > > On Fri Apr 18 10:27:03 2008, DAVIDNICO wrote:
> > I load a 749-edge graph and try to output it as_txt, and it hangs.
Some more additional info: The layout throws an error about "undef in array context" because the path returned by A* is undef. This happens because a hard limit of 50000 steps in that algorithm is reached and the pathfinding aborts. I have now added a warning and returning [] to counter this. However, why it aborts after 50000 steps is not yet clear. Either the algorithm really needs more steps (because the layout is already that big), or it hangs in an endless loop and thus does not finish. Debugging this is a bit hard, as it takes a very very long time to reach this condition. For now, I already streamlined a function that gets called a few hundred thousand times to make it faster, streamlining is still going on. Also I have some ideas how to make the layouter generated a beter layout in a faster way. But the original abort still needs to be investigated. All the best, Tels -- Signed on Sat Apr 19 14:51:29 2008 with key 0x93B84C15. View my photo gallery: http://bloodgate.com/photos PGP key on http://bloodgate.com/tels.asc or per email. "HOT PACKET ON SERVER ACTION! Click here for FREE ACCESS to streaming video of dirty packets penetrating badly-configured firewalls!!!" -- aanand (705284) on 2004-03-20 on /. about the Adult and Evil bits
Download (untitled)
application/pgp-signature 481b

Message body not shown because it is not plain text.

CC: "David Nicol" <davidnicol [...] gmail.com>
Subject: Re: [rt.cpan.org #35184] Layouter hangs on 749-edge graph
Date: Thu, 24 Apr 2008 20:48:54 +0200
To: bug-Graph-Easy [...] rt.cpan.org
From: Tels <nospam-abuse [...] bloodgate.com>
Moin, On Friday 18 April 2008 18:33:18 nospam-abuse@bloodgate.com via RT wrote: Show quoted text
> Queue: Graph-Easy > Ticket <URL: http://rt.cpan.org/Ticket/Display.html?id=35184 > > > On Friday 18 April 2008 17:11:37 David Nicol via RT wrote:
> > Queue: Graph-Easy > > Ticket <URL: http://rt.cpan.org/Ticket/Display.html?id=35184 > > > > > On Fri Apr 18 10:27:03 2008, DAVIDNICO wrote:
> > > I load a 749-edge graph and try to output it as_txt, and it > > > hangs.
> > > > sorry that is incorrect. as_txt works, as does the graphviz > > format. html format hangs; svg format is hung right now. Layouter > > is hanging. What should I start throwing overboard to lighten my > > balloon? Redundant edges?
> > I think the graph is just way too complex for my simple layouter. > However, it will provide a nice testcse for debugging, maybe the hang > is a true hang (aka endless loop) instead of just a veeery long > computation time. I'll have a look at the weekend.
My, what an interesting opportunity to improve my code this proved to be. :) Sorry for the long delay, I was quite busy. Here is what I have done so far: After fixing the problem that the A* run out of tries and aborted, I raised the number of maximum tries from 50_000 to 200_000. The layout took a long time and there were quite some messages that the max tries were exceeded. So I raised the limit to 500_000 and tried again. It took a loong (forgot to time it, tho) time and still had 91 max_tries-exceeded. Oops. Raising the tries to 1_000_000 did not really help as the layouter took 37 minutes just to place all nodes and add 550 or so edges and with 200 edges still to go it would take ages (as these edges now took a lot of time with the already complicted layout). There are now three ways how we can improve the situations, ranked in increasing complexity: 1 make A* do what it does, but faster 2 make A* find the same way, but with less work 3 improve the layouter so that A* has less to do I first tackled problem number 1. After profiling, it was clear that A* spent almost 80..90% of the time in managing its heap when the layout field is really big. So I changed the heap code from "sort if dirty before extract" to "always keep heap sorted". Even with only splitting the heap into two partitions upon insert it improved the timing quite a lot, now I implemented a hybrid between binary search and linear insert. It improves the performance between 20% to 60% depending on layout and complexity :) What the old code accomplished in 2 minutes is now done in under 40 seconds :) I also streamlined a few functions that are called a lot. For the second stage, I have had at least one idea. For instance it would be possible to restrict the playing field for the A* algortihm further - currently it is a rectangle defined by the two far outmost occupied cells. For large fields, this can create a lot of dead space on the outsides. If we restrict the field on a per-row and per-column based metric, the field would be smaller, the A* has less cells to expand to, so it does less trials and thus finishes earlier (and has less chance to exceed the maximum number). The path finding would then generate inward-bending paths at the outsides, but apart from the fact that it already does sometimes this, these will be corrected afterwards by the path straighten code. So it could work, but I have not yet implemented it to see how much it brings. Adjusting the layouter is item #3, and one idea I am banding about for a long time is to prevent the layouter from routing edges along nodes and thus blocking the sides of nodes. Two solutions: * make it possible for edges crossing also edges with a start field (so if one edge goes close by a node, an edge can still start at the node) * keep node ports free, so the edge can still start/end at the node Second option sounds cleaner, but is equally hard to implement. Without this change the layouter frequently paints itself into a corner, where routing an edge to/from a node becomes impossible. In your case, this also means that A* spents a *really* long time to find this out - and in the end can't place the edge anyway. So it needs fixing. Thank you again for your bug report! All the best, Tels -- Signed on Thu Apr 24 20:06:49 2008 with key 0x93B84C15. View my photo gallery: http://bloodgate.com/photos PGP key on http://bloodgate.com/tels.asc or per email. "Any sufficiently rigged demo is indistinguishable from an advanced technology." -- Don Quixote, slashdot guy
Download (untitled)
application/pgp-signature 481b

Message body not shown because it is not plain text.