Как объединить повторяющиеся узлы в один узел?

Question

Этот вопрос является продолжением вопроса .

У меня есть n точек с (x, y) координатами, организованными в виде матрицы:

A <- t(matrix(c(
 0, 0, 1, 0, 1,-1, 1,-2, 0,-2,-1,-2,-2,-2,-2,-1,-1,-1, 0,-1, 0, -2, 0,-3,
 0,-4,-1,-4,-1,-3,-1,-2, 0,-2, 1,-2, 2,-2, 2,-3, 1,-3, 0,-3, 0,-2, 0,-1, 0, 0), nrow =2)); 

Как видите, k=8 пары повторяли (x,y) координаты.

Edit.

ids <- which(duplicated(A))
k <- length(ids)

Я создал объект igraph g и построил его. Узлы с повторяющимися координатами обозначены красным цветом на рисунке. Некоторые из них повторяются дважды, а некоторые три или даже четыре раза.

library(igraph)
g <- make_empty_graph(n=nrow(A)) 
g <- g + path(seq_len(nrow(A))) 

V(g)$id    <- seq_len(vcount(g))
V(g)[V(g)$id %in% ids]$color <- "red"


plot(g, layout=as.matrix(A),
     edge.arrow.size = 0.3,
     edge.curved = TRUE
)

Мне нужно объединить узлы с повторяющимися координатами в один узел.

Вопрос. Можно ли объединить узлы с повторяющимися координатами в один узел? Повторные ребра также должны быть объединены в одно ребро. Направление кромок может быть опущено.

Answer 1

После моего комментария и дальнейших исследований мне удалось уменьшить ваш график. Это было не тривиально, так как мне пришлось явно указать igraph, какие узлы я хочу объединить с помощью вектора идентификатора, то есть: если у вас есть четыре узла с идентификаторами c (1,2,3,4) и вы хотите объединить первый три из них, вы должны дать следующий вектор id: c (1,1,1,2).

Я также использовал библиотеку data.table , так как я более знаком с ее синтаксисом.

Код, который я использовал:

dt <- as.data.table(A)
groupID <- dt[,.(gID = .GRP),by = list(dt$V1,dt$V2)]
colnames(dt) <- c('X','Y')
colnames(groupID) <- c('X','Y','gid')

dt[groupID, gID := i.gid, on = c(X = 'X', Y = 'Y')]

plot(contract.vertices(g,dt$gID),layout = as.matrix(groupID))

Я преобразовал данную матрицу m в таблицу data.table, затем создал другой dt ( data.table ) для идентификаторов группы, поэтому у вас есть отдельный идентификатор для каждого группа, созданная уникальными комбинациями координат (у вас есть идентификатор для каждого [-2,0], еще один для каждого [0,0] и т. д.)

Итак, groupID dt выглядит так:

     X  Y gid
 1:  0  0   1
 2:  1  0   2
 3:  1 -1   3
 4:  1 -2   4
 5:  0 -2   5
 6: -1 -2   6
 7: -2 -2   7
 8: -2 -1   8
 9: -1 -1   9
10:  0 -1  10
11:  0 -3  11
12:  0 -4  12
13: -1 -4  13
14: -1 -3  14
15:  2 -2  15
16:  2 -3  16
17:  1 -3  17

После этого я просто переименовал столбцы для дальнейших преобразований.

Следующим шагом было объединение двух точек в их общих столбцах X и Y , которым я дал новое имя прямо перед этим.

DT теперь выглядит так:

     X  Y gID
 1:  0  0   1
 2:  1  0   2
 3:  1 -1   3
 4:  1 -2   4
 5:  0 -2   5
 6: -1 -2   6
 7: -2 -2   7
 8: -2 -1   8
 9: -1 -1   9
10:  0 -1  10
11:  0 -2   5
12:  0 -3  11
13:  0 -4  12
14: -1 -4  13
...

Последним шагом было объединение узлов по их идентификаторам с функцией contract.vertices . Атрибут gID объединенного dt должен быть задан как атрибут, поэтому он знает, какие узлы должны быть объединены. (Вы можете присвоить это переменной g ofc.)

К счастью, groupID dt содержит правильный макет для вашего графика, поскольку в нем есть группы (ваши координаты) и их идентификатор.

Теперь узлы объединены, но есть еще несколько ребер от объединенных вершин до их соседей, после чего их необходимо удалить.

После преобразований график выглядит так:

Соответствующие сообщения:

• Как получить индекс каждой группы dt
• Объединить узлы с contract.vertices