Блог

Я строю большие направленные графы (используя igraph из R) и обнаружил странную проблему, при которой вершины, по-видимому, дублируются для определенных имен вершин. Эта проблема не возникает на небольших графах, и проблема возникает только тогда, когда имена вершин достигают 1e 05. Существует четкая закономерность для дублирующихся вершин. Чтобы забежать вперед, дублирование вершин выглядит следующим образом (сгенерировано в разделе 2 приведенного ниже кода):

     name_vertex id_cell id_vertex
 1:      100000  100000     97355
 2:       1e 05  100000   1435205
 3:      200000  200000    197106
 4:       2e 05  200000   1435206
 5:      400000  400000    396605
 6:       4e 05  400000   1435207
 7:      500000  500000    496356
 8:       5e 05  500000   1435208
 9:      700000  700000    695855
10:       7e 05  700000   1435209
11:      800000  800000    795606
12:       8e 05  800000   1435210
13:     1000000 1000000    995105
14:       1e 06 1000000   1435211
  

Дублирование происходит при достижении 1e 05, а затем для этой и каждой последующей вершины генерируются дубликаты, равные xe 0n, где x находится в 1: 9, а n равно > = 5 (обратите внимание, что в этом графике нет вершины с значением 3e 05 по построению — она лежит на матрицемаржа — и именно поэтому ее нет).

Все x0.. версии вершин содержат исходящие ребра, в то время как xe 0.. версии содержат входящие ребра.

Воспроизводимый пример: (примечание: способ, которым я генерирую фрейм данных смежности, в большей степени зависит от конвейера, который я использовал для генерации графиков для моего варианта использования. Предположительно, проблема может быть сгенерирована более непосредственно).

Приведенный ниже код генерирует матрицу, идентифицирует смежности каждой ячейки, а затем строит из них граф. Ячейкам на полях матрицы присваиваются значения 0, чтобы удалить их из таблицы смежности (чтобы предотвратить обертывание по краям).

Есть три раздела:

(1) запуск для размера матрицы 100×100: правильное поведение

(2) запуск для размера матрицы 1200×1200: дублирование

(3) устранение проблемы дублирования

ПРИМЕЧАНИЕ: для создания графика в (2) требуется около 30 секунд или около того и 3-4 ГБ оперативной памяти

 # packages
library(data.table); library(igraph)

# function to get adjacent cells in a matrix
get_adjacent <- function(cells, n_row, n_col) {
    adjacencies_i <- c(cells-n_row - 1, 
                       cells-n_row, 
                       cells-n_row 1, 
                       cells-1, 
                       cells 1, 
                       cells n_row-1, 
                       cells n_row, 
                       cells n_row 1)
    return(adjacencies_i)
}

# function to get the margins of a matrix (i.e. 1-deep outer margin of cells)    
get_margins <- function(matrix) {
    dims <- dim(matrix)
    bottom_right <- prod(dims)
    top_right <- (bottom_right - dims[1])
    c(1:dims[1], # first column 
      top_right:bottom_right, # last column
      seq(1, top_right, dims[1]), # top row
      seq(dims[1], bottom_right, dims[1])) # bottom row
}


# (1) Before creating the failure case, produce a much smaller graph that 
# has the correct behaviour

# generate a matrix of 1-valued cells
test_mat <- matrix(1, ncol=100, nrow=100)

# remove edge cells to prevent the adjacencies wrapping around the edges
test_mat[get_margins(test_mat)] <- 0

# plot: all black cells are those that should be represented in the graph, and 
# each of these cells should each be linked to their immediately adjacent neighbours 
# (including diagonals - see get_adjacent function)
image(test_mat, asp=1, col=c("red", "black"))

# calculate the adjacency dataframe to calculate a graph from
permitted_cells <- which(test_mat[] == 1)
n_row <- dim(test_mat)[1]
n_col <- dim(test_mat)[2]

