[R] Intransitive DAG

[Thomas S. Dye]

Peter Langfelder <peter.langfelder at gmail.com> writes:

> On Mon, Jul 11, 2011 at 12:28 PM, Thomas S. Dye <tsd at tsdye.com> wrote:
>> Aloha all,
>>
>> I have an adjacency matrix for an acyclic digraph that contains
>> transitive relations, e.g. (u,v), (v,w), (u,w).  I want a DAG with only
>> intransitive relations.  Can someone point me to an R function that will
>> take my adjacency matrix and give me back one with only intransitive
>> relations?  In the example, I'd like to get rid of (u,w) and keep (u,v)
>> and (v,w).
>
> I assume your adjacency matrix is unweighted, i.e. contains only
> entries 0 and 1.
>
> Don't know of a function, but the algorithm isn't very difficult - if
> no one suggests a better way, just code it yourself. For example, for
> 3 variables, start with vector c(1, 0, 0). If you multiply it by the
> adjacency matrix, you will get c(0, 1, 1), that is, u is connected to
> v and w. If you multiply it by the adjacency again, you will get
> c(0,0,1) because v is connected w but w is not connected to anything.
> So you can get from u to w in two steps (via v) and so the link (u, w)
> should be deleted. For a 3x3 adjacency that's all you get but if you
> have more nodes, simply continue multiplying by the adjacency and
> deleting edges from the starting link to whatever has a 1 in one of
> the resulting vectors. You need to multiply at most n-1 times since an
> DAG cannot have a path length more than n-1. Then do the same thing
> starting from c(0,1,0), starting from c(0,0,1) etc.
>
> If my algorithm doesn't work I apologize :)
>
> HTH
>
> Peter

Aloha Peter,

Yes, that does seem to work.  I was hoping there was a simple answer.

Thanks!

Tom
-- 
Thomas S. Dye
http://www.tsdye.com