Definición de un camino / sendero / caminata

Muchos predicados definen algún tipo de camino acíclico construido a partir de los bordes definidos a través de una relación binaria, bastante 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 los gráficos ha cambiado un poco, introduciendo la noción de caminar , señalando

Tradicionalmente, un camino se refería a lo que ahora se conoce como caminata abierta. Hoy en día, cuando se indica sin ninguna calificación, un camino generalmente se entiende como simple, lo que significa que no se repiten los vértices (y por lo tanto no hay bordes). (El término cadena también se ha usado 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 debe 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). 

Quiero centrarme en nombrar el predicado.

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

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

Hasta ahora, me gusta 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 necesitaría ser aclarado 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 en el lado de maplist/2

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

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

En cuanto al significado de “ruta”: las rutas definitivamente deberían permitir From=To y no excluir eso por defecto (con desigualdades de términos pairwise). Es fácil excluir esto con un objective dif(From,To) adicional, pero no al revés.

¿Qué hay de definir path/4 así?

 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 objectives en la conjunción de arriba …

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

… y utiliza la siguiente implementación diferida de all_dif/1 :

 all_dif (Xs): -% aplica desigualdad de término pairwise
    congelar (Xs, all_dif_aux (Xs, [])).  % (puede retrasarse)

 all_dif_aux ([], _).
 all_dif_aux ([E | Es], Vs): -               
    maplist (dif (E), Vs),% nunca se retrasa
    congelar (Es, all_dif_aux (Es, [E | Vs])).  % (puede retrasarse)

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

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

No veo la razón para definir en path / 4 los argumentos “start node” y “end node”. Parece que un simple camino / 2 con la regla y la lista de nodos debe ser suficiente.

Si el usuario desea una lista que comience con un nodo (por ejemplo, ‘a’), puede consultar la instrucción como: ruta (some_rule, [‘a’ | Q]).

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

* Addendum 1 *

Algunos objectives 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 ] ). 

* Adición 2 *

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

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

y ejecutar algoritmos 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 falla en la fuerza bruta. Por esta razón, si el algoritmo no mejora, sugiero que no agregue el “nodo final” como argumento de “ruta”.