Stromy, grafy
Stromy
Uzly stromu Tree jsou reprezentovány termy
tree(Left,Value,Right): Left a Right jsou opet stromy, Value je ohodnocení uzlu
-í* leaf(Value): Value je ohodnoceni uzlu
6
M Příklad:
/ \
/ \ / \
2 8
/ \ / 14 7
/ \
3 5
tree(tree(leaf(1), 2, tree(leaf(3),4,leaf(5)) ), 6, tree(leaf(7),8,[]) )
Hana Rudová, Logické programování I, 13. května 2011 2 Stromy, grafy
Stromy: hledáni prvku in(X,T)
Predikát in(X,T) uspeje, pokud se prvek X nachází ve stromu T. Prvek X se nachází ve strome T, jestliže
C Xje listem stromu T, jinak leaf(X) & Xje koren stromu T, jinak tree(Left,X,Right) -í* X je menší než koren stromu T, pak se nachází v levém podstromu T, jinak & X se nachází v pravém podstromu T
Hana Rudová, Logické programování I, 13. kvetna 2011
3
Stromy, grafy
Stromy: hledáni prvku in(X,T)
Predikát in(X,T) uspeje, pokud se prvek X nachází ve stromu T. Prvek X se nachází ve strome T, jestliže
C Xje listem stromu T, jinak leaf(X)
& Xje koren stromu T, jinak tree(Left,X,Right)
-í* X je menší než koren 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)) :- 1.
in(X, tree(_,X,_)) :- 1.
in(X, tree(Left, Root, Right) ) :-
X<Root, 1,
in(X,Left). in(X, tree(Left, Root, Right) ) :-
in(X,Right).
Hana Rudová, Logické programování I, 13. kvetna 2011 3 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 korenem V, vlevo má leaf(X) (vpravo je []) JS> pokud T=tree(L,V,R) a X>V, pak v novém strome L ponechej a X pridej doprava (rekurzivne)
pokud T=tree(L,V,R) a X<V, pak v novém strome R ponechej a X pridej doleva (rekurzivne)
Hana Rudová, Logické programování I, 13. kvetna 2011
4
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 korenem V, vlevo má leaf(X) (vpravo je []) JS> pokud T=tree(L,V,R) a X>V, pak v novém strome L ponechej a X pridej doprava (rekurzivne)
pokud T=tree(L,V,R) a X<V, pak v novém strome R ponechej a X pridej doleva (rekurzivne)
add([],X,leaf(X)) :- 1.
add(leaf(V), X, tree([],V,leaf(X) ) :- X>V, 1. add(leaf(V), X, tree(leaf(X),V,[]) ) :- 1. X<V,
Hana Rudová, Logické programování I, 13. kvetna 2011
4
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 korenem V, vlevo má leaf(X) (vpravo je []) JS> pokud T=tree(L,V,R) a X>V, pak v novém strome L ponechej a X pridej doprava (rekurzivne)
pokud T=tree(L,V,R) a X<V, pak v novém strome R ponechej a X pridej doleva (rekurzivne)
add([],X,leaf(X)) !.
add(leaf(V), X, tree([],V,leaf(X) )      X>V, !. add(leaf(V), X, tree(leaf(X),V,[]) )       !. X<V, add(tree(L,V,R), X, tree(L,V,R1)) :-X>V,  !, add(R,X,R1). add(tree(L,V,R), X, tree(L1,V,R))      X<V, add(L,X,L1).
Hana Rudová, Logické programování I, 13. kvetna 2011
4
Stromy, grafy
Procházení stromů
Napište predikát traverse(Tree, List), který projde traversálne strom Tree. Seznam List pak obsahuje všechny prvky tohoto stromu.
Poradí preorder: nejprve uzel, pak levý podstrom, nakonec pravý podstrom
?- traverse(tree(tree(leaf(1),2,tree(leaf(3),4,leaf(5))),6,
tree(leaf(7),8,leaf(9))),  [6,2,1,4,3,5,8,7,9]). (preorder)
traverse(T,Pre):- t_pre(T,Pre,[]).
t_pre([],S,S). t_pre(leaf(V),[V|S],S).
t_pre(tree(L,V,R),[V|S],S2):-t_pre(L,S,S1), t_pre(R,S1,S2).
6
/ \ / \
/\
2 8        % V=2, S=[1,4,3,5|S2]
/ \        / \      % S=[1|S1] 14     7     9% S1=[4,3,5|S2]
/\
35
Hana Rudová, Logické programování I, 13. kvetna 2011
5
Stromy, grafy
Procházení stromů
Napište predikát traverse(Tree, List), který projde traversálne strom Tree. Seznam List pak obsahuje všechny prvky tohoto stromu.
Poradí preorder: nejprve uzel, pak levý podstrom, nakonec pravý podstrom
?- traverse(tree(tree(leaf(1),2,tree(leaf(3),4,leaf(5))),6,
tree(leaf(7),8,leaf(9))),  [6,2,1,4,3,5,8,7,9]). (preorder)
traverse(T,Pre):- t_pre(T,Pre,[]).
t_pre([],S,S).
t_pre(leaf(V),[V|S],S).
t_pre(tree(L,V,R),[V|S],S2):-
t_pre(L,S,S1),
t_pre(R,S1,S2).
Použit princip rozdílových seznamu
6
/ \ / \
/\
2 8        % V=2, S=[1,4,3,5|S2]
/ \        / \      % S=[1|S1] 14     7     9% S1=[4,3,5|S2]
/\
35
Hana Rudová, Logické programování I, 13. kvetna 2011
5
Stromy, grafy
Procházení stromů
traverse(T,Pre):- t_pre(T,Pre,[]).
t_pre([],S,S).
t_pre(leaf(V),[V|S],S).
t_pre(tree(L,V,R),[V|S],S2):-
t_pre(L,S,S1),
t_pre(R,S1,S2).
6
/ \ / \
/\
2 8
/ \    / \
14     7 9
/\
3 5
% V=2, S=[1,4,3,5|S2]
% S=[1|S1]
% S1=[4,3,5|S2]
Modifikuje algoritmus tak, aby byly uzly vypsány v poradí inorder (nejprve levý podstrom, pak uzel a nakonec pravý podstrom), tj. [1,2,3,4,5,6,7,8,9]
Hana Rudová, Logické programování I, 13. kvetna 2011
6
Stromy, grafy
Procházení stromů
traverse(T,Pre):- t_pre(T,Pre,[]).
t_pre([],S,S).
t_pre(leaf(V),[V|S],S).
t_pre(tree(L,V,R),[V|S],S2):-
t_pre(L,S,S1),
t_pre(R,S1,S2).
6
/ \ / \
/\
2 8
/ \    / \
14     7 9
/\
3 5
% V=2, S=[1,4,3,5|S2] % S1=[4,3,5|S2]
Modifikuje algoritmus tak, aby byly uzly vypsány v poradí 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,S1,S2).
Hana Rudová, Logické programování I, 13. kvetna 2011
Stromy, grafy
6
DÚ: Procházení stromu postorder
Modifikuje algoritmus tak, aby byly uzly vypsány v poradí postorder (nejprve levý podstrom, pak pravý podstrom a nakonec uzel), tj. [1,3,5,4,2,7,9,8,6]
Hana Rudová, Logické programování I, 13. kvetna 2011
7
Stromy, grafy
DÚ: Procházení stromu postorder
Modifikuje algoritmus tak, aby byly uzly vypsány v poradí 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,[]). 6
/ \
t_pre([],S,S). / \
t_post(leaf(V),[V|S],S). / \
t_post(tree(L,V,R),S,S2):- 2 8
/ \      / \
t_post(L,S,S1), 14     7 9
t_post(R,S1,[V|S2]). / \
3 5
Hana Rudová, Logické programování I, 13. kvetna 2011
7
Stromy, grafy
Reprezentace grafu
Reprezentace grafu: pole následníku uzlů
Grafy nebudeme modifikovat, tj. pro reprezentaci pole lze využít term
(Orientovaný) neohodnocený graf
1--2
\ | \|
3
?- functor(Graf,graf,PocetUzlu). ?- arg(Uzel,Graf,Sousedi).
6--1--2--3
& (Orientovany) ohodnocený graf [Soused-Ohodnoceni|Sousedi]
Hana Rudová, Logické programování I, 13. kvetna 2011 8
Stromy, grafy
Procházení grafu do hloubky
Napište predikát dfs(Uzel,Graf,Parents) pro procházení grafu Graf do hloubky z uzlu Uzel. Výsledkem je datová struktura Parents, která reprezentuje strom vzniklý pri prohledávání do hloubky (pro každý uzel stromu známe jeho rodiCe).
Datová struktura pro rodiCe uzlu:
pri reprezentaci rodiCu lze využít term s aritou odpovídající poCtu uzlu
ií> iniciálne jsou argumentu termu volné promenné
C- na záver je v N-tém argumentu uložen rodic N-tého uzlu (iniciální uzel oznacíme empty)
1--2       1--2 5--4 5 4
\  | \ |    | | |
\| \ 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. kvetna 2011 9 Stromy, grafy
Procházení grafu do hloubky: algoritmus I
Procházení grafu z uzlu Uzel
Vytvoríme term pro rodice (všichni rodici jsou zatím volné promenné) JS> Uzel Uzel má prázdného rodice a má sousedy Sousedi
Procházíme (rekurzivne) všechny sousedy v Sousedi
dfs(Uzel,Graf,Parents) :-
functor(Graf,graf,Pocet), functor(Parents,rodice,Pocet), arg(Uzel,Parents,empty), arg(Uzel,Graf,Sousedi),
prochazej_sousedy(Sousedi,Uzel,Graf,Parents).
Hana Rudová, Logické programování I, 13. kvetna 2011
10
Stromy, grafy
Procházení grafu do hloubky: algoritmus II
Procházení sousedů uzlu Uzel (pokud Uzel nemá sousedy, tj. Sousedi=[], koncíme)
1. Uzel Vje první soused
2. Zjistíme rodice uzlu V ... pomocí arg(V,Parents,Rodic)
3. Pokud jsme V ješte neprošli (tedy nemá rodice a platí var(Rodic)), tak
(a) nastavíme rodice uzlu V na Uzel ... pomocí arg/3
(b) rekurzivne procházej všechny sousedy uzlu V
pokud jsme V prošli, dále tímto uzlem nepokracujeme, tj. celkem (var(Rodic) -> true)
4. Procházej zbývající sousedy uzlu Uzel
Hana Rudová, Logické programování I, 13. kvetna 2011
11
Stromy, grafy
Procházení grafu do hloubky: algoritmus II
Procházení sousedu uzlu Uzel (pokud Uzel nemá sousedy, tj. Sousedi=[], konCíme)
1. Uzel Vje první soused
2. Zjistíme rodice uzlu V ... pomocí arg(V,Parents,Rodic)
3. Pokud jsme V ješte neprošli (tedy nemá rodice a platí var(Rodic)), tak
(a) nastavíme rodice uzlu V na Uzel ... pomocí arg/3
(b) rekurzivne procházej všechny sousedy uzlu V
pokud jsme V prošli, dále tímto uzlem nepokracujeme, 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,Rodic),
( nonvar(Rodic) -> true ; Rodic = Uzel, arg(V,Graf,SousediV),
prochazej_sousedy(SousediV,V,Graf,Parents)
),
prochazej_sousedy(T,Uzel,Graf,Parents).
Hana Rudová, Logické programování I, 13. kvetna 2011 11 Stromy, grafy
DÚ: Procházení grafu do šířky
Napište predikát bfs(U,G,P) pro procházení grafu G do šírky z uzlu U. Výsledkem procházení je datová struktura P, která reprezentuje strom vzniklý pri prohledávání grafu G do šírky (pro každý uzel stromu známe jeho rodice).
graf([2,3],[1,3],[1,2]).
graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]).
1--2
\ | \|
3
1-- 2
5- -4 | |
6- -1--2--3
3
U=2: rodic(2,empty,2)
5- - 4
|
6- -1--2-- 3
U=4: rodic(4, 1, 2, empty, 4, 1)
Hana Rudová, Logické programování I, 13. kvetna 2011
12
Stromy, grafy