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

Question

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

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

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

注意：我知道上面的图片不是有向图，因为它们没有方向。但是，它们仍然显示了原理。

标签： matlabplotdigraphs

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