Prolog: Debugging Recursive Source Removal Algorithm

Question

I am currently working on implementing a source-removal topological sorting algorithm for a directed graph. Basically the algorithm goes like this:

Find a node in a graph with no incoming edges
Remove that node and all edges coming out from it and write its value down
Repeat 1 and 2 until you eliminate all nodes

So, for example, the graph

would have a topological sort of a,e,b,f,c,g,d,h. (Note: topological sorts aren't unique and thus there can be a different topological sort as well)

I am currently working on a Prolog implementation of this with the graph being represented in list form as follows:

[ [a,[b,e,f]], [b,[f,g]], [c,[g,d]], [d,[h]], [e,[f]], [f,[]], [g,[h]], [h,[]] ]

Where the [a, [b,e,f] ] term for example represents the edges going from a to b, e, and f respectively, and the [b, [f,g] ] term represents the edges going from b to f and g. In other words, the first item in the array "tuple" is the "from" node and the following array contains the destinations of edges coming from the "from" node. I am also operating under assumption that there is one unique name for each vertex and thus when I find it, I can delete it without worrying about any potential duplicates.

I wrote the following code

    % depends_on shows that D is adjacent to A, i.e. I travel from A to D on the graph
% returns true if A ----> D
depends_on(G,A,D) :- member([A,Ns],G), member(D,Ns).

% doesnt_depend_on shows that node D doesnt have paths leading to it 
doesnt_depend_on(G, D) :- \+ depends_on(G, _, D).

% removes node from a graph with the given value
remove_graph_node([ [D,_] | T], D, T). % base case -- FOUND IT return the tail only since we already popped it
remove_graph_node([ [H,Ns] | T], D, R) :- \+ H=D,remove_graph_node( T, D, TailReturn), append([[H,Ns]], TailReturn, R).

%----------------------------------------------------
source_removal([], []]). % Second parameter is empty list due to risk of a cycle
source_removal(G,Toposort):-member([D,_], G), 
                            doesnt_depend_on(G,D), 
                            remove_graph_node(G,D,SubG),
                            source_removal(SubG, SubTopoSort),
                            append([D], SubTopoSort, AppendResult),
                            Toposort is AppendResult.

And I tested the depends_on, doesnt_depend_on, and remove_graph_node by hand using the graph [ [a,[b,e,f]], [b,[f,g]], [c,[g,d]], [d,[h]], [e,[f]], [f,[]], [g,[h]], [h,[]] ] and manually changing the parameter variables (especially when it comes to node names like a, b, c and etc). I can vouch after extensive testing that they work.

However, my issue is debugging the source_removal command. In it, I repeatedly remove a node with no directed edge pointing towards it along with its outgoing edges and then try to add the node's name to the Toposort list I am building.

At the end of the function's running, I expect to get an array of output like [a,e,b,f,c,g,d,h] for its Toposort parameter. Instead, I got

?- source_removal([ [a,[b,e,f]], [b,[f,g]], [c,[g,d]], [d,[h]], [e,[f]], [f,[]], [g,[h]], [h,[]] ], Result).
false.

I got false as an output instead of the list I am trying to build.

I have spent hours trying to debug the source_removal function but failed to come up with anything. I would greatly appreciate it if anyone would be willing to take a look at this with a different pair of eyes and help me figure out what the issue in the source_removal function is. I would greatly appreciate it.

Thanks for the time spent reading this post and in advance.

Jens Classen Jens Classen · Accepted Answer · 2019-10-10T21:29:35

The first clause for source_removal/2 contained a typo (one superfluous closing square bracket).

The last line for the second clause in your code says Toposort is AppendResult. Note that is is used in Prolog to denote the evaluation of an arithmetic expression, e.g., X is 3+4 yields X = 7 (instead of just unifying variable X with the term 3+4). When I change that line to use = (assignment, more precisely unification) instead of is (arithmetic evaluation) like so

source_removal([], []). % Second parameter is empty list due to risk of a cycle
source_removal(G,Toposort):-member([D,_], G), 
                            doesnt_depend_on(G,D), 
                            remove_graph_node(G,D,SubG),
                            source_removal(SubG, SubTopoSort),
                            append([D], SubTopoSort, AppendResult),
                            Toposort = AppendResult.

I get the following result:

?- source_removal([ [a,[b,e,f]], [b,[f,g]], [c,[g,d]], [d,[h]], [e,[f]], [f,[]], [g,[h]], [h,[]] ], Result).
Result = [a, b, c, d, e, f, g, h] ;
Result = [a, b, c, d, e, g, f, h] ;
Result = [a, b, c, d, e, g, h, f] ;
Result = [a, b, c, d, g, e, f, h] ;
Result = [a, b, c, d, g, e, h, f] ;
Result = [a, b, c, d, g, h, e, f] ;
Result = [a, b, c, e, d, f, g, h] ;
Result = [a, b, c, e, d, g, f, h] ;
Result = [a, b, c, e, d, g, h, f] ;
Result = [a, b, c, e, f, d, g, h] ;
Result = [a, b, c, e, f, g, d, h] ;
...
Result = [c, d, a, e, b, g, h, f] ;
false.

(Shortened, it shows 140 solutions in total.)

Edit: I didn't check all the solutions, but among the ones it finds is the one you gave in your example ([a,e,b,f,c,g,d,h]), and they look plausible in the sense that each either starts with a or with c.

Prolog: Debugging Recursive Source Removal Algorithm

1 Answers