Path search in a tree from generic start and end nodes using prolog

Question

I am searching for paths using some generic definitions. For example, when I search for A to B, I actually want to find paths like A to B, A_1 to B_2, A to B_1, or A_5 to B.

The middle nodes traversed may or may not be have a suffix like _N based on the connections in the tree. My prolog statement is like below.

path(A,B,Path) :-
  travel(A,B,[A],Q),
  reverse(Q,Path).

travel(A,B,P,[B|P]) :-
  arc(A,B).
travel(A,B,Visited,Path) :-
  arc(A,C),
  C \== B,
  \+member(C,Visited),
  travel(C,B,[C|Visited],Path).

Using this prolog code, I can find some paths but can not find others. For example, for the generic search criteria A -->15

Paths like (A, 1, 4, 7, 15) are ok,

Paths like (A, 1_1, 4_3, 7, 15) are also ok

Paths like

(A_1, X, X, X, 15)

(A, X, X, X, 15_2),

(A_3, X, X, X, 15_1)

are not ok

Note: X is a placeholder for any node either with the underscore or not.

Can you please help me to find out the problem.

Many thanks, Ferda

Consider [this](https://stackoverflow.com/q/30328433/772868). — false, Jun 18 '21 at 15:57
Which part do you recommend? That problem looks different and there are lots of code suggestions.. — Ferda-Ozdemir-Sonmez, Jun 18 '21 at 17:22
`path(arc, Path, A, B)` implements your task. All what is listed there as "implementation" is needed. — false, Jun 18 '21 at 18:13

score 2 · Answer 1 · answered Jun 18 '21 at 17:40

2

I would extend the arc/2 predicate, or better, would introduce a service arc_ext/2, and would change travel/4 accordingly:

travel(A,B,P,[B|P]) :- arc_ext(A,B).
travel(A,B,Visited,Path) :- arc_ext(A,C),...

% TBD: optimize, when the logic has been tested
arc_ext(A,B) :-
  arc(X,Y),
  sub_atom(X,0,_,_,A), % X starts with A
  sub_atom(Y,0,_,_,B).

answered Jun 18 '21 at 17:40

CapelliC

59,646
5
47
90

Hi @CapelliC, Your answer (sub_atom parts) helped me find the solution. Many thanks.. – Ferda-Ozdemir-Sonmez Jun 20 '21 at 07:12

Ferda-Ozdemir-Sonmez · Accepted Answer · 2021-06-21T17:18:01.023

0

adding this line solved the problem.

path_generic(A,B,Path) :- path(X,Y,Path),sub_atom(X,0,_,_,A), sub_atom(Y,0,_,_,B).

edited Jun 21 '21 at 17:18

answered Jun 20 '21 at 07:13

Ferda-Ozdemir-Sonmez

674
2
13
38

Path search in a tree from generic start and end nodes using prolog

2 Answers2