On 11-Jul-11 19:28:12, Thomas S. Dye 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). > > All the best, > Tom > -- > Thomas S. Dye > http://www.tsdye.com
A quick question, for clarification. Your problem, as posed, is ambiguous, and there would need to be some mark in the data to distinguish between relations that are listed because transitivity implies them, and relations which complete a transitivity involving other relations but which have an independent existence in their own right. That is to say, there are two reasons in yo9ur example why (u,w) would be rthere: A: It is there because (u,v) and (v,w) were externally given (e.g. each is a one-way road between two points, (u -> v) and (v -> w), say, and (u,w) is there because you can go from u to w via v). Diagrammatically: "u -> v -> w" is the map of the roads. B: All three of (u,v), (v,w), and (u,w) are given, i.e. there are three roads (u -> v), (u -> w) and (v -> w). Diagrammatically (view in fixed-width font): _ v /| \ / \ / _\| u ------> w is the map of the roads. As I understand you question, in case (A) you would want to delete (u,w) because it is only there by virtue of being implied by (u,v) and (v,w) and transitivity. However, in case (B), where (u,w) really exists in the real world (whether or not implied by (u,v) and (v,w) and transitivity), do you really want to delete (u,w)? If, in case (B), you would want to keep (u,w), then there needs to be some marker to distinguish it as a "case (B)" link rather than a "case (A)" link. But if you did not want to keep (u,w) even though it exists, becaused it is implied by (u,v) and (v,w), then I think you are in the following situation. One of the ambiguities in your question is whether a relation is there because it "really exists" (even if also implied by other relations), or whether your data matrix contains all the relations, not only those which "really exist" but also those that do not "really exist" but are implied by the ones which do "really exist". If in fact what you really want to do is to extract a "minimal set" of directed relations, such that none of them is implied by the existence of the others and transitivity, and all relations in the original adjacency matrix are implied by the ones you keep, then I think that (a) it is possible, but in general does not have a unique solution; (b) there may be somewhere in R a function or package that can do it (but I can't at the moment think where to look for it). However, if you could clarify the above questions, it would certainly help to define a better starting focus. Ted. -------------------------------------------------------------------- E-Mail: (Ted Harding) <ted.hard...@wlandres.net> Fax-to-email: +44 (0)870 094 0861 Date: 11-Jul-11 Time: 23:22:14 ------------------------------ XFMail ------------------------------ ______________________________________________ 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.
