Preiskovanje grafov v prologu

Članek govori o preiskovanju usmerjenih grafov v programskem jeziku Prolog.

Povezave lahko zakodiramo z dejstvi:

p(a,b).
p(a,c).
p(b,c).
p(b,e).
p(c,d).
p(d,b).

Ali z naprednejšim zapisom:

graf([a/b,a/c, ... ]).

Povezava

Ali obstaja pot med 2 elementoma?

?- povezava(a,d).
yes

?- povezava(c,e).
no

povezana(Vozel1,Vozel2) :-
  povezava(Vozel1,Vozel2).
povezana(Vozel1,Vozel2) :-
  povezana(Vozel1,Vmesni),
  povezana(Vmesni,Vozel2).

Ciklanje

Če obstajajo poti po katerih lahko pridemo nazaj na naše začetno izhodišče se program lahko zacikla. To je resen problem pri rekurziji.

Temu se lahko izognemo tako, da preverjamo, če smo se zaciklali, s sledjo. Sled je seznam vozlišč v katerih smo že bili.

povezana_brez_ciklanja(Vozel1,Vozel2) :-
  isci_pot(Vozel1,Vozel2,[]).

isci_pot(Vozel1,Vozel2,_) :-
  povezava(Vozel1,Vozel2).
isci_pot(Vozel1,Vozel2,Sled):-
  povezava(Vozel1,Vmesni),
  ni_element(Vmesni,Sled),
  isci_pot(Vmesni,Vozel2,[Vozel1,Sled]).