[R] Intransitive DAG

[Thomas S. Dye]

(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