#!/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')]