#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
from linked_lists import LinkedList, Cons, Nil, member, member_anyX
def path(a, z, graph):
for cesta, cena in path1(a, LinkedList([z]), 0, graph, 1):
yield (cesta, cena)
def path1(a, akumulator_cesty, akumulator_ceny, graph, depth):
if akumulator_cesty.head == a:
yield (akumulator_cesty, akumulator_ceny)
else:
y = akumulator_cesty.head
for x, cenaXY in adjacent_anyXcenaXY(y, graph):
if not member(x, akumulator_cesty):
for cesta, cena in path1(a, Cons(x, akumulator_cesty),
akumulator_ceny + cenaXY, graph, depth+1):
yield (cesta, cena)
def adjacent_anyXcenaXY(y, edges):
for a, b, cenaAB in member_anyX(edges):
if y == a:
yield (b, cenaAB)
if y == b:
yield (a, cenaAB)
# demonstracni vypis
if __name__ == "__main__":
print('Cesta v grafu\n')
cesta_, cena_ = next(path("s", "u", LinkedList([
("s", "t", 3), ("t", "v", 1), ("t", "u", 5), ("u", "t", 2), ("v", "u", 2)])))
print('Cesta=%s' % cesta_)
print('Cena=%d\n' % cena_)
Cesta v grafu
Cesta=['s', 't', 'u']
Cena=8
| % nacteni:
/* ['2.9.2_22.pl']. */
path(A,Z,Graf,Cesta,Cena) :- path1(A,[Z],0,Graf,Cesta,Cena).
path1(A,[A|Cesta1],Cena1,_,[A|Cesta1],Cena1).
path1(A,[Y|Cesta1],Cena1,Graf,Cesta,Cena) :- adjacent(X,Y,CenaXY,Graf),
\+ member(X,Cesta1),Cena2 is Cena1+CenaXY,
path1(A,[X,Y|Cesta1],Cena2,Graf,Cesta,Cena).
adjacent(X,Y,CenaXY,Graf) :- member(X-Y/CenaXY,Graf);member(Y-X/CenaXY,Graf).
start:-
write('Cesta v grafu'),nl, nl,
path(s, u, [s-t/3, t-v/1, t-u/5, u-t/2, v-u/2], Cesta, Cena),
write('Cesta='), write(Cesta), nl,
write('Cena='), write(Cena), nl, nl.
?-start.
Cesta v grafu
Cesta=[s,t,u]
Cena=8
|