Re: transitive closure again
From: paul c <toledobythesea_at_oohay.ac>
Date: Sat, 05 Nov 2005 00:32:16 GMT
Message-ID: <k4Taf.405431$1i.385457_at_pd7tw2no>
>
>
> Here is a slightly different (and amusing) perspective. Transitive
> closure T of graph G is a formal power series
>
> T = 1 + G + G^2 + G^3 + ...
>
> This equation has standard interpretation where each T and G is an
> adjacency matrix for a graph. Is this equation useful at all? Let's
> extract factor G on the left side
>
> T = 1 + G (1 + G + G^2 + ...)
>
> which gives the recurrence equation
>
> T = 1 + G T
>
> which is essentialy the same as
>
> T = (1 - G)^(-1)
>
> (This is a valid trick for acyclic graphs only. Why?)
>
> If nothing else, the last equation allows calculating transitive
> closure via formal matrix operations.
>
> In the context of Paul's question, starting from this equation perhaps,
> we can deduce a another formula that represents G in terms of T? Well,
> without any clever idea by just rearranging terms I've got
>
> G = 1 - T^(-1)
>
> which seems lead nowhere. The trick is another recurrence formula
>
> T = G + T^2
>
> which you can verify by expanding the T and expanding T^2 into a
> series.This is the exact answer:
>
> G = T - T^2
>
> "the original graph edges are those in transitive closure graph except
> those that are compositions of nodes (x,z) (z,y)"
>
Received on Sat Nov 05 2005 - 01:32:16 CET
Date: Sat, 05 Nov 2005 00:32:16 GMT
Message-ID: <k4Taf.405431$1i.385457_at_pd7tw2no>
Many thanks. Seems neat (and clever). I'll try to reconcile it. (If it's of any interest, I had in mind always keeping the closure in a 'base' relation and using a view of the adjacency relation to update the base - with the right constraints of course. Even though it appears to involve what could be a moderately large join, the right engine shouldn't have trouble optimizing it and this would happen only at update time anyway).
cheers,
pc
Vadim Tropashko wrote:
> Mikito Harakiri wrote:
>
>>paul c wrote: >> >>>If we have a relation that is the closure (including trivial >>>relationships if necessary), can we obtain what Mikito (if I recall), >>>calls the adjacency list, using the RM algebra but without recursion? >> >>Seems easy: for all pairs of nodes making an edge (x,y ) in the TC >>graph, select only those that aren't represented as (x,z) & (z,y).
>
>
> Here is a slightly different (and amusing) perspective. Transitive
> closure T of graph G is a formal power series
>
> T = 1 + G + G^2 + G^3 + ...
>
> This equation has standard interpretation where each T and G is an
> adjacency matrix for a graph. Is this equation useful at all? Let's
> extract factor G on the left side
>
> T = 1 + G (1 + G + G^2 + ...)
>
> which gives the recurrence equation
>
> T = 1 + G T
>
> which is essentialy the same as
>
> T = (1 - G)^(-1)
>
> (This is a valid trick for acyclic graphs only. Why?)
>
> If nothing else, the last equation allows calculating transitive
> closure via formal matrix operations.
>
> In the context of Paul's question, starting from this equation perhaps,
> we can deduce a another formula that represents G in terms of T? Well,
> without any clever idea by just rearranging terms I've got
>
> G = 1 - T^(-1)
>
> which seems lead nowhere. The trick is another recurrence formula
>
> T = G + T^2
>
> which you can verify by expanding the T and expanding T^2 into a
> series.This is the exact answer:
>
> G = T - T^2
>
> "the original graph edges are those in transitive closure graph except
> those that are compositions of nodes (x,z) (z,y)"
>
Received on Sat Nov 05 2005 - 01:32:16 CET