R igraph: алгоритм для нахождения иерархии между определенными ребрами в DAG

ProgramBox

R igraph: алгоритм для нахождения иерархии между определенными ребрами в DAG

Post author:admin
Запись опубликована:13 июля, 2022
Post category:Вопросы по программированию

#r #graph-theory #igraph

#r #теория графов #igraph

Вопрос:

У меня есть ориентированный граф (DAG), представляющий речную сеть. На некоторых реках (ребрах) есть станции измерения расхода. Я хотел бы ранжировать эти станции в соответствии с их иерархией из самых верхних сегментов реки. Большинство станций, находящихся выше по течению, будут иметь класс 1. Станции, имеющие только 1 ранг станции выше по течению, будут иметь класс 2, станции с 2 рангами станций выше по течению будут иметь класс 3 и так далее. Есть ли в igraph алгоритм для этого? Я искал в документе такие термины, как «ранг», «иерархия», «порядок», но не нашел ничего похожего на то, что я хотел бы выполнить.

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

Есть какие-либо предложения по алгоритму графа для этого?

Вот иллюстрация классификации:

Вот данные, которые я использую для тестирования (НЕ связанные с изображением):

 library(igraph)

vertices_df <- data.frame(
  id = c(418,410,402,394,386,427,378,370,362,354,346,338,330,322,314,306,298,290,282,274,595,266,419,395,258,250,242,234,226,218,210,202,194,186,178,170,162,146,138,130,122,114,106,98,90,82,74,66,58,50,42,34,26,18,10,2,587,579,571,563,555,547,539,531,523,515,28,12,154,507,499,491,483,475,467,459,451,443,435,411,403,387,379,371,363,355,347,339,331,323,315,307,299,291,283,275,267,259,251,243,235,227,219,211,203,195,187,179,171,163,155,147,139,131,123,115,107,99,91,83,75,67,59,51,43,35,27,19,11,3,20,4),
  station = c(1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0)
)

edges_df <- data.frame(
  from = c(410,402,394,378,427,403,370,362,354,346,338,330,322,314,306,298,290,282,274,595,587,395,107,3,250,218,226,26,58,66,146,34,18,98,106,74,130,507,571,563,443,547,539,531,523,515,28,20,499,491,483,475,467,459,451,435,411,355,387,379,347,371,331,307,195,291,115,147,171,43,99,123,227,259,27,2,234,10,386,419,194,202,186,122,170,162,258,178,266,242,114,210,154,11,75,90,42,82,50,138,579,67,323,555,179,211,243,219,267,12,4,35,315,363,19,299,51,187,91,155,275,163,339,203,283,131,139,59,83,235,251),
  to = c(418,410,402,394,386,427,378,370,362,354,346,338,330,322,314,306,298,290,282,274,595,266,419,395,258,250,242,234,226,218,210,202,194,186,178,170,162,587,579,571,563,555,547,539,531,523,515,28,507,499,491,483,475,467,459,451,443,435,411,403,387,379,371,363,355,347,339,331,323,315,307,299,291,283,275,418,410,402,394,386,370,362,354,346,338,330,322,314,306,298,282,274,595,419,395,250,234,226,218,210,587,579,571,563,555,547,539,531,523,515,28,507,491,483,467,459,451,443,435,411,403,387,379,355,347,331,323,307,299,291,283)
)

net <- graph.data.frame(
  edges_df[, c("from", "to")],
  directed=TRUE,
  vertices=vertices_df
)

Так что я знаю края 418, 394, 386, 499, 355, 331, 35 у меня есть станции, и я хотел бы ранжировать их по атрибутам 1, 2, 3, 4…

После того, как я попробовал алгоритм «расстояния» и «topo_sort» в igraph, моей последней попыткой было использовать dfs:

 res <- dfs(
  net,
  root = "418",
  neimode = "in",
  unreachable = TRUE,
  order = TRUE,
  order.out = TRUE,
  father = TRUE,
  dist = TRUE
)

res$dist[names(res$dist) %in% as.character(vertices_df[vertices_df$station == 1, "id"])]

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

Я бы предпочел использовать R, поскольку другие части рабочего процесса находятся на этом языке…

1. Пожалуйста, поделитесь воспроизводимым примером

2. Не могли бы вы предоставить (1) небольшую иллюстрацию, объясняющую проблему и ожидаемый результат; фотография доски идеальна (2) небольшой пример данных в любом формате.

3. Также сообщите нам, на каком языке программирования вы используете igraph.

4. Похоже, вам в основном нужно число Стралера, за исключением только станций, а не других частей графика. Правильно? en.wikipedia.org/wiki/Strahler_number

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

Ответ №1:

Вы можете попробовать приведенный ниже код

 # subset vertices of interest, i.e., `station == 1`
v <- as.character(with(vertices_df, id[station == 1]))

# find the sink node among `v`
snk <- v[which(colSums(distances(net, v, v, "out") == Inf) == 0)]

# find the paths to the sink node from all other nodes and assign ranks along the path
lst <- lapply(
  v[!v %in% snk],
  function(p) {
    s <- intersect(names(shortest_paths(net, p, snk)$vpath[[1]]), v)
    data.frame(id = s, vrank = seq_along(s))
  }
)

# aggreagte all info and take the max rank for each id
dfout <- aggregate(. ~ id, do.call(rbind, lst), max)

и вы увидите

 > dfout
   id vrank
1 331     1
2  35     1
3 355     1
4 386     2
5 394     3
6 418     4
7 499     2