#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
from linked_lists import LinkedList, Cons, Nil, member, member_anyX
def stree(graph):
for edge in member_anyX(graph):
for kostra in spread(LinkedList([edge]), graph):
yield kostra
def spread(akumulator_kostry, graph):
for akumulator_kostry1 in addedge(akumulator_kostry, graph):
for kostra in spread(akumulator_kostry1, graph):
yield kostra
try:
next(addedge(akumulator_kostry, graph))
except StopIteration: # nelze pridat hranu
yield akumulator_kostry
def addedge(akumulator_kostry, graph):
for x, y in adjacent_anyXY(graph):
if node(x, akumulator_kostry) and not node(y, akumulator_kostry):
yield Cons((x, y), akumulator_kostry)
def adjacent_anyY(x, edges):
for a, b in member_anyX(edges):
if x == a:
yield b
if x == b:
yield a
def adjacent_anyXY(edges):
for a, b in member_anyX(edges):
yield (a, b)
yield (b, a)
def node(x, graph):
try:
next(adjacent_anyY(x, graph))
return True
except StopIteration:
return False
# demonstracni vypis
if __name__ == "__main__":
print('Kostra grafu')
print('Volani stree(LinkedList([("a", "b"), ("b", "c"), ("b", "d"), ("c", "d")])) vrati:')
for kostra_ in stree(LinkedList([("a", "b"), ("b", "c"), ("b", "d"), ("c", "d")])):
print(' %s' % kostra_)
Kostra grafu
Volani stree(LinkedList([("a", "b"), ("b", "c"), ("b", "d"), ("c", "d")])) vrati:
[('b', 'd'), ('b', 'c'), ('a', 'b')]
[('c', 'd'), ('b', 'c'), ('a', 'b')]
[('b', 'c'), ('b', 'd'), ('a', 'b')]
[('d', 'c'), ('b', 'd'), ('a', 'b')]
[('b', 'd'), ('b', 'a'), ('b', 'c')]
[('c', 'd'), ('b', 'a'), ('b', 'c')]
[('b', 'a'), ('b', 'd'), ('b', 'c')]
[('b', 'a'), ('c', 'd'), ('b', 'c')]
[('b', 'c'), ('b', 'a'), ('b', 'd')]
[('d', 'c'), ('b', 'a'), ('b', 'd')]
[('b', 'a'), ('b', 'c'), ('b', 'd')]
[('b', 'a'), ('d', 'c'), ('b', 'd')]
[('b', 'a'), ('c', 'b'), ('c', 'd')]
[('b', 'a'), ('d', 'b'), ('c', 'd')]
| % nacteni:
/* ['2.10_23.pl']. */
stree(Graph,Tree) :- member(Edge,Graph),spread([Edge],Tree,Graph).
spread(Tree1,Tree,Graph) :- addedge(Tree1,Tree2,Graph),spread(Tree2,Tree,Graph).
spread(Tree,Tree,Graph) :- \+ addedge(Tree,_,Graph).
addedge(Tree,[A-B|Tree],Graph) :- adjacent(A,B,Graph),node(A,Tree), \+ node(B,Tree).
adjacent(A,B,Graph) :- member(A-B,Graph);member(B-A,Graph).
node(A,Graph) :- adjacent(A,_,Graph),!.
% demonstracni vypis
% abychom se vyhli varovanim "Redefined static procedure ..."
:- dynamic
write_all_X/3,
start/0.
write_all_X(Goal,X,Name):-
call(Goal),write(' '),write(Name),write(' = '),write(X),nl,fail.
write_all_X(_,_,_).
start:-
write('Kostra grafu'),nl,
write('Volani "stree([a-b,b-c,b-d,c-d],T)" vrati:'),nl,
write_all_X(stree([a-b,b-c,b-d,c-d],T), T, 'T').
?-start.
:- retractall(write_all_X/3).
:- retractall(start/0).
Kostra grafu
Volani "stree([a-b,b-c,b-d,c-d],T)" vrati:
T = [b-d,b-c,a-b]
T = [c-d,b-c,a-b]
T = [b-c,b-d,a-b]
T = [d-c,b-d,a-b]
T = [b-a,b-d,b-c]
T = [b-a,c-d,b-c]
T = [b-d,b-a,b-c]
T = [c-d,b-a,b-c]
T = [b-a,b-c,b-d]
T = [b-c,b-a,b-d]
T = [d-c,b-a,b-d]
T = [b-a,d-c,b-d]
T = [b-a,c-b,c-d]
T = [b-a,d-b,c-d]
|