From owner-freebsd-fs Tue Sep 10 04:14:54 1996 Return-Path: owner-fs Received: (from root@localhost) by freefall.freebsd.org (8.7.5/8.7.3) id EAA10238 for fs-outgoing; Tue, 10 Sep 1996 04:14:54 -0700 (PDT) Received: from zwei.siemens.at (zwei.siemens.at [193.81.246.12]) by freefall.freebsd.org (8.7.5/8.7.3) with ESMTP id EAA10225 for ; Tue, 10 Sep 1996 04:14:42 -0700 (PDT) Received: from sol1.gud.siemens.co.at (root@firix [10.1.143.100]) by zwei.siemens.at (8.7.4/8.7.3) with SMTP id NAA12516 for ; Tue, 10 Sep 1996 13:12:59 +0200 (MET DST) Received: from ws2301.gud.siemens.co.at by sol1.gud.siemens.co.at with smtp (Smail3.1.28.1 #7 for ) id m0v0Ql6-0001zPC; Tue, 10 Sep 96 13:13 MET DST Received: by ws2301.gud.siemens.co.at (1.37.109.16/1.37) id AA067513751; Tue, 10 Sep 1996 13:09:11 +0200 From: "Hr.Ladavac" Message-Id: <199609101109.AA067513751@ws2301.gud.siemens.co.at> Subject: Transitive Closure--a Question for Terry To: fs@freebsd.org Date: Tue, 10 Sep 1996 13:09:11 +0200 (MESZ) X-Mailer: ELM [version 2.4 PL24 ME8a] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: owner-fs@freebsd.org X-Loop: FreeBSD.org Precedence: bulk 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