igraph - получить все ребра, которые образуют путь между двумя вершинами - есть ли лучшее решение? - PullRequest
Новая
       84

igraph - получить все ребра, которые образуют путь между двумя вершинами - есть ли лучшее решение?

1 голос
/ 27 марта 2019

У меня есть график с разными трассами между контрольными точками (для трассировки).Пример может выглядеть следующим образом. 

library(ggraph)
library(igraph)
library(dplyr)

example_data = data.frame(start = c("D_2", "A_2", "A_2", "E_2", "G_2", "H_2", "G_2", "A_2", "B_2", "C_2", "C_2", "D_2"), 
                             end = c("D_1", "A_1", "B_1", "E_1", "G_1", "H_1", "F_1", "B_1", "A_1", "C_1", "C_1", "A_1"), 
                             length = rnorm(12, 100, 10),
                             difficulty = c("soft", "soft", "medium", "medium", "soft", "soft", "soft", "soft", "soft", "soft", "medium", "hard"),
                             trail = c(paste0("trail_", 1:11), "Fake_pist"), 
                             stringsAsFactors = F)

# relable connected end and start section points (sometimes the end of a trail is so close to the start of the next that they are seen as one point)
example_data$start[which(example_data$start %in%  c("D_1", "A_2"))] = "A_2_D_1"
example_data$end[which(example_data$end %in%  c("D_1", "A_2"))] = "A_2_D_1"

example_graph = graph_from_data_frame(example_data, directed = T)

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

p <- ggraph(example_graph) + 
  geom_edge_fan(aes(color = as.factor(difficulty), 
                    start_cap = label_rect(node1.name), 
                    end_cap = label_rect(node2.name),
                    label = trail), arrow = arrow(type = "closed", length = unit(3, 'mm')),
                angle_calc = 'along') + 
  geom_node_text(aes(label = name)) + 
  ggtitle('An example') +
  scale_edge_colour_manual(values = c("red", "yellow", "green"))
p

Для первопроходца я хочу выяснить, какие возможные пути он может пройти от начальной точки до конечной точки, и я хочу знать длину, сложность и так далее этих трасс.Например, если бегун начинает с D_2 и хочет добраться до B_1, ему сначала нужно пройти trail_1, чтобы достичь A_2_D_1, а затем выбрать между trail_8 и trail_3, чтобы достичь B_1.Таким образом, возможны следующие пути: D_2 -> A_2_D_1 -> B_1 (в форме вертикали) trail_1 -> trail_8 или trail_1 -> trail_3 (в форме ребра)

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

Улучшаемая функция: 

# get all simple path (== desired results but in Vertix-form )
l = all_simple_paths(example_graph, from = "D_2", to = "B_1", mode = "out")
l

l2 = all_simple_paths(example_graph, from = "D_2", to = "A_1", mode = "out")
l2



my_get_edges = function(temp_vertix, temp_graph)
{
  # convert graph to data.frame
  temp_graph_df = igraph::as_data_frame(temp_graph, what="edges")

  # If the overall path consists of more than just 1 trail.
  temp_vertix = names(temp_vertix)
  if(length(temp_vertix) > 2)
  {
    # create matrix with each row beeing start-vertix, end-vertix for every trail of the whole path
    temp_vertix = c(temp_vertix[1], rep(temp_vertix[-c(1, length(temp_vertix))], each = 2), temp_vertix[length(temp_vertix)])
    temp_vertix = matrix(temp_vertix, ncol = 2, byrow = T)
  } else
  {
    temp_vertix = matrix(temp_vertix, ncol = 2, byrow = T)
  }

  # filter those rows from the data.frame that match the start and stop vertix
  temp_edges = apply(temp_vertix, 1, function(f) temp_graph_df %>% filter(from == f[1], to == f[2]))

  return(temp_edges)
}

lapply(l, my_get_edges, example_graph)

lapply(l2, my_get_edges, example_graph)

Заранее спасибо

...