From owner-freebsd-fs Tue Sep 24 01:53:55 1996 Return-Path: owner-fs Received: (from root@localhost) by freefall.freebsd.org (8.7.5/8.7.3) id BAA25675 for fs-outgoing; Tue, 24 Sep 1996 01:53:55 -0700 (PDT) Received: from parkplace.cet.co.jp (parkplace.cet.co.jp [202.32.64.1]) by freefall.freebsd.org (8.7.5/8.7.3) with ESMTP id BAA25647 for ; Tue, 24 Sep 1996 01:53:48 -0700 (PDT) Received: from localhost (michaelh@localhost) by parkplace.cet.co.jp (8.7.6/CET-v2.1) with SMTP id IAA21618; Tue, 24 Sep 1996 08:53:27 GMT Date: Tue, 24 Sep 1996 17:53:27 +0900 (JST) From: Michael Hancock Reply-To: Michael Hancock To: "Hr.Ladavac" cc: fs@FreeBSD.ORG Subject: Re: Transitive Closure--a Question for Terry In-Reply-To: <199609101109.AA067513751@ws2301.gud.siemens.co.at> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-fs@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk It summarizes information in a directed graph. There's a description in "Algorithms in C" by Robert Sedgewick. The book is also a good reference if you want to look at radix tries which are used in couple places in 4.4BSD. Regards, Mike Hancock On Tue, 10 Sep 1996, Hr.Ladavac wrote: > Hi all, especially Terry. > > The term "Transitive Closure" and its calculation has been > repeatedly mentioned in this forum (list, whatever.) > > My personal question is what does it mean to you. To be > honest, I've never stumbled upon the term before, and the > fact that the graph theory textbooks I read were in Russian > is probably no help either. > > My gut tells me it has to do with cycle detection/prevention > in a directed graph, but I cannot be sure. > > If so, the obvious algorithms to use are very simple, albeit > not deterministic in time, with the worst case of O(N**2) > IIRC. > > /Marino >