3. Grafs (3 punts)

En aquest problema haureu de treballar amb grafs que representen un arbre genealògic, que ja coneixeu. Per exemple:

../../../../_images/familia.svg

3.1. Avis (2 punts)

Dissenyeu la funció següent, que heu de desar al fitxer familiars.py:

familiars.avis(g, nom)
Paràmetres:

  • g – una instancia de DiGraph que representa un arbre genealògic

  • nom – el nom d’una persona (str)

Retorna:

una llista (list) dels avis i àvies de la persona donada. La llista ha d’estar formada per tuples (nom, data de naixement) per cada avi o àvia. Els tuples han d’estar ordenats per ordre alfabètic.

Per exemple, essent g el graf genealògic corresponent a la figura anterior, aquesta funció ha de respondre així:


>>> from familiars import avis
>>> avis(g, 'Nil')
[('Carlota', datetime.date(1974, 1, 9)), ('Martha', datetime.date(1969, 5, 5)), ('Oriol', datetime.date(1967, 3, 7)), ('Pau', datetime.date(1961, 3, 7))]
>>> avis(g, 'Pau')
[('Felip', datetime.date(1910, 6, 9)), ('Nadia', datetime.date(1910, 5, 10))]
>>> avis(g, 'Neus')
[]

Disposeu de jocs de proves al fitxer tests-avis.txt.

3.2. Matussalem i benjamí (1 punt)

Dissenyeu la funció següent, que heu de desar al mateix fitxer familiars.py:

familiars.matben(g)
Paràmetres:

g – una instancia de DiGraph que representa un arbre genealògic

Retorna:

un tuple (tuple) amb els noms de dues persones del graf. Aquesta parella és tal que la primera persona és un avantpassat de la segona i és la parella que més edat els separa de totes les parelles possibles d’avantpassat/descendent del graf.

Per exemple, essent g el graf genealògic corresponent a la figura anterior, aquesta funció ha de respondre així:


>>> from familiars import matben
>>> matben(g)
('Nadia', 'Nil')
>>> g.remove_node('Nil')
>>> matben(g)
('Felip', 'Joan')

Observeu que en la parella a trobar, l’avantpassat no té antecessors i el descendent no té successors. Disposeu de jocs de proves al fitxer tests-matben.txt.