CODEWITHSUNDEEP
rgraphpathgrouping
ThatGuy
ThatGuy

Reputation: 1233

Find paths with only pairs of values

I have paired values representing paths and I want to be able to group these into those where the paths are joined. For example, I have:

    x  y
1:  1  2
2:  2  3
3:  4  5
4: 12 13
5: 13 14
6: 13 15
7: 13 16

And need to group these together such that 1-2-3, 4-5, and 12-13-14-15-16 are separated.

Ideal output would be a table something like this:

     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16]
[1,]    1    2    3    4    5    6    7    8    9    10    11    12    13    14    15    16
[2,]    1    1    1    2    2    3    4    5    6    7     8     9     9     9     9     9

Is there an algorithm that will do this efficiently in R?

Upvotes: 0

Views: 37

Answers (1)

ThatGuy
ThatGuy

Reputation: 1233

Thanks to @akrun, using the igraph package it is relatively simple:

g <- make_graph(c(1,2, 2,3, 4,5, 12,13, 13,14, 13,15, 13,16), directed = FALSE)
cbind(components(g)$membership, seq(1,16))

gives

     [,1] [,2]
 [1,]    1    1
 [2,]    1    2
 [3,]    1    3
 [4,]    2    4
 [5,]    2    5
 [6,]    3    6
 [7,]    4    7
 [8,]    5    8
 [9,]    6    9
[10,]    7   10
[11,]    8   11
[12,]    9   12
[13,]    9   13
[14,]    9   14
[15,]    9   15
[16,]    9   16

Upvotes: 3

Related Questions