''' Diciamo che un dizionario d rappresenta un albero (e lo indichiamo come dizionario-albero) se ciascuna chiave di d e' un identificativo di un nodo dell'albero e l'attributo della chiave e' la lista (eventualmente vuota) degli identificativi dei figli del nodo. Gli identificativi dei nodi all'interno delle liste sono in ordine lessicografico crescente. Ecco un esempio di dizionario d che rappresenta un dizionario-albero d={ #'a':['b'], 'b':['c','d'], 'c':['i'], 'd':['e','l'], 'e':['f','g','h'], 'f':[], 'g':[], 'h':[], 'i':[], 'l':[] } L'albero rappresentato da d e' 'a' | _____________'b'____________ | | 'c' ________'d'_______ | | | 'i' _______'e'_______ 'l' | | | 'f' 'g' 'h' Implementare le seguenti funzioni: 1) la funzione genera_sottoalbero(fnome,x,fout) che, presi: - il nome di un file json contenente un dizionario-albero d (fonome) - un identificativo x - il nome di un file json (fout) produce il dizionario-albero che rappresenta il sottoalbero radicato nell'identificativo x che si ottiene dal dizionario-albero d. Il dizionario-albero ottenuto va registrato nel file fout. Se l'identificativo x non e' tra i nodi di d allora il dizionario-albero prodotto deve essere vuoto. Ad esempio se fnome contiene il dizionario-albero d allora dopo l'esecuzione di genera_sottoalbero(fname,'d',fout) il file fout conterra' il dizionario {'f': [], 'g': [], 'h': [], 'e': ['f', 'g', 'h'], 'l': [], 'd': ['e', 'l']} 2) la funzione cancella_sottoalbero(fnome,x,fout) che, presi: - il nome di un file json contenente un dizionario-albero d (fonome) - un identificativo x - il nome di un file json (fout) ricava da d il sottoalbero radicato in x e lo salva nel file fout. Se x non e' presente tra le chiavi di d allora il dizionario-albero d non viene modificato. Ad esempio se fnome contiene il dizionario-albero d allora dopo l'esecuzione di cancella_sottoalbero(fname,'d',fout) il file fout conterra' il dizionario {'a': ['b'], 'b': ['c'], 'c': ['i'], 'i':[]} 3) la funzione dizionario_livelli(fnome, fout) che, presi: - il nome di un file json contenente un dizionario-albero d (fonome) - il nome di un file json (fout) costruisce il dizionario che ha come chiavi i livelli del dizionario-albero d. L'attributo di una chiave di valore x e' la lista degli identificativi dei nodi che si trovano a livello x nell'albero rappresentato da d. La lista e' ordinata lessicograficamente ed in modo crescente. Il dizionario cosi' costruito va registrato nel file fout. Ad esempio se fnome contiene il dizionario-albero d allora dopo l'esecuzione di dizionario_livelli(fname,fout) il file fout conterra' il dizionario {0: ['a'], 1: ['b'], 2: ['c', 'd'], 3: ['e','i','l'], 4: ['f', 'g', 'h']} 4) la funzione dizionario_gradi_antenati(fnome,y,fout) che, presi: - il nome di un file json contenente un dizionario-albero d (fonome) - un intero y - il nome di un file json (fout) costruisce il dizionario che ha come chiavi gli identificativi dei nodi dell'albero rappresentato dal dizionario-albero d, Attributo di una chiave di valore x e' il numero di antenati di grado y che ha il nodo con identificativo x nell'albero. Registra il dizionario costruito nel file fout. Ad esempio se fnome contiene il dizionario-albero d allora dopo l'esecuzione di dizionario_gradi_antenati(fnome,2,fout) il file fout conterra' il dizionario {'a': 0, 'b': 0, 'c': 1, 'd': 1, 'e': 2, 'f': 2, 'g': 2, 'h': 2, 'i': 1, 'l': 2} {'a': 0, 'b': 0, 'c': 1, 'd': 1, 'e': 2, 'f': 2, 'g': 2, 'h': 2, 'i': 1, 'l': 2} AVVERTENZE: non usare caratteri non ASCII, come le lettere accentate; non importare moduli che non sono nella libreria standard. ''' import json def genera_sottoalbero(fnome,x,fout): '''inserire qui il vostro codice''' with open(fnome, encoding='utf8') as f: albero = json.load(f) sottoalbero = subtree(albero, x) with open(fout, mode='w', encoding='utf8') as f1: json.dump(sottoalbero, f1) return sottoalbero def subtree(albero, chiave): sottoalbero = { chiave: albero[chiave].copy() } for son in albero[chiave]: sottoalbero.update(subtree(albero, son)) return sottoalbero def cancella_sottoalbero(fnome,x,fout): '''inserire qui il vostro codice''' with open(fnome, encoding='utf8') as f: albero = json.load(f) print(albero) cancellato = del_subtree(albero, x) with open(fout, mode='w', encoding='utf8') as f1: json.dump(cancellato, f1) return cancellato def del_subtree(albero, nodo): _del_subtree(albero, nodo) for k, v in albero.items(): if nodo in v: v.remove(nodo) return albero def _del_subtree(albero, nodo): '''elimino il nodo ed i figli e poi lo tolgo dal padre''' for son in albero[nodo]: _del_subtree(albero, son) del albero[nodo] def dizionario_livelli(fnome,fout): '''inserire qui il vostro codice''' with open(fnome, encoding='utf8') as f: albero = json.load(f) radice = trova_radice(albero) livelli = {} costruisci_livelli(albero, radice, 0, livelli) print(livelli) for v in livelli.values(): v.sort() print(livelli) #with open(fout, mode='w', encoding='utf8') as f1: # json.dump(livelli, f1) #return livelli def trova_radice(albero): nodi = set(albero.keys()) figli = set() for sons in albero.values(): figli |= set(sons) radici = nodi - figli print(radici) return radici.pop() def costruisci_livelli(albero, radice, livello, risultato): if livello not in risultato: risultato[livello] = [] risultato[livello].append(radice) for son in albero[radice]: costruisci_livelli(albero, son, livello+1, risultato) def dizionario_gradi_antenati(fnome,y,fout): '''inserire qui il vostro codice''' with open(fnome, encoding='utf8') as f: albero = json.load(f) padri = trova_padri(albero) print(padri) nodi = albero.keys() dga = {} for nodo in nodi: if nodo in padri: padre = padri[nodo] dga[nodo] = conta_antenati(padre, y, padri, albero) else: dga[nodo] = 0 print(dga) def trova_padri(albero): padri = {} for nodo, figli in albero.items(): for f in figli: padri[f] = nodo return padri def conta_antenati(nodo, y, padri, albero): if nodo not in padri: if len(albero[nodo]) == y: return 1 else: return 0 else: padre = padri[nodo] n = conta_antenati(padre, y, padri, albero) if len(albero[nodo]) == y: return 1+n else: return n if __name__ == '__main__': #print(genera_sottoalbero('Alb10.json', 'd', 'test_generaAlb10.json')) #print(cancella_sottoalbero('Alb10.json', 'd', 'test_cancellaAlb10.json')) #print(dizionario_livelli('Alb10.json', 'test_livelliAlb10.json')) print(dizionario_gradi_antenati('Alb10.json', 2, 'test_livelliAlb10.json'))