Find all possible paths w/o loops in Graph in Prolog -

i got homework assignment logic course, more or less don't have clue how solve it... query like

  ?- find(a,[r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),r(d,[a,e]),   r(e,[b,d,f]),r(f,[e,g]),r(g,[f])],path). 

prolog should return possible paths in given graph. terms r(x,list) define graph, meaning nodes in list can reached node x. in case, output be:

path = [a,b,c] ; path = [a,b,e,d] ; path = [a,b,e,f,g] ; path = [a,d,e,b,c] ; path = [a,d,e,f,g] ; false. 

although hang of numerous solutions here on se , on web in general similar problems, i'm somehow dumb figure out how work definition of graph in assignment.

i figure find(start,...) should called recursively members of list in r(start,list), total newbie prolog(we did standard family tree stuff...) don't know how that.

any appreciated. i'm aware of fact don't have start with, spent half night trying figure out , don't have clue.

/edit:

for starters, think i'll need kind of base case abort recursion. think should either

find([],_,_). 

because guess last recursive call wouldn't have start with, or

find(_,[],_). 

assuming list of terms defining adjacent nodes should empty when program finished processing it.

now actual call. like

find(start,[r(start,[adjacent|restadj])|rest],path):-            find(???). 

my problems here following:

-how make program use members of list in r(...) term next start?

-how check if node has been "visited"/ how can remove node specific list in r

-how put found nodes path list? append? or execute recursive call [path|start]?

as see, it's not much. suggestive questions nice, since prolog seems quite interesting , therefore fun learn...

---

after spending time neat pdt-eclipse trace tool, think understood program doing. dont't @ point why last node gets lost. after backtracking fails, example because r(c,[b]) next found term , memberchk(b,[b]) fails because of negation(that's thing + does) , no other term r(c,x) can found, starts on looking other possibilities go node b, has adjacent nodes left in r(b,[...]). why program forget put node c path list? there possibility kind of if-then-else in case

 member(r(node, adjacent), graph), member(adjnode, adjacent), \+ memberchk(adjnode, seen), 

fails, still append last node path?

i suspect what's tripping here instead of getting data out of database, you're having find within explicit data structure. first crack @ might this:

find(_, _, []). find(node, graph, [node|path]) :-     member(r(node,adjacent), graph),     member(adjnode, adjacent),     find(adjnode, graph, path). 

see how i'm using member/2 find data within graph. solution isn't correct though, because loops. improvement might this:

find(node, graph, path) :- find(node, graph, path, []).  find(_, _, [], _). find(node, graph, [node|path], seen) :-     member(r(node, adjacent), graph),     member(adjnode, adjacent),     \+ memberchk(adjnode, seen),     find(adjnode, graph, path, [node|seen]). 

this 1 same above version except has "seen" list track has been. still doesn't produce output want, think enough on right track.

edit in response edit,

for starters, think i'll need kind of base case abort recursion.

yes. chose first case because don't think can safely "consume" graph during traversal. suppose use select/3 in lieu of member/2 , pass graph-without-this-node onward. might interesting thing try (suggestion!).

• how make program use members of list in r(...) term next start?

as demonstrated, use member/2 retrieve things graph. it's funny, because used exact word predicate need. :)

• how check if node has been "visited"/ how can remove node specific list in r

as demonstrated in second set of code, have parameter auxiliary predicate, , use memberchk/3 or member/3.

• how put found nodes path list? append? or execute recursive call [path|start]?

i went recursive call. append/3 more expensive.

edit: using findall/3 per will's comment, can find paths @ once:

all_paths(from, graph, paths) :- findall(path, find(from, graph, path), paths). 

you can invoke so:

?- all_paths(a, [r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),r(d,[a,e]),                  r(e,[b,d,f]),r(f,[e,g]),r(g,[f])], allpaths). 

i haven't tested should work.