подкомпонент (mode = "in") для нескольких исходных вершин - PullRequest
Новая
       27

подкомпонент (mode = "in") для нескольких исходных вершин

0 голосов
/ 07 января 2019

Вопрос

В пакете igraph R существует ли эффективная реализация subcomponent() и / или BFS, которая может обрабатывать несколько исходных вершин?

Мотивация

Пакет drake R моделирует рабочий процесс пользователя как DAG взаимозависимых объектов и файлов. Группа обеспечения доступности баз данных должна содержать только цели пользователя и их исходные зависимости, поэтому drake использует igraph::subcomponent() для устранения лишних вершин. Этот подход неэффективен, потому что аргумент v должен быть одной вершиной, поэтому drake заканчивает тем, что проводит новую BFS для каждой цели, которую хочет построить пользователь.

РЕДАКТИРОВАТЬ: 2019-01-10

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

1 Ответ

0 голосов
/ 10 января 2019

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

Пример кода: 

library(igraph)
library(microbenchmark)

# generate some random testing data
set.seed(1234)
g <- erdos.renyi.game(50, .01)

# Here we make a function that iterates 
# across the vector of IDs applying the function
# and returns a list where each element is the
# ids of the subcomponents
sc_apply <- function(g) {
  vs <- V(g)
  res <- sapply(vs, function(v){as.numeric( # to facilitate comparison
    subcomponent(g, v, mode = "in")
    )})
  res
}

# Try it for testing
t1 <- sc_apply(g)

# Here we get the matrix of node distances. Infinite distance
# implies a seperate component. We iterate through rows of
# matrix to extract the set of nodes that are connected 
sc_distmat <- function(g) {
  dmat <- distances(g, mode = "in")
  res <- apply(dmat, 1, function(row){which(is.finite(row))})
  res
}

# extract for testing
t2 <- sc_distmat(g)

# check that equal (we need to sort the 
# subcomponent list elements first to facilitate comparison)
all.equal(lapply(t1, sort), t2)
#> [1] TRUE

Результаты идентичны - хотя стоит отметить, что если ваш график представляет собой один гигантский компонент, то применение apply вернет вам матрицу, а не список, поэтому вам придется выполнять сравнения немного другим способом.

Хорошо, теперь давайте посмотрим, насколько / быстрее это: 

# generate graphs of different sizes (not too big because my
# laptop is borderline antique!)
set.seed(42)
small_g <- erdos.renyi.game(10, .2)
mid_g <- erdos.renyi.game(50, .1)
big_g <- erdos.renyi.game(100, .1)

# check speed improvement
microbenchmark(sc_apply(small_g), sc_distmat(small_g))
#> Unit: microseconds
#>                 expr      min        lq      mean   median        uq
#>    sc_apply(small_g) 2181.465 2243.4895 2734.7132 2313.005 2777.7135
#>  sc_distmat(small_g)  451.333  471.8565  840.4742  521.865  598.0845
#>        max neval cld
#>   9152.262   100   b
#>  27139.262   100  a
microbenchmark(sc_apply(mid_g), sc_distmat(mid_g))
#> Unit: microseconds
#>               expr       min        lq       mean    median         uq
#>    sc_apply(mid_g) 11006.113 11327.794 13590.9536 12919.492 15397.2510
#>  sc_distmat(mid_g)   757.752   795.308   949.2551   841.834   965.4545
#>        max neval cld
#>  27068.296   100   b
#>   2061.824   100  a
microbenchmark(sc_apply(big_g), sc_distmat(big_g))
#> Unit: milliseconds
#>               expr      min        lq      mean    median        uq
#>    sc_apply(big_g) 23.11678 26.696373 29.940675 29.191045 33.012796
#>  sc_distmat(big_g)  1.67531  1.727873  2.156307  1.855994  2.244872
#>        max neval cld
#>  47.081647   100   b
#>   7.576123   100  a

Как вы можете видеть, подход distances() становится все быстрее и быстрее с ростом размера графика.

Создано в 2019-01-10 пакетом Представление (v0.2.1)

...