# full set of adjacencies
adj <- data.table(from = rep(permitted_cells, (1*2   1)^2 - 1), 
                  to = get_adjacent(permitted_cells, n_row, n_col))
# remove those that are 0-valued
adj_permitted <- adj[to %in% permitted_cells,] 

# calculate graph
g <- graph_from_data_frame(adj_permitted[,list(from, to)], directed = T)

# get vertex names 
vertex_names <- names(V(g))
graph_vertices <- data.table(name_vertex = vertex_names, 
                             id_cell = as.integer(vertex_names), 
                             id_vertex = 1:length(vertex_names)) 
setorder(graph_vertices, id_cell)

# looks good: same number of vertices in graph as there are 1-valued cells in the 
# original matrix
print(paste0("n_vertices: ", nrow(graph_vertices)))
print(paste0("n_cells: ", sum(test_mat)))


## (2) failure case. Code is identical to the above, save for the dimensions of 
## the matrix being much larger (1200 rather than 100), and the image() function 
## is commented out. 

# generate a matrix of 1-valued cells
test_mat <- matrix(1, ncol=1200, nrow=1200)

# remove edge cells to prevent the adjacencies wrapping around the edges
test_mat[get_margins(test_mat)] <- 0

# plot: all black cells are those that should be represented in the graph, and 
# each of these cells should each be linked to their immediately adjacent neighbours 
# (including diagonals - see get_adjacent function)
# image(test_mat, asp=1, col=c("red", "black"))

# calculate the adjacency dataframe to calculate a graph from
permitted_cells <- which(test_mat[] == 1)
n_row <- dim(test_mat)[1]
n_col <- dim(test_mat)[2]

# full set of adjacencies
adj <- data.table(from = rep(permitted_cells, (1*2   1)^2 - 1), 
                  to = get_adjacent(permitted_cells, n_row, n_col))
# remove those that are 0-valued
adj_permitted <- adj[to %in% permitted_cells,] 

# calculate graph
g <- graph_from_data_frame(adj_permitted[,list(from, to)], directed = T)

# get vertex names 
vertex_names <- names(V(g))
graph_vertices <- data.table(name_vertex = vertex_names, 
                             id_cell = as.integer(vertex_names), 
                             id_vertex = 1:length(vertex_names)) 
setorder(graph_vertices, id_cell)

# there are 7 more vertices than there are 1-valued cells
print(paste0("n_vertices: ", nrow(graph_vertices)))
print(paste0("n_cells: ", sum(test_mat)))

print(paste0("n_extra_vertices: ", nrow(graph_vertices) - sum(test_mat)))

# (3) What are these extra vertices?
# get duplicated vertices
duplicated_vertices <- 
    graph_vertices[id_cell %in% graph_vertices[duplicated(id_cell),id_cell]]
setorder(duplicated_vertices, id_cell, id_vertex)

# the 7 additional vertices arise through duplication 
nrow(duplicated_vertices)
print(duplicated_vertices)

# xe .. version has the incoming edges
incoming <- adjacent_vertices(g, duplicated_vertices$id_vertex, mode="in")
incoming[unlist(lapply(incoming, function(x) length(x) != 0))]
# x0.. version has outgoing edges
outgoing <- adjacent_vertices(g, duplicated_vertices$id_vertex, mode="out")
outgoing[unlist(lapply(outgoing, function(x) length(x) != 0))]
  

Чтобы (наконец) перейти к вопросу. Что здесь происходит? Могу ли я что-нибудь сделать, чтобы предотвратить такое поведение? Обходной путь, который у меня есть в настоящее время, заключается в том, чтобы принимать входящие ребра, полученные xe 0.. версия и добавьте ребра к этим вершинам для версии x0.. перед удалением xe 0.. версия вершины.

Проблема, по-видимому, вызвана тем, что R (или igraph) приравнивает две формы 100000 и 1e 05 . Мне удалось решить эту проблему, добавив оператор options(scipen=99) в начале скрипта, который останавливает R от использования e обозначения.