search

mdickinson / refcycle

Support for displaying and analyzing reference graphs of Python objects.
Apache License 2.0
15 stars 1 forks source link

AnnotatedGraph.strongly_connected_components is slow. #24

Closed mdickinson closed 10 years ago

mdickinson commented 10 years ago

... took several seconds for a graph of size 8000 or so; this feels as though there's some nonlinear behaviour going on somewhere.

mdickinson commented 10 years ago

The issue is probably in the implementation of full_subgraph, which iterates over all edges to decide which ones to add. That's unnecessary (doubly so, because the algorithm for computing strongly connected components finds the edges naturally; we're currently throwing that information away only to reconstruct it later).