| 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 |
Volem utilitzar un graf no dirigit de networkx per a representar la xarxa de metro d'una ciutat. Els nodes del graf són les parades i les arestes els túnels que les uneixen. Les arestes estan etiquetades amb un atribut 'linia', corresponent al nom de la línia entre les dues parades.
Un exemple de graf és:
creat amb la següent seqüència d'operacions en Python,
>>> import networkx as nx >>> metro = nx.Graph() >>> metro.add_path(['A1', 'A2', 'A3', 'X1', 'A4', 'X3'], linia='A') >>> metro.add_path(['B1', 'B2', 'X1', 'B3', 'X2', 'B4'], linia='B') >>> metro.add_path(['C1', 'C2', 'C3', 'X1', 'C4', 'C5', 'C6', 'C7', 'X2', 'C8', 'C9'], linia='C') >>> metro.add_path(['D1', 'X2', 'D2', 'D3', 'D4', 'D5', 'X3', 'D6', 'D7', 'X1', 'D8', 'D9'], linia='D')
Dissenyeu la funció nTransbords(metro, cami) que, donat un graf metro com el descrit i un trajecte representat com un camí (llista de nodes), retorna el nombre de transbords que cal fer (canvi de línies a fer al llarg del trajecte). En el graf de l'exemple anterior,
>>> nTransbords(metro, ['A1', 'A2', 'A3', 'X1', 'A4', 'X3', 'D5', 'D4', 'D3', 'D2', 'X2', 'C8']) 2 >>> nTransbords(metro, ['A1', 'A2', 'A3', 'X1', 'B3', 'X2', 'C8']) 2 >>> nTransbords(metro, ['A1', 'A2', 'A3', 'X1', 'D7', 'D6', 'X3', 'D5', 'D4', 'D3', 'D2', 'X2', 'C8']) 2 >>> nTransbords(metro, ['A1', 'A2', 'A3', 'X1', 'C4', 'C5', 'C6', 'C7', 'X2', 'C8']) 1
Deseu la funció al fitxer ex1.py.
Afegirem a les arestes del graf anterior un atribut més anomenat temps que indica el temps en segons que triga un tren en passar entre les dues estacions que connecta l'aresta.
Dissenyeu la funció tempsViatge(metro, a, b) que, donat un graf metro com el descrit i el nom de dues estacions a i b, retorna un tuple amb una llista de nodes per on passa el trajecte més curt en temps que va d'a a b , i el temps final del trajecte més curt en segons.
>>> tempsViatge(metro, 'C8','C9') (['C8', 'C9'], 45) >>> tempsViatge(metro, 'C8','D2') (['C8', 'X2', 'D2'], 164)
Per resoldre aquest problema recomanem que llegiu detingudament la documentació sobre camins mínims de networkx.
Deseu la funció al fitxer ex2.py.