установить направление в ориентированном графе - PullRequest
Новая
       15

установить направление в ориентированном графе

2 голосов
/ 14 апреля 2020

У меня есть следующий неориентированный график g, полученный из шейп-файла реки. Я хочу преобразовать g в ориентированный граф, где вершина 55 - это root, а "направление" всех ребер направлено к вершине root (представьте себе поток воды из всех частей сети в направлении root).

Пример неориентированного графа: 

library(igraph)

g <- structure(list(From = c(48, 37, 39, 32, 38, 36, 49, 46, 31, 26, 
      33, 35, 18, 23, 45, 41, 42, 47, 52, 51, 50, 54, 16, 14, 8, 10, 
      5, 6, 17, 11, 20, 24, 2, 3, 1, 0, 44, 4, 7, 29, 30, 34, 40, 53, 
      43, 15, 9, 28, 27, 12, 13, 19, 21, 22, 25), To = c(32, 32, 31, 
        31, 33, 33, 45, 45, 23, 23, 26, 26, 16, 16, 35, 35, 41, 41, 50, 
        50, 47, 47, 6, 6, 5, 5, 2, 2, 10, 10, 11, 11, 1, 1, 0, 55, 30, 
        3, 3, 28, 28, 29, 29, 40, 40, 7, 7, 22, 22, 9, 9, 13, 13, 19, 
        19)), class = "data.frame", row.names = c(NA, -55L))

g <- graph.data.frame(g, directed = FALSE) 

l <- igraph::layout_as_tree(g, flip.y = FALSE)
plot(g,
    vertex.size = 10,
    vertex.color = "darkgray",
    layout = l)

Я могу сделать следующее, чтобы создать ориентированный граф, но некоторые ребра направлены в правильном направлении, а другие - нет. 

g2 <- get.adjacency(g, sparse = F)
g2[upper.tri(g2)] <- 0
g2 <- igraph::graph.adjacency(g2)

plot(g2,
      vertex.size = 10,
      vertex.color = "darkgray",
      layout = l)

enter image description here

Я вижу проблему в результате того, что вершины в матрице смежности помечены, но не могут найти решение.

Мой вопрос: возможно ли преобразовать неориентированный граф в ориентированный граф, где направление всех ребер ориентировано в направлении выбранной вершины (в данном случае вершины 55)?

Хорошо, если вершины получаются переименован et c.

1 Ответ

2 голосов
/ 14 апреля 2020

Для каждого ребра, соединяющего вершины a и b, если кратчайшее расстояние от a до 55 короче, чем кратчайшее расстояние от b до 55, чем b должно идти в направлении a. Я не знаком с igraph, но я нашел способ, основанный на этом обосновании: 

d <- distances(g)[, '55']
dd <- outer(d, d, FUN = '>')

g2 <- get.adjacency(g, sparse = F)
g2 <- g2 * dd
g2 <- igraph::graph.adjacency(g2)

plot(g2,
    vertex.size = 10,
    vertex.color = "darkgray",
    layout = l)

enter image description here

Примечание: направление все стрелки можно перевернуть, изменив outer(d, d, FUN = '>') на outer(d, d, FUN = '<').

...