Многие предикаты определяют какой-то ациклический путь, построенный из ребер, определенных через двоичное отношение, совершенно аналогично определяющему транзитивное закрытие. Таким образом, генерируется общее определение.
Обратите внимание, что понятия, определенные в теории графов, не всегда соответствуют ожидаемому. В частности, нас не интересуют имена краев.
Хуже того, теория графов немного изменилась, введя понятие walk, отметив
Традиционно путь относится к тому, что сейчас обычно называют открытым ходом. В настоящее время, когда заявлено без какой-либо квалификации, путь обычно понимается простым, что означает, что никакие вершины (и, следовательно, никакие ребра) не повторяются. (Термин цепочка также используется для обозначения ходьбы, в котором все вершины и ребра различны.)
Итак, мой вопрос: как назвать и определить эту функциональность?
То, что я сделал до сих пор, это определить:
path(Rel_2, Path, X0,X)
Первый аргумент должен быть продолжением отношения. Затем приходит либо Path, либо пара вершин.
Пример использования
n(a, b).
n(b, c).
n(b, a).
?- path(n,Xs, a,X).
Xs = [a], X = a ;
Xs = [a, b], X = b ;
Xs = [a, b, c], X = c ;
false.
Реализация
:- meta_predicate path(2,?,?,?).
:- meta_predicate path(2,?,?,?,+).
path(R_2, [X0|Ys], X0,X) :-
path(R_2, Ys, X0,X, [X0]).
path(_R_2, [], X,X, _).
path(R_2, [X1|Ys], X0,X, Xs) :-
call(R_2, X0,X1),
non_member(X1, Xs),
path(R_2, Ys, X1,X, [X1|Xs]).
non_member(_E, []).
non_member(E, [X|Xs]) :-
dif(E,X),
non_member(E, Xs).
