[R] Intransitive DAG

[Peter Langfelder]

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