graph - Definición de un camino/sendero/caminata

prolog transitive-closure

Question

Muchos predicados definen algún tipo de camino acíclico construido a partir de bordes definidos a través de una relación binaria, de manera muy similar a la definición del cierre transitivo . Por lo tanto, se requiere una definición genérica.

Tenga en cuenta que las nociones definidas en la teoría de grafos no coinciden fácilmente con lo que comúnmente se espera. En particular, no estamos interesados ​​en los nombres de los bordes.

Peor aún, también la teoría de gráficos ha cambiado un poco, introduciendo la noción de walk , observando

Tradicionalmente, un camino referido a lo que ahora se conoce generalmente como un paseo abierto. Hoy en día, cuando se establece sin ninguna calificación, generalmente se entiende que una ruta es simple, lo que significa que no se repiten vértices (y, por lo tanto, no hay bordes). (El término cadena también se ha utilizado para referirse a una caminata en la que todos los vértices y bordes son distintos).

Entonces mi pregunta es: ¿Cómo nombrar y definir esta funcionalidad?

Lo que he hecho hasta ahora es definir:

path(Rel_2, Path, X0,X)

El primer argumento tiene que ser la continuación de la relación. Luego viene el Path o el par de vértices.

Ejemplo de uso

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.

Implementación

:- 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).

Answer 1

¿Qué tal definir path/4 como esta?

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

Para ayudar a la terminación universal, intercambiamos los dos objetivos en la conjunción anterior ...

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

... y use la siguiente implementación diferida de all_dif/1 :

all_dif(Xs) :- % enforce pairwise term inequality freeze(Xs, all_dif_aux(Xs,[])). % (may be delayed) all_dif_aux([], _). all_dif_aux([E|Es], Vs) :- maplist/2(dif(E), Vs), % is never delayed freeze(Es, all_dif_aux(Es,[E|Vs])). % (may be delayed)

walk/4 se define como path/4 y path/5 dado por el 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).

La path/4 anterior de IMO path/4 es más simple y más accesible, especialmente para los principiantes. ¿Estarías de acuerdo?

Answer 2

No veo la razón para definir en la ruta / 4 los argumentos "nodo inicial" y "nodo final". Parece que una simple ruta / 2 con la regla y la lista de nodos debe ser suficiente.

Si el usuario desea una lista que comience con algún nodo (por ejemplo, ''a''), puede consultar la declaración como: ruta (some_rule, [''a'' | Q]).

Un usuario podría, por ejemplo, solicitar una ruta que tenga una longitud de 10 en la forma: longitud (P, 10), ruta (some_rule, P).

* Anexo 1 *

Algunos objetivos de utilidad se pueden agregar fácilmente, pero no son el tema principal. Ejemplo, ruta / 3 con nodo de inicio es:

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

* Anexo 2 *

La adición del último nodo como argumento podría dar la falsa idea de que este argumento impulsa el algoritmo, pero no lo hace. Supongamos por ejemplo:

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

y la ejecución del algoritmo de rastreo para la consulta:

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

Como puede ver, en este caso el algoritmo no logra la fuerza bruta. Por esta razón, si el algoritmo no mejora, sugiero que no agregue "nodo final" como argumento de "ruta".

Answer 3

Quiero centrarme en nombrar el predicado.

• A diferencia de maplist/2 , el orden de los argumentos no es de importancia primordial aquí.

• El nombre del predicado debe aclarar el significado de los argumentos respectivos.

Hasta ahora, me gusta más path_from_to_edges , pero también tiene sus pros y sus contras.

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

Vamos a separarlo:

• pro: path es un sustantivo, no se puede leer mal un verbo. Para mí, una lista de vértices está implícita.

• pro: from representa un vértice, y también lo hace to .

• con: edges es algo vago, pero usar lambdas aquí es la opción más versátil.

• con: Según Wikipedia , un camino es un camino en el que todos los vértices ( excepto posiblemente el primero y el último ) son distintos. Entonces eso debería aclararse en la descripción.

Usando lambdas para una lista de vértices vecinos 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.

Editar 2015-06-02

¡Otra oportunidad para nombrar mejor! Esto se inclina más al lado de maplist/2 ...

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

Aquí, graph , por supuesto, es un sustantivo, no un verbo.

Con respecto al significado de "ruta": las rutas definitivamente deberían permitir From=To y no excluir eso por defecto (con desigualdades de términos por pares). Es fácil excluir esto con un objetivo adicional dif(From,To) , pero no al revés.