在 MATLAB 中从有向图中提取分支

Question

我正在寻找一种在 MATLAB 中提取有向图分支的方法。准确地说，如果我有一个类似于以下的网络（my_digraph）：

当我输入 my_digraph.plot 时，我收到了这个：

我现在可以通过查看图片手动记下分支，例如[1, 2]、[1, 3]、[1, 6, 7] 等。但是，在更大的网络中，这不再是可能的。我可以使用哪个函数从图片中提取此信息，以便它给我类似包含这些向量的数组？

注意：我知道上面的图片不是有向图，因为它们没有方向。不过，他们还是说明了原理。

Answer 1

据我了解你的问题，你想要从节点 1 到所有 "end-nodes"（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

在 MATLAB 中从有向图中提取分支

Extract branches from digraph in MATLAB

matlab

plot

digraphs