Calculating all paths from a given node in a digraph

10 次查看（过去 30 天）
Niels de Vries
Niels de Vries 2018-9-4
回答： Pierre Harouimi 2021-12-29
Hey all,
I am using the digraph function and trying to find all paths from a given source node, i was wondering if there already exist a object function to do this such as the shortest path object functions.
As an example:
The output i would like:
[1 2 4]
[1 2 5]
[1 2 6]
[1 3 7 9]
[1 3 7 8]

请先登录，再回答此问题。

采纳的回答

Guillaume
Guillaume 2018-9-4
I've not tested it thoroughly but I think this should work:
function paths = getpaths(g)
%return all paths from a DAG.
%the function will error in toposort if the graph is not a DAG
paths = {}; %path computed so far
endnodes = []; %current end node of each path for easier tracking
for nid = toposort(g) %iterate over all nodes
if indegree(g, nid) == 0 %node is a root, simply add it for now
paths = [paths; nid]; %#ok<AGROW>
endnodes = [endnodes; nid]; %#ok<AGROW>
end
%find successors of current node and replace all paths that end with the current node with cartesian product of paths and successors
toreplace = endnodes == nid; %all paths that need to be edited
s = successors(g, nid);
if ~isempty(s)
[p, tails] = ndgrid(paths(toreplace), s); %cartesian product
paths = [cellfun(@(p, t) [p, t], p(:), num2cell(tails(:)), 'UniformOutput', false); %append paths and successors
paths(~toreplace)];
endnodes = [tails(:); endnodes(~toreplace)];
end
end
end
  4 个评论
显示 2更早的评论
Guillaume
Guillaume 2020-4-29
If the graph has cycle, then as commented in the code, the matlab function toposort will error since it only works with DAG. You'd have to write your own algorithm for this, I'm afraid.
The first thing you'll have to answer is what the definition of 'all paths' is when there are cycles.

请先登录，再进行评论。

更多回答（2 个）

Walter Roberson
Walter Roberson 2018-9-4
Mathworks does not provide any function for that purpose. Perhaps the graph theory toolbox in the File Exchange?
Your text asks for "all paths", and your example is a digraph that happens to have "in degree" 1 for all nodes. In the special case of a digraph with "in degree" 1 for all nodes, then "all paths" becomes the same as all shortest path tree https://www.mathworks.com/help/matlab/ref/graph.shortestpathtree.html .
This routine will not work for cases where the in degree is more than 1, such as if node 3 also pointed to node 9: in that case the "shortest" path choices in the routine would prune out some of the paths.
  3 个评论
显示 1更早的评论
Niels de Vries
Niels de Vries 2018-9-4
编辑：Niels de Vries 2018-9-4
It indeed is, backtracking is needed, but i am not sure how to implement something like that in Matlab. An example digraph is added, and unfortunately couldn't find something in the file exchange

请先登录，再进行评论。

Pierre Harouimi
Pierre Harouimi 2021-12-29
R2021a: allpaths

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

产品


版本

R2017b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by