Как выбрать определенные пути в зависимости от их длины до узла - PullRequest
Новая
       26

Как выбрать определенные пути в зависимости от их длины до узла

1 голос
/ 08 января 2020

Я прочитал этот отличный пост о sf и tidygraph, https://www.r-spatial.org//r/2019/09/26/spatial-networks.html

Они создали объект графа с функцией sf_to_tidygraph, описанной в посте. Вот простой воспроизводимый пример 

nodes <- tibble("NodeID" = 1:4)
edges <- tibble("from" = c(1, 1,2,3,2), "to" = c(2, 3,3,4,4), "edgeID" = 1:5, 
            "length" = c(100, 200, 100, 200, 50))
graph <- tbl_graph(nodes = nodes, edges = edges, directed = FALSE)

Я хотел бы выбрать все пути на основе их длины для определенного c узла , а не только кратчайшие пути. Для кратчайших путей у меня есть следующий код: 

distances <- distances(
    graph = graph,
    weights = graph %>% activate(edges) %>% pull(length)
    )

 table_distance <- 
      distances %>% 
      as_tibble() %>% 
      rownames_to_column("from") %>% 
      pivot_longer(2:5, names_to = "to", values_to = "distance") %>% 
      mutate(to = substring(to, 2))

 nodes_inf_300_to_node_1 <- table_distance %>% 
     filter(from == "1") %>% 
     filter(distance <= 300)  %>% 
     pull(to)

 path <- shortest_paths(graph, from = 1,
                   to = nodes_inf_300_to_node_1,
                   output = 'both',
                   weights = graph %>% 
                     activate(edges) %>% 
                     pull(length))

объект «путь» дает мне весь кратчайший путь от узла 1 к узлам, которые находятся ниже расстояния 300.

Но не все пути от узла 1 до расстояния не более 300 м. Есть ли функция igraph, которую я пропускаю, или другое решение?

Я мог бы сделать: 

 all_simple_paths(graph, 1, nodes_inf_300_to_node_1)

и затем вычислить длину каждого пути

Но функция all_simple_path слишком длинный для сложного графа

all_simple_paths с аргументом отсечения (max) и аргументом веса

https://github.com/igraph/igraph/issues/774

...