Извлечение веток из орграфа в MATLAB

Question

Я ищу способ извлечь ветви орграфа в MATLAB. Точно, если у меня есть сеть (my_digraph), подобная следующей:

Когда я ввожу my_digraph.plot, я получаю это:

Теперь я мог бы вручную записать ветви, посмотрев на картинку, например, [1, 2], [1, 3], [1, 6, 7] и т. Д. Однако в больших сетях это уже невозможно. С помощью какой функции я могу извлечь эту информацию из картинки, чтобы она выглядела как массив, содержащий эти векторы?

Примечание: я знаю, что рисунки выше не являются орграфами, поскольку у них нет направления. Тем не менее, они все еще показывают принцип.

Answer 1

Как я понимаю ваш вопрос, вы хотите, чтобы все кратчайшие пути от узла 1 до всех "конечных узлов" (узлов степени 1).

Давайте сначала определим граф:

edges = [
  [1,2],
  [1,3],
  [1,4],
  [1,5],
  [1,6],
  [6,7],
  [6,8],
  [6,9],
  [6,10],
  [6,11]]

G = graph(edges(:,1),edges(:,2))

Теперь давайте определим наш начальный узел (1) и найдем все конечные узлы, которые мы получим как индексы всех узлов степени 1 (т.е. узлы, соединенные только через одно ребро)

node_start = 1
nodes_degree = degree(G)
nodes_end = find(nodes_degree == 1)

Теперь мы перебираем все конечные узлы и для каждого находим кратчайший путь от начального узла к соответствующему конечному узлу. Мы сохраняем полученные массивы узлов по кратчайшему пути в ячейке paths.

paths = {}
for path_idx = 1:numel(nodes_end)
  node_end = nodes_end(path_idx)
  path = shortestpath(G,node_start,node_end)
  paths{path_idx} = path
end

Наша ячейка paths теперь содержит все кратчайшие пути. Например:

disp(paths{5})

>>>  1   6   7

Или для отображения всех

cellfun(@(path) disp(path), paths) 

>>>  1     2

     1     3

     1     4

     1     5

     1     6     7

     1     6     8

     1     6     9

     1     6    10

     1     6    11