Peter Langfelder <peter.langfel...@gmail.com> writes: > 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
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 ______________________________________________ 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.
