On Mon, Jul 11, 2011 at 12:28 PM, Thomas S. Dye <t...@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 ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
