Блог

Мне интересно, есть ли способ вычислить длину пути из графа или сети, исключая пути между промежуточными вершинами (с входящими и исходящими ребрами). Я работаю с библиотекой igraph R (http://igraph.org/r/doc /), но другие R-решения также приветствуются.

Итак, учитывая следующий ориентированный граф:

 require(igraph)
edges= graph.formula(A -  B,
                     A -  C,
                     B -  C,
                     C -  D,
                     B -  D,
                     D -  E)
  

Я стремлюсь узнать длины следующих путей:

• A-B-C-D-E (4)
• A-B-D-E (3)
• A-C-D-E (3)

Я могу выбрать интересующие меня пути с помощью следующей igraph функции:

 all_simple_paths(edges, from="A", to="E")
  

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

Итак, мне нужно было бы иметь возможность:

1. Определите все начальные и конечные вершины нескольких подграфов.
2. Получить все возможные пути между каждой парой вершин
3. Получите их длины (что-то похожее на то, что path.length.hist делает функция, но для результатов 2-го шага).

Это разные проблемы, но я подумал, что вопрос достаточно общий, чтобы держать их в одном потоке. Как я уже говорил, мне нравится igraph , но другие решения R тоже приветствуются!

Приветствия,

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

 require(igraph)
edges <- graph.formula(A -  B,
                     A -  C,
                     B -  C,
                     C -  D,
                     B -  D,
                     D -  E)

indeg <- degree(edges, mode="in")
outdeg <- degree(edges, mode="out")
START <- names(indeg)[indeg==0] 
END <- names(outdeg)[outdeg==0]

listPaths <- NULL
for (start in START) {
  for (end in END) {
    listPaths <- append(listPaths, all_simple_paths(edges, from=start, to=end))
  }
}

lengthPaths <- sapply(listPaths, length)