Пролог: отладка алгоритма рекурсивного удаления источника - PullRequest
Новая
       23

Пролог: отладка алгоритма рекурсивного удаления источника

2 голосов
/ 09 октября 2019

В настоящее время я работаю над реализацией алгоритма топологической сортировки с удалением источника для ориентированного графа. В основном алгоритм выглядит следующим образом:

  1. Найти узел в графе без входящих ребер
  2. Удалить этот узел и все ребра, выходящие из него, и записать его значение
  3. Повторяйте 1 и 2, пока не удалите все узлы

Так, например, график

Sample graph

будетимеют топологический вид a, e, b, f, c, g, d, h . (Примечание: топологические сортировки не уникальны, и, следовательно, может быть и другая топологическая сортировка)

В настоящее время я работаю над реализацией этого в Прологе с графом, представленным в виде списка следующим образом:

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

Где [a, [b, e,f]] термин, например, представляет ребра, идущие от a до b , e и f соответственно, и [b, [f, g]] термин представляет ребра, идущие от b до f и g . Другими словами, первый элемент в массиве «кортеж» - это узел «от», а следующий массив содержит места назначения ребер, идущих от узла «от». Я также работаю в предположении, что для каждой вершины есть одно уникальное имя, и поэтому, когда я его нахожу, я могу удалить его, не беспокоясь о возможных дубликатах.

Я написал следующий код 

    % 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.

И я протестировал depends_on, doesnt_depend_on и remove_graph_node вручную, используя график [ [a,[b,e,f]], [b,[f,g]], [c,[g,d]], [d,[h]], [e,[f]], [f,[]], [g,[h]], [h,[]] ] и вручную изменяя переменные параметров (особенно когда речь идет об именах узлов, таких как a , b , c и т. Д.). После тщательного тестирования я могу подтвердить, что они работают.

Однако моя проблема заключается в отладке команды source_removal. В нем я неоднократно удаляю узел без направленного ребра, указывающего на него вместе с его исходящими ребрами, и затем пытаюсь добавить имя узла в список Toposort, который я строю.

В конце работы функции я ожидаю получить массив выходных данных, например [a,e,b,f,c,g,d,h] для параметра Toposort. Вместо этого я получил 

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

Я получил false в качестве вывода вместо списка, который я пытаюсь построить.

Я потратил часы, пытаясь отладить source_removal функция, но ничего не удалось придумать. Я был бы очень признателен, если бы кто-нибудь захотел взглянуть на это другими глазами и помочь мне выяснить, в чем заключается проблема с функцией source_removal. Я был бы очень признателен.

Спасибо за потраченное время на чтение этого поста и заранее.

1 Ответ

1 голос
/ 11 октября 2019

В первом предложении для source_removal/2 содержится опечатка (одна лишняя закрывающая квадратная скобка).

В последней строке второго предложения в вашем коде написано Toposort is AppendResult. Обратите внимание, что is используется в Прологе для обозначения оценки арифметического выражения, например, X is 3+4 дает X = 7 (вместо простого объединения переменной X с термином 3+4). Когда я изменяю эту строку, чтобы использовать = (назначение, точнее объединение) вместо is (арифметическая оценка), например, так: 

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.

, я получаю следующий результат: 

?- 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.

(Сокращено, в общей сложности показано 140 решений.)

Редактировать : Я не проверил все решения, но среди найденных найден тот, который вы дали в своем примере. ([a,e,b,f,c,g,d,h]), и они выглядят правдоподобно в том смысле, что каждый из них начинается либо с a, либо с c.

...