Stromy, grafy
Stromy: hledáni prvku in(X,T)
Predikát in(X,T) uspěje, pokud se prvek X nachází ve stromu T. Prvek X se nachází ve stromě T, jestliže
■ Xje listem stromu T, jinak leaf(X)
■ Xje kořen stromu T, jinak tree(i_eft,x,Right)
■ Xje menší než kořen stromu T, pak se nachází v levém podstromu T, jinak
■ X se nachází v pravém podstromu T
in(X, leaf(X)) :- !.
in(X, tree(_,X,_)) :- !.
in(X, tree(Left, Root, Right) ) :-
X<Root, !,
in(X,l_eft) . in(X, tree(Left, Root, Right) ) :-
in(X.Right) .
Hana Rudová, Logické programování 1,13. května 2011
Stromy, grafy
Stromy
Příklad:
Uzly stromu Tree jsou reprezentovány termy
■ tree(Left,Value,Right): Left a Right jsou opět stromy, Value je ohodnocení uzlu
■ leaf(Value): Value je ohodnoceni uzlu
6
/ \ / \ / \
2 8 / \ /
14 7
/ \
3 5
tree(treeOeaf (1) , 2, treeQeaf (3) ,4, leaf (5)) ), 6, treeQeaf (7) , 8, []) )
Hana Rudová, Logické programování 1,13. května 2011 2 Stromy, grafy
Stromy: přidávání add(T,X,TWithX)
Prvek X přidej do stromu T jednou z následujících možností:
■ pokud T = [], pak je nový strom leaf(X)
■ pokud T=leaf(V) a X>V, pak vznikne nový strom s kořenem V, vpravo má leaf(X) (vlevo je []) pokud T=leaf(V) a X<V, pak vznikne nový strom s kořenem V, vlevo má leaf(X) (vpravo je [])
■ pokud T=tree(L,V,R) a X>V, pak v novém stromě L ponechej a X přidej doprava (rekurzivně) pokud T=tree(L,V,R) a X<V, pak v novém stromě R ponechej a X přidej doleva (rekurzivně) add([],X,leaf(X)) :- !.
addOeaf(V), X, tree( [] , V, leaf (X) ) :- X>V, !. addOeaf(V), X, treeQeaf (X) ,V, []) ) :- !. X<V, add(tree(L,V,R), X, tree(L,V,Rl)) :- X>V,  !, add(R,X,Rl). add(tree(L,V,R), X, tree(Ll,V,R)) :- X<V, add(L,X,LI).
Hana Rudová, Logické programování 1,13. května 2011
Stromy, grafy
Procházení stromů
Napište predikát traverse(Tree, List), který projde traversálně strom Tree. Seznam List pak obsahuje všechny prvky tohoto stromu.
Pořadí preorder: nejprve uzel, pak levý podstrom, nakonec pravý podstrom
Procházení stromů
?- traverse(tree(treeOeaf (1) , 2 , treeOeaf (3) ,4,leaf(5))) ,6, tree(]eaf(7) ,8,leaf(9))) , [6,2,1,4, 3 , 5 ,8,7,9]) .
(preorder)
travérse(T,Pře):- t_pre(T,Pře,[]).
t_pre([],S,S). t_pre(leaf(V) , [V|S] ,S) . t_pre(tree(L,V,R),[V|S],S2):-
t_pre(L,S,Sl),
t_pre(R,Sl,S2) .
Použit princip rozdílových seznamů
Hana Rudová, Logické programování 1,13. května 2011
6 / \ / \ / \
2 8 % V=2, S=[1,4,3,5|S2] /\        /\      % S=[1|S1]
1     4     7     9     % S1=[4,3,5|S2] / \
3 5
Stromy, grafy
traverse(T,Pře):- t_pre(T,Pře,[]).
t_pre([],S,S). t_pre(leaf(V),[V|S],S). t_pre(tree(L,V,R),[V|S],S2):-
t_pre(L,S,Sl),
t_pre(R,Sl,S2).
6
/ \ / \ / \
2 8 % V=2, S=[1,4,3,5|S2] / \         / \       % S=[1|S1]
1     4     7     9     % S1=[4,3,5|S2] / \
3 5
Modifikuje algoritmus tak, aby byly uzly vypsány v pořadí inorder (nejprve levý podstrom, pak uzel a nakonec pravý podstrom), tj. [1,2,3,4,5,6,7,8,9]
traverse(T,In):- t_in(T,In,[]).
t_pre([],S,S). t_in(leaf(V) , [V|S] ,S) . t_in(tree(L,V,R),S,S2):-
t_in(L,S,[V|S1]),
t_in(R,Sl,S2).
Hana Rudová, Logické programování 1,13. května 2011 6 Stromy, grafy
DÚ: Procházení stromu postorder
Modifikuje algoritmus tak, aby byly uzly vypsány v pořadí postorder (nejprve levý podstrom, pak pravý podstrom a nakonec uzel), tj. [1,3,5,4,2,7,9,8,6]
traverse_post(T,Post):-
t_post(T,Post,[]).
t_pre([],S,S).
t_post(leaf(V) , [V|S] ,S) .
t_post(tree(L,V,R),S,S2):-t_post(L,S,Sl) , t_post(R,Sl,[V|S2]).
6 / \ / \ / \
2 8 / \         / \
14     7 9 / \
3 5
Reprezentace grafu
Reprezentace grafu: pole následníků uzlů
Grafy nebudeme modifikovat, tj. pro reprezentaci pole lze využít term (Orientovaný) neohodnocený graf
graf([2,3],[l,3],[l,2]).
1--2
\ I
graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]).
5— 4 I I
6- -1--2--3
Hana Rudová, Logické programování 1,13. května 2011
Stromy, grafy
?- functorCCraf,graf,PocetUzlu). ?- arg(Uzel,Graf.Sousedi).
1 (Orientovaný) ohodnocený graf [Soused-Ohodnoceni|Sousedi]
graf([2-l,3-2],[1-1,3-2],[1-2,2-2]).
grafC[2-1,4-3,6-1],[1-1,3-2],[2-2],[1-3,5-1],[4-1,6-2],[1-1,5-2]).
Hana Rudová, Logické programování 1,13. května 2011 8 Stromy, grafy
Procházení grafu do hloubky
Napište predikát dfs(Uzel,Craf,Parents) pro procházení grafu Graf do hloubky z uzlu Uzel. Výsledkem je datová struktura Parents, která reprezentuje strom vzniklý při prohledávání do hloubky (pro každý uzel stromu známe jeho rodiče).
Datová struktura pro rodiče uzlů:
■ při reprezentaci rodičů lze využít term s aritou odpovídající počtu uzlů
■ iniciálně jsou argumentu termu volné proměnné
■ na závěr je v N-tém argumentu uložen rodič N-tého uzlu (iniciální uzel označíme empty)
graf([2,3],[l,3],[l,2]). graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]).
1--2       1—2 5—4 5 4
\  I \ II II
\| \ 6--1--2--3 6--1--2--3
3 3 Uzel=4: rodic(4, 1, 2, empty, 6, 1)
Uzel=2: rodic(2,empty,1)
Hana Rudová, Logické programování I, 13. května 2011 9 Stromy, grafy
Procházení grafu do hloubky: algoritmus I
Procházení grafu z uzlu Uzel
■ Vytvoříme term pro rodiče (všichni rodiči jsou zatím volné proměnné)
■ Uzel Uzel má prázdného rodiče a má sousedy Sousedi
■ Procházíme (rekurzivně) všechny sousedy v Sousedi
dfs(Uze"l ,Graf, Parents) :-
functor(Graf,graf,Počet), functor(Parents,rodiče,Počet), argCUzel,Parents,empty), argCUzel,Graf.Sousedi) ,
prochazej_sousedy(Sousedi,Uzel,Graf,Parents) .
Hana Rudová, Logické programování I, 13. května 201 1 10 Stromy, grafy
Procházení grafu do hloubky: algoritmus II
Procházení sousedů uzlu Uzel (pokud Uzel nemá sousedy, tj. Sousedi=[], končíme)
1. Uzel V je první soused
2. Zjistíme rodiče uzlu V ... pomocí arg(V,Parents,Rodič)
3. Pokud jsme V ještě neprošli (tedy nemá rodiče a platí var(Rodic)), tak
(a) nastavíme rodiče uzlu V na Uzel ... pomocí arg/3
(b) rekurzivně procházej všechny sousedy uzlu V
pokud jsme V prošli, dále tímto uzlem nepokračujeme, tj. celkem (var(Rodic) -> true)
4. Procházej zbývající sousedy uzlu Uzel prochazej_sousedy([],_,_,_).
prochazej_sousedy([V|T],Uzel,Graf,Parents) :- arg(V,Parents,Rodič),
( nonvar(Rodic) -> true ; Rodič = Uzel , arg(V,Graf.SousediV),
prochazej_sousedy(SousediV,V,Graf,Parents)
),
prochazej_sousedy(T,Uzel,Graf,Parents).
Hana Rudová, Logické programování 1,13. května 2011
Stromy, grafy
DÚ: Procházení grafu do šířky
Napište predikát bfs(U,C,P) pro procházení grafu C do šířky z uzlu U. Výsledkem procházení je datová struktura P, která reprezentuje strom vzniklý při prohledávání grafu C do šířky (pro každý uzel stromu známe jeho rodiče).
graf([2,3],[l,3],[l,2]).
1--2 1--2
\ I I
\l I
3 3
graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]).
5—4 5—4
I    I I 6__1__2 —3        6__i__2 —3
U=4: rodic(4, 1, 2, empty, 4, 1)
U=2: rodic(2,empty,2)
Hana Rudová, Logické programování 1,13. května 2011
Stromy, grafy