Calculating all paths from a given node in a digraph

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]

[Can Chen]

Hi Niels, I work at MathWorks on graphs. If you have a few minutes, I would very much appreciate hearing more about your workflow using paths. Would you please contact me directly? Thanks.

[Walter Roberson]

See https://www.mathworks.com/matlabcentral/answers/171277-how-can-i-get-all-paths-between-two-nodes#answer_165813

https://www.mathworks.com/matlabcentral/answers/470708-matlab-built-in-function-to-retrieve-all-possible-paths-between-two-nodes#comment_722515

Answer 1

[Guillaume]

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

[Niels de Vries]

So far its working perfectly! Will be testing it more thoroughly, again thanks a lot !

[Evangelia Vayena]

What if the graph is not acyclic? Thank you!

[Guillaume]

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.

[navanit dubey]

https://in.mathworks.com/matlabcentral/answers/650538-how-to-find-kshortest-path-or-use-dijkstra-algorithm-for-12-plot-points?s_tid=srchtitle

please help me sir

Answer 2

[Walter Roberson]

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.

[Niels de Vries]

Indeed the 'in degree' for this example happens to be 1, but this is not the case, i should have provided a better example. I will take a look in the file exchange and hopefully find something there, thanks.

[Walter Roberson]

The task is more difficult if loops are possible.

[Niels de Vries]

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

Answer 3

[Pierre Harouimi]

R2021a: allpaths