| Organització: | Secció ETSEIB, Departament LSI, UPC |
|---|---|
| Data: | 10 de desembre de 2014 |
| Copyright: | Reconeixement-CompartirIgual 3.0 No adaptada de Creative Commons |
| Durada: | 30 minuts |
Hem utilitzat un graf dirigit de networkx (un DiGraph) per a representar les relacions familiars entre persones. En aquest graf, només hi ha desada la relació pare/mare-fill/a, és a dir, els nodes del graf són les persones, identificades pel nom (un string) i una aresta dirigida de x a y indica que x és progenitor de y.
Per exemple el graf següent,
creat amb la següent seqüència d'operacions en Python,
>>> import networkx as nx
>>> g = nx.DiGraph()
>>> gent = ['Joan','Anna','Pere','Josep','Maria','Carla','Rut','Gisela']
>>> fills = [ ('Joan','Anna'), ('Joan','Pere'), ('Joan','Josep'), ('Maria','Anna'), ('Maria','Pere'), ('Carla','Josep'), ('Pere','Rut'), ('Pere','Gisela') ]
>>> g.add_nodes_from(gent)
>>> g.add_edges_from(fills)
representa una família de 8 membres, en la qual en Joan té tres fills (Anna, Pere, Josep), la Maria dos (Anna, Pere), la Carla un (en Josep) i en Pere dues filles (Rut i Gisela).
Dissenyeu la funció son_germans(g, a, b) que, donat un digraf g com el descrit i els noms de dues persones, retorna un booleà que indica si a i b són germans, o sigui, si tenen els dos mateixos progenitors en el graf g. En el graf de l'exemple anterior,
>>> import ex1 >>> ex1.son_germans(g, 'Anna', 'Pere') True >>> ex1.son_germans(g, 'Josep', 'Rut') False >>> ex1.son_germans(g, 'Pere', 'Josep') # no són germans, sinó germanastres False >>> ex1.son_germans(g, 'Rut','Gisela') # potser són germanes, però al graf només hi consta un progenitor False
Deseu la funció al fitxer ex1.py.
Dissenyeu la funció nets(g, a) que, donat un digraf g com el descrit i el nom d'una persona, retorna una llista amb els noms dels seus néts (els fills dels fills), ordenada lexicogràficament. En el graf de l'exemple anterior,
>>> import ex2 >>> ex2.nets(g, 'Joan') ['Gisela', 'Rut'] >>> ex2.nets(g, 'Maria') ['Gisela', 'Rut'] >>> ex2.nets(g, 'Carla') []
Deseu la funció al fitxer ex2.py.