Árvore Genealógica

No texto de apoio à disciplina é introduzido um conceito simplista de árvore genealógica. Estas árvores são representadas por um dicionário em que as chaves são nomes de pessoas (um progenitor) e os valores são listas de nomes de pessoas (os filhos). Esta representação permite, por exemplo, obter os filhos de alguém de modo trivial:

view sourceprint?

1.def filhos(dicio,progenitor):

2.    """ lista dos filhos."""

3.    return dicio.get(progenitor,[])

Também é fácil listar os netos de alguém. Por exemplo:

view sourceprint?

01.def netos(dicio,progenitor):

02.    """ Lista netos. Filhos dos filhos"""

03.    desc1 = filhos(dicio,progenitor)

04.    if desc1:

05.        net = []

06.        for elem in desc1:

07.            desc2 = filhos(dicio,elem)

08.            if desc2:

09.                net = net + desc2

10.        return net

11.    else:

12.        return []

Esta solução calcula primeiro os filhos e, caso existam, os filhos dos filhos. Não é difícil propor versões alternativas para esta questão. Por exemplo:

view sourceprint?

1.def netos_b(arv_genea,progenitor):

2.    net = []

3.    desc1 = filhos(arv_genea,progenitor)

4.    for prog in desc1:

5.        net.extend(filhos(arv_genea,prog))

6.    return net

Aqui simplificamos o código no interior do ciclo recorrendo ao método extend. Mas ainda podemos aproximarmo-nos mais da defino natural: netos são os filhos dos filhos:

view sourceprint?

01.def netos_b(dicio ,progenitor):

02.    """ Lista dos netos. Os filhos dos filhos"""

03.    return filhos_b(dicio,filhos_b(dicio,[progenitor]))

04. 

05.def filhos_b(dicio,lista_progenitores):

06.    lista_filhos = []

07.    for filho in lista_progenitores:

08.        lista_filhos.extend(dicio.get(filho,[]))

09.    return lista_filhos

Note-se que tivemos que alterar a função filhos para agora me dar a lista dos filhos de um conjunto de pessoas.
Agora o conceito básico de progenitor de alguém:

view sourceprint?

1.def progenitor(ag,nome):

2.    for p,fil in ag.items():

3.        if nome in fil:

4.            return p

5.    return None

Neste caso vamos procurar o nome na lista dos filhos de alguém que, a existir, será o progenitor. Passemos a outros exemplos. Irmãos são pessoas que têm um progenitor comum. Com está organizada a árvore genealógica cada pessoa tem um progenitor único, logo:

view sourceprint?

1.def irmaos(ag,nome1,nome2):

2.    """ Têm o mesmo progenitor?"""

3.    prog1 = progenitor(ag, nome1)

4.    prog2 = progenitor (ag,nome2)

5.    return prog1 == prog2

Socorrendo-nos de novo da ideia de progenitor podemos definir o conceito de avô/avó.

view sourceprint?

1.def avo(dic,nome):

2.    """ Quem é o avô/avó do nome."""

3.    prog = progenitor(dic,nome)

4.    if prog:

5.        return progenitor(dic,prog)

6.    return None

Deixamos ao leitor o cuidado de definir outras relações de parentesco. Por exemplo, tente o conceito de primos (os filhos de irmãos). Por outro lado, alguns dos conceitos acima são booleanos. Imagine que em vez de se saber se duas pessoas são primos se pretende saber quais os primos de alguém. Não lhe deve ser difícil chegar à solução.
Finalmente, pense numa implementação mais realista de uma árvore genealógica, em que cada pessoa tem associado os seus pais. E faça tudo de novo!!!