Ordering objects in r based on their relationship

Question

I have a data frame containing 3 objects (A, B, C) that have the following relationships:

relationships<-data.frame(object.1=c("A","A","B"),object.2=c("B","C","C"),relationship=1:3) relationships object.1 object.2 relationship 1 AB 1 2 AC 2 3 BC 3 

Consider all possible permutations of A, B, C and estimates of relations between adjacent objects, i.e.

 A 1 B 3 C = 4 A 2 C 3 B = 5 C 2 A 1 B = 3 B 1 A 2 C = 3 B 3 C 2 A = 5 C 3 B 1 A = 4 

I need to determine the order of the objects that order the objects so that the relations of adjacent objects are as high as possible, going from left to right, i.e. for the example above, I would choose

 B 3 C 2 A = 5 

Any suggestions how should I do this? Thanks.

Answer 1

Is this close to what you are looking for?

 library(data.table) relationships<-data.table(object.1=c("A","A","B"),object.2=c("B","C","C"),relationship=1:3) relationships<-rbindlist(list(relationships,relationships[,list(object.1=object.2, object.2=object.1, relationship)])) setkey(relationships,object.1,object.2) perm<-CJ(C1=LETTERS[1:3],C2=LETTERS[1:3],C3=LETTERS[1:3])[!C1==C2 & !C1==C3 & !C2==C3] setkey(perm,C1,C2) perm[relationships,rel.1:=relationship] setkey(perm,C2,C3) perm[relationships,rel.2:=relationship] perm[order(-rel.1,-rel.2)] 

It is not very extensible as it is, but perhaps it can be expanded ...

Answer 2

This seems to be the shortest path in the graph task (i.e. the longest, but it doesn't matter) - try using igraph to treat your input as a real graph, then use shortest.paths to find the optimal connections, finally select this. which best fulfills your reduction criteria. (This is not an optimal solution, but the optimal one will probably need to write it in C or something like that).