Graph::delete_vertex should not use _edges_at (in all cases)

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/

Received on Thursday, 23 January 2014 23:03:16 UTC