Informàtica. Lliurament 4 grup 10
| 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 |
Es representen els vols d'una aerolínia com un graf dirigit networkx en el que els nodes són aeroports i una aresta dirigida entre dos nodes indica que hi ha un vol directe de la companyia des de l'aeroport origen fins al aeroport destí.
Vegeu, per exemple el graf següent,
creat amb la següent seqüència d'operacions en Python.
>>> import ex1
>>> import networkx as nx
>>> dg = nx.DiGraph()
>>> lnodes = ['Paris', 'Londres', 'Amsterdam', 'Lyon', 'Barcelona', 'Malaga', 'Milà', 'Liverpool', 'Roma']
>>> ledges = [('Paris', 'Londres'), ('Paris', 'Roma'), ('Roma', 'Londres'), ('Paris', 'Amsterdam'), ('Amsterdam', 'Liverpool'), ('Liverpool', 'Londres'), ('Barcelona', 'Milà'), ('Milan', 'Liverpool'), ('Roma', 'Barcelona')]
>>> dg.add_nodes_from(lnodes)
>>> dg.add_edges_from(ledges)
Exercici 1 (5 punts):
Dissenyeu la funció pla_de_vol(digraf, origen, desti, n), que donat un DiGraph de vols com el descrit, donats dos strings que representen l'aeroport origen i l'aeroport destí respectivament i donat un enter n, retorna la llista de totes les combinacions de vols possibles per anar del primer aeroport al segon passant per un total de n aeroports, inclosos l'origen i el destí. Cada combinació ha de ser una llista d'aeroports; ha de començar amb l'aeroport origen i acabar amb l'aeroport destí. La llista ha d'estar ordenada alfabèticament.
Vegeu per exemple, pel graf representat amunt:
>>> ex1.pla_de_vol(dg, 'Paris', 'Londres', 2)
[['Paris', 'Londres']]
>>> ex1.pla_de_vol(dg, 'Paris', 'Londres', 3)
[['Paris', 'Roma', 'Londres']]
>>> ex1.pla_de_vol(dg, 'Paris', 'Londres', 4)
[['Paris', 'Amsterdam', 'Liverpool', 'Londres']]
>>> ex1.pla_de_vol(dg, 'Paris', 'Londres', 5)
[]
>>> dg.add_edge('Barcelona', 'Liverpool')
>>> dg.add_edge('Paris', 'Barcelona')
>>> ex1.pla_de_vol(dg, 'Paris', 'Liverpool', 3)
[['Paris', 'Amsterdam', 'Liverpool'], ['Paris', 'Barcelona', 'Liverpool']]
Deseu la funció al fitxer ex1.py.
Exercici 2: (5 punts)
Dissenyeu la funció connexio(digraf, origen), que donat un DiGraph de vols com el descrit i donat un string que representa un aeroport, retorna la llista ordenada alfabèticament de tots els aeroports als que es pot anar, directa o indirectament a partir de l'aeroport donat.
Vegeu per exemple:
>>> import ex2
>>> import networkx as nx
>>> dg = nx.DiGraph()
>>> lnodes = ['Paris', 'Londres', 'Amsterdam', 'Lyon', 'Barcelona', 'Malaga', 'Milà', 'Liverpool', 'Turí', 'Madrid', 'Valencia','Zurich']
>>> ledges = [('Paris', 'Londres'), ('Paris', 'Roma'), ('Roma', 'Londres'), ('Paris', 'Amsterdam'), ('Amsterdam', 'Liverpool'), ('Liverpool', 'Londres'), ('Barcelona', 'Milà'), ('Milan', 'Liverpool'), ('Roma', 'Barcelona')]
>>> dg.add_nodes_from(lnodes)
>>> dg.add_edges_from(ledges)
>>> ex2.connexio(dg, 'Paris')
['Amsterdam', 'Barcelona', 'Liverpool', 'Londres', 'Milà', 'Roma']
>>> ex2.connexio(dg, 'Liverpool')
['Londres']
>>> dg.add_edge('Lisboa', 'Oporto')
>>> ex2.connexio(dg, 'Lisboa')
['Oporto']
>>> ex2.connexio(dg, 'Oporto')
[]
Deseu la funció al fitxer ex2.py.