| Subject: | Graph::delete_vertex should not use _edges_at (in all cases) |
| Date: | Fri, 24 Jan 2014 00:02:52 +0100 |
| To: | bug-graph [...] rt.cpan.org |
| From: | Bjoern Hoehrmann <derhoermi [...] gmx.net> |
Hi,
In Graph.pm v0.96 the `delete_vertex` function is excruciatingly slow,
at least for the graphs I usually handle. Devel::NYTProf told me this is
caused by _edges_at. I have also found that retrieving and deleting the
edges around a vertex I want to delete is very fast, so
sub delete_vertex_fast {
my $g = shift;
$g->expect_non_unionfind;
my $V = $g->[ $g->SUPER::_V ];
return $g unless $V->has_path( @_ );
$g->delete_edge($_[0], $_) for $g->successors($_[0]);
$g->delete_edge($_, $_[0]) for $g->predecessors($_[0]);
$V->del_path( @_ );
$g->[ $g->SUPER::_G ]++;
return $g;
}
is something I am considering using in a derived package. Testing shows
a speedup of an order of magnitude at least (and I intend to test this
is kept in proper working condition by cloning random graphs, deleting
the same random vertices in both of them, and comparing the result). If
a new maintainer is found for the module, I am happy to write a patch.
regards,
--
Björn Höhrmann · mailto:bjoern@hoehrmann.de · http://bjoern.hoehrmann.de
Am Badedeich 7 · Telefon: +49(0)160/4415681 · http://www.bjoernsworld.de
25899 Dagebüll · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/