How can I find all nodes that should precede node 'Node' from the information contained in a digraph G?

Dear all,

I am struggling in my mind with coding a function that solves the following problem. For a given node which is called Node, say 4, I would like to obtain all the nodes that should precede said node from the information in the digraph which is also input. See digraph in Figure 1 below. I construct the digraph as:

source = [1 1 2 3 4 5 7];
sink = [2 3 5 4 7 4 6];

G = digraph(source,sink);

Figure 1: Digraph G showing the precedence constraints on visiting the customer nodes

Any edge in the digraph G, see Figure 1, from i to j implies that node i should precede node j. A shell of the desired function (findprecNodes.m) containing information about what it is supposed to do is attached. For instance, for node 4 I would expect the output:

precNodes = [1 2 3 5]

which needs not necessarily to be sorted in ascending magnitude. I, sort of, know the logic of what the function should do but do not know how to put it in code (e.g.: whether to use a while loop or several for loops here etc.). Namely, it should find the predecessors of said node, like so:

Pred = predecessors(G,Node);

And then it should continue by finding the predecessors of Pred (and then the predecessors of the predecessors of Pred) until all predecessors do not have predecessors anymore (the results of the statement above will be an empty matrix).

This might come across as lazy but is more of a logic-understanding-issue than a coding issue, and some help would greatly be appreciated. So if any of you guys have any suggestions I would love to hear them.

Martijn

EDIT:

I appear to have found a solution:

function precNodes = findprecNodes(G,Node)

%Input: - digraph containing precedence constraint information
%       - node to be evaluated


%Output: - all nodes which should precede node 'Node'

allnoPred = 0;
Pred = predecessors(G,Node);
precNodes = Pred;

while (allnoPred ~= 1)
    noPred = 0;
    prec_Prec = [];
    for i = 1:length(Pred)
        evalNode = Pred(i);
        X = predecessors(G,evalNode);
        if (isempty(X) == 1)
            noPred = noPred+1;
            if (noPred == length(Pred))
                allnoPred = 1;
            end
        end
        prec_Prec = [prec_Prec X];
        precNodes = union(precNodes,X);
    end
    Pred = prec_Prec;
end
end

Whether it can be done more neatly and leaner I don't know.

Answer 1

[Bruno Luong]

source = [1 1 2 3 4 5 7];
sink = [2 3 5 4 7 4 6];
node = 4
p = FindprecNodes(source, sink, node)

function p = FindprecNodes(source, sink, node)
notvisit = true(size(sink));
p = fpn_engine(source, sink, node, notvisit, []);
p = sort(p);
end

function p = fpn_engine(source, sink, nodes, notvisit, p)
pp = source(ismember(sink,nodes));
pp(~notvisit(pp)) = [];
if ~isempty(pp)
    notvisit(pp) = false;
    p = fpn_engine(source, sink, pp, notvisit, [p, pp]);
end
end

[Martijn Kamphuis]

Dear Bruno,

Thank you so much for your reply. This does indeed give the desired answer, and I will definitely consider it, however, I will need to adapt it to use G as input since at this point in my algorithm source and sink are not known anymore.

Thanks again for your contribution.

[Bruno Luong]

It takes few simple commands to retrieve source and sink from graph

edges = table2array(G.Edges)
source = edges(:,1)';
sink = edges(:,2)';

Answer 2

[Steven Lord]

So you want to know "I want to get here. Where could I have come from?"

You could flip the edges and do breadth-first search or depth-first search or you could find all nodes whose distances from your target node are finite (you can get here from there.)