Определение пути/тропы/прогулки

Многие предикаты определяют какой-то ациклический путь, построенный из ребер, определенных через двоичное отношение, совершенно аналогично определяющему транзитивное закрытие. Таким образом, генерируется общее определение.

Обратите внимание, что понятия, определенные в теории графов, не всегда соответствуют ожидаемому. В частности, нас не интересуют имена краев.

Хуже того, теория графов немного изменилась, введя понятие 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).

Ответы

Ответ 1

Я хочу сосредоточиться на названии предиката.

  • В отличие от maplist/2, порядок аргументов здесь не имеет первостепенного значения.

  • Имя предиката должно четко указывать значение соответствующих аргументов.

Пока мне нравится path_from_to_edges лучше, но у него есть свои плюсы и минусы.

path_from_to_edges(Path,From,To,Edges_2) :-
    path(Edges_2,Path,From,To).

Пусть выделите его:

  • pro: path - существительное, оно не может быть неправильно прочитано глаголом. Для меня подразумевается список вершин.

  • pro: from обозначает вершину, а также to.

  • con: edges несколько расплывчато, но использование lambdas здесь является самым универсальным выбором.

  • con: Согласно Wikipedia, путь - это след, в котором все вершины (за исключением, возможно, первого и последнего ) различны. Поэтому в описании должно быть разъяснено.

Использование lambdas для списков соседних вершин Ess:

?- Ess  = [a-[b],b-[c,a]], 
   From = a,
   path_from_to_edges(Path,From,To,\X^Y^(member(X-X_neibs,Ess),member(Y,X_neibs))).
Ess = [a-[b],b-[c,a]], From = a, To = a, Path = [a]     ;
Ess = [a-[b],b-[c,a]], From = a, To = b, Path = [a,b]   ;
Ess = [a-[b],b-[c,a]], From = a, To = c, Path = [a,b,c] ;
false.

Редактировать 2015-06-02

Еще один выстрел в лучшее название! Это больше зависит от стороны maplist/2...

graph_path_from_to(P_2,Path,From,To) :-
   path(P_2,Path,From,To).

Здесь graph, конечно, является существительным, а не глаголом.

Что касается значения "путь": пути определенно должны допускать From=To и не исключать этого по умолчанию (с попарно-временными неравенствами). Это легко исключить с помощью дополнительной цели dif(From,To), но не наоборот.

Ответ 2

Как насчет определения path/4 как это?

path(R_2, Xs, A,Z) :-                   % A path `Xs` from `A` to `Z` is ...
   walk(R_2, Xs, A,Z),                  % ... a walk `Xs` from `A` to `Z` ...
   all_dif(Xs).                         % ... with no duplicates in `Xs`.

Чтобы помочь универсальному завершению, мы заменяем две цели в соединении выше...

path(R_2, Xs, A,Z) :-
   all_dif(Xs),                         % enforce disequality ASAP
   walk(R_2, Xs, A,Z).

... и используйте следующую ленивую реализацию all_dif/1:

<Предварительно > all_dif (Xs): -% принудительно использовать неравенство с парой термов  freeze (Xs, all_dif_aux (Xs, [])). % (может быть отложено) all_dif_aux ([], _). all_dif_aux ([E | Es], Vs): -  maplist (dif (E), Vs),% никогда не задерживается  freeze (Es, all_dif_aux (Es, [E | Vs])). % (может быть отложено)

walk/4 определяется как path/4 и path/5, заданный OP:

:- meta_predicate walk(2, ?, ?, ?).
walk(R_2, [X0|Xs], X0,X) :-
   walk_from_to_step(Xs, X0,X, R_2).

:- meta_predicate walk_from_to_step(?, ?, ?, 2).
walk_from_to_step([], X,X, _).
walk_from_to_step([X1|Xs], X0,X, R_2) :-
   call(R_2, X0,X1),
   walk_from_to_step(Xs, X1,X, R_2).

IMO выше path/4 проще и доступнее, особенно для новичков. Согласитесь?

Ответ 3

Я не вижу причины определять в пути /4 аргументы "start node" и "end node". Кажется, что достаточно простого пути /2 с правилом и списком узлов.

Если пользователю нужен список, начинающийся с некоторого node (например, 'a'), он может запросить оператор как: path (some_rule, ['a' | Q]).

Пользователь может, например, запросить путь, длина которого равна 10: length (P, 10), path (some_rule, P).

* Добавление 1 *

Некоторые цели полезности могут быть легко добавлены, но они не являются основным предметом. Например, путь /3 с началом node равен:

path( some_rule, [start|Q], start ) :- 
  path ( some_rule, [start|Q ] ).

* Добавление 2 *

Добавление последнего node в качестве аргумента может дать ложную идею о том, что этот аргумент управляет алгоритмом, но это не так. Предположим, например:

n(a, b).
n(a, c).
n(a, d).

и выполнение алгоритма трассировки для запроса:

[trace]  ?- path( n, P, X, d ).
   Call: (6) path(n, _G1025, _G1026, d) ? creep
   Call: (7) path(n, _G1107, _G1026, d, [_G1026]) ? creep
   Exit: (7) path(n, [], d, d, [d]) ? creep
   Exit: (6) path(n, [d], d, d) ? creep
P = [d],
X = d ;
   Redo: (7) path(n, _G1107, _G1026, d, [_G1026]) ? creep
   Call: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, b) ? creep

   Call: (8) non_member(b, [a]) ? creep
   Call: (9) dif:dif(b, a) ? creep
   Exit: (9) dif:dif(b, a) ? creep
   Call: (9) non_member(b, []) ? creep
   Exit: (9) non_member(b, []) ? creep
   Exit: (8) non_member(b, [a]) ? creep
   Call: (8) path(n, _G1113, b, d, [b, a]) ? creep
   Call: (9) n(b, _G1118) ? creep
   Fail: (9) n(b, _G1118) ? creep
   Fail: (8) path(n, _G1113, b, d, [b, a]) ? creep
   Redo: (9) non_member(b, []) ? creep
   Fail: (9) non_member(b, []) ? creep
   Fail: (8) non_member(b, [a]) ? creep
   Redo: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, c) ? creep

   Call: (8) non_member(c, [a]) ? creep
   Call: (9) dif:dif(c, a) ? creep
   Exit: (9) dif:dif(c, a) ? creep
   Call: (9) non_member(c, []) ? creep
   Exit: (9) non_member(c, []) ? creep
   Exit: (8) non_member(c, [a]) ? creep
   Call: (8) path(n, _G1113, c, d, [c, a]) ? creep
   Call: (9) n(c, _G1118) ? creep
   Fail: (9) n(c, _G1118) ? creep
   Fail: (8) path(n, _G1113, c, d, [c, a]) ? creep
   Redo: (9) non_member(c, []) ? creep
   Fail: (9) non_member(c, []) ? creep
   Fail: (8) non_member(c, [a]) ? creep
   Redo: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, d) ? creep

   Call: (8) non_member(d, [a]) ? creep
   Call: (9) dif:dif(d, a) ? creep
   Exit: (9) dif:dif(d, a) ? creep
   Call: (9) non_member(d, []) ? creep
   Exit: (9) non_member(d, []) ? creep
   Exit: (8) non_member(d, [a]) ? creep
   Call: (8) path(n, _G1113, d, d, [d, a]) ? creep
   Exit: (8) path(n, [], d, d, [d, a]) ? creep
   Exit: (7) path(n, [d], a, d, [a]) ? creep
   Exit: (6) path(n, [a, d], a, d) ? creep
P = [a, d],
X = a .

как вы можете видеть, в этом случае алгоритм не может использовать команду перебора. По этой причине, если алгоритм не улучшен, я предлагаю не добавлять "end node" в качестве аргумента "path".