From owner-freebsd-hackers@FreeBSD.ORG  Thu Feb 15 12:35:38 2007
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
X-Original-To: freebsd-hackers@freebsd.org
Delivered-To: freebsd-hackers@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52])
	by hub.freebsd.org (Postfix) with ESMTP id CB2D316A406
	for <freebsd-hackers@freebsd.org>; Thu, 15 Feb 2007 12:35:38 +0000 (UTC)
	(envelope-from joerg@britannica.bec.de)
Received: from shell.asta.uni-rostock.de (gateway.stura.uni-rostock.de
	[139.30.252.67])
	by mx1.freebsd.org (Postfix) with ESMTP id 8D2C413C481
	for <freebsd-hackers@freebsd.org>; Thu, 15 Feb 2007 12:35:37 +0000 (UTC)
	(envelope-from joerg@britannica.bec.de)
Received: from britannica.bec.de (unknown [192.168.16.3])
	by shell.asta.uni-rostock.de (Postfix) with ESMTP id BC95E187E
	for <freebsd-hackers@freebsd.org>; Thu, 15 Feb 2007 12:35:35 +0000 (GMT)
Received: by britannica.bec.de (Postfix, from userid 1000)
	id 32B2DB70C; Thu, 15 Feb 2007 13:35:34 +0100 (CET)
Date: Thu, 15 Feb 2007 13:35:34 +0100
From: Joerg Sonnenberger <joerg@britannica.bec.de>
To: freebsd-hackers@freebsd.org
Message-ID: <20070215123533.GA554@britannica.bec.de>
Mail-Followup-To: freebsd-hackers@freebsd.org
References: <20070215001758.GA32225@lpthe.jussieu.fr>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20070215001758.GA32225@lpthe.jussieu.fr>
User-Agent: Mutt/1.5.13 (2006-08-11)
Subject: Re: portupgrade O(n^m)?
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
	<freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>, 
	<mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Thu, 15 Feb 2007 12:35:38 -0000

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