[R] Intransitive DAG

[Ted Harding]

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 ------------------------------