Date: Thu, 15 Feb 2007 13:35:34 +0100 From: Joerg Sonnenberger <joerg@britannica.bec.de> To: freebsd-hackers@freebsd.org Subject: Re: portupgrade O(n^m)? Message-ID: <20070215123533.GA554@britannica.bec.de> In-Reply-To: <20070215001758.GA32225@lpthe.jussieu.fr> References: <20070215001758.GA32225@lpthe.jussieu.fr>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20070215123533.GA554>