portupgrade O(n^m)?

Joerg Sonnenberger joerg at britannica.bec.de
Thu Feb 15 12:35:38 UTC 2007


On Thu, Feb 15, 2007 at 01:17:58AM +0100, Michel Talon wrote:
> The problem is the so called topological sorting of a DAG which is of
> order (n+m) where n is the number of nodes and m the number of arrows in
> the DAG. In my python program pkgupgrade, i perform this sorting for
> the whole set of ports (16000 +) in a couple of seconds.

Actually, the topological sorting can be done lazily, it is pretty
instant. Been using Python as well :-) What took a while for me was
sorting the DAG after topological depth of the tree aka building
things first which have more depending packages. But even that is a job
done in a number of seconds.

Joerg


More information about the freebsd-hackers mailing list