StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>building on the excellently clear code by Daniel Lyons, a breadth first search:</p> <pre class="lang-prolog prettyprint-override"><code>all_paths(Node, Graph, Paths) :- bfs(Graph, [[Node]-[]], R, []), % or dfs(...) maplist( fst, Paths, R). fst(A, A-_). % utility pair(B, A, A-B). % helpers add(LS,H,[H|LS]). % bfs(_G, [], Z, Z). % queue is empty bfs(Graph, [H|Q], [H|R], Z) :- H = Path-Seen, Path = [Node|_], findall( Next, member(r(Node, Next), Graph), NS), flatten_diff( NS, Seen, WS), % working set of nodes maplist( add(Path), WS, PS), % new paths maplist( pair([Node|Seen]), PS, QH), % new addition to the queue %% append( QH, Q, Q2), % DFS append( Q, QH, Q2), % BFS bfs(Graph, Q2, R, Z). </code></pre> <p>(not tested). <code>flatten_diff(A,B,C)</code> should flatten list of lists <code>A</code>, while removing the elements of it that appear also in list <code>B</code>, producing the list <code>C</code> as the result. </p> <hr> <p>As PeterPanter has noticed, Daniel Lyons's code needs a little tweaking, to not exclude the very last node in its resulting paths.</p> <pre class="lang-prolog prettyprint-override"><code>find(Node, Graph, [Node|Path]) :- find(Node, Graph, Path, []). find(_, _, [], _). find(Node, Graph, [AdjNode|Path], Seen) :- member(r(Node, Adjacent), Graph), member(AdjNode, Adjacent), \+ memberchk(AdjNode, Seen), find(AdjNode, Graph, Path, [Node|Seen]). </code></pre> <p>There are no empty paths produced now, and it works as expected:</p> <pre class="lang-prolog prettyprint-override"><code>11 ?- find(a,[r(a,[b,d]),r(b,[a,c,e]),r(c,[b]), r(d,[a,g]), r(e,[b,d,f]),r(f,[e,g]),r(g,[f])], Path). Path = [a] ; Path = [a, b] ; Path = [a, b, c] ; Path = [a, b, e] ; Path = [a, b, e, d] ; Path = [a, b, e, d, g] ; Path = [a, b, e, d, g, f] ; Path = [a, b, e, f] ; Path = [a, b, e, f, g] ; Path = [a, d] ; Path = [a, d, g] ; Path = [a, d, g, f] ; Path = [a, d, g, f, e] ; Path = [a, d, g, f, e, b] ; Path = [a, d, g, f, e, b, c] ; false. </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload