8 messages · Thomas S. Dye, (Ted Harding), Peter Langfelder +1 more
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
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'm needing to guess at what sort of code you are using but assuming this is a square matrix: require(ggm) dag <- DAG(y ~ x, x ~ z, u~z) > which(dag != t(dag), arr.ind=TRUE) row col x 2 1 y 1 2 z 3 2 x 2 3 u 4 3 z 3 4
All the best, Tom -- Thomas S. Dye http://www.tsdye.com
______________________________________________ R-help at 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.
David Winsemius, MD West Hartford, CT
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.harding at wlandres.net> Fax-to-email: +44 (0)870 094 0861 Date: 11-Jul-11 Time: 23:22:14 ------------------------------ XFMail ------------------------------
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
David Winsemius <dwinsemius at comcast.net> writes:
On Jul 11, 2011, at 3:28 PM, 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).
I'm needing to guess at what sort of code you are using but assuming this is a square matrix: require(ggm) dag <- DAG(y ~ x, x ~ z, u~z)
which(dag != t(dag), arr.ind=TRUE)
row col x 2 1 y 1 2 z 3 2 x 2 3 u 4 3 z 3 4
Aloha David, Thanks for this suggestion. I don't think it does what I want. Sorry if I wasn't precise. The graph theory language is new to me. What I'm looking for is a function that gets rid of transitive relations, like so: tdye> dag <- DAG(v ~ u, w ~ v, w ~ u) tdye> dag v u w v 0 0 1 u 1 0 1 w 0 0 0 tdye> dag[2,3] <- 0 tdye> dag v u w v 0 0 1 u 1 0 0 w 0 0 0 All the best, Tom
All the best, Tom -- Thomas S. Dye http://www.tsdye.com
______________________________________________ R-help at 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.
David Winsemius, MD West Hartford, CT
Thomas S. Dye http://www.tsdye.com
David Winsemius <dwinsemius at comcast.net> writes:
On Jul 11, 2011, at 3:28 PM, 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).
I'm needing to guess at what sort of code you are using but assuming this is a square matrix: require(ggm) dag <- DAG(y ~ x, x ~ z, u~z)
which(dag != t(dag), arr.ind=TRUE)
row col x 2 1 y 1 2 z 3 2 x 2 3 u 4 3 z 3 4
Aloha David, Thanks for this suggestion. I don't think it does what I want. Sorry if I wasn't precise. The graph theory language is new to me.
It appears to me to be new as well. I imagined that w ~ u and u~w would be the definition of "transitive" when directed was a modifier, but apparently there are mathematical constructions that are more complex than I imagined.
What I'm looking for is a function that gets rid of transitive relations, like so: tdye> dag <- DAG(v ~ u, w ~ v, w ~ u) tdye> dag v u w v 0 0 1 u 1 0 1 w 0 0 0 tdye> dag[2,3] <- 0 tdye> dag v u w v 0 0 1 u 1 0 0 w 0 0 0 All the best, Tom
All the best, Tom -- Thomas S. Dye http://www.tsdye.com
______________________________________________ R-help at 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.
David Winsemius, MD West Hartford, CT
-- Thomas S. Dye http://www.tsdye.com
David Winsemius, MD West Hartford, CT
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
(Ted Harding) <ted.harding at wlandres.net> writes:
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.harding at wlandres.net> Fax-to-email: +44 (0)870 094 0861 Date: 11-Jul-11 Time: 23:22:14 ------------------------------ XFMail ------------------------------
Aloha Ted, Interesting. My matrix codes stratigraphic relations in an archaeological site, so all the relations are real and not there because they are implied by other relations. In some cases a feature is, say, younger than two other features, but we know the relative ages of those two features. I want to keep the relationship with the younger of the two and get rid of the relationship with the older of the two. Peter's matrix multiplication solution appears to work for my case. Thanks for the thoughtful response. All the best, Tom
Thomas S. Dye http://www.tsdye.com