1. Xarxa de metro amb temps

En aquest problema treballarem amb la representació de la xarxa de metro d’una ciutat que ja coneixeu. Ara bé, en aquest cas les arestes del graf entre dues parades de metro no només tindran una etiqueta 'linia' que indica la línia de metro a la qual pertanyen, sinó que hi afegirem una segona etiqueta, de nom 'temps', que indicarà el temps que es triga a realitzar el trajecte entre les dues parades. Vegeu-ne un exemple:

Xarxa de metro d’una ciutat amb dues etiquetes a cada aresta ('linia' i 'temps'). Cada línia de metro està pintada d’un color diferent. El valor mostrat al costat de cada aresta és el temps que es triga a anar d’una parada a l’altra (en segons).

Suggeriment

Al fitxer crea.py disposeu de la funció crea_graf(), que retorna un graf com el de l’exemple. Descarregueu-lo, que us anirà bé per a fer les proves. A més a més, els doctests el fan servir.

1.1. Funció assignar_temps (2 punts)

Al mòdul metro3 (fitxer metro3.py), implementeu-hi la funció següent:

metro3.assignar_temps(g, noml, segons)

Paràmetres:

• g (networkx.Graph) – Graf que representa la xarxa de metro d’una ciutat

• noml (str) – Nom d’una línia de metro de g

• segons (int) – Temps que es triga entre les estacions de la línia, en segons

Modifica el graf g assignant a totes les arestes de la línia de metro de nom noml el valor segons a l’etiqueta 'temps'

Per exemple, si g és el graf de l’exemple de més amunt, aquesta funció ha de respondre així:

>>> from metro3 import assignar_temps
>>> from crea import crea_graf
>>> g = crea_graf()  # Crea el graf de l'exemple

>>> assignar_temps(g, 'L1', 150)
>>> l1 = ['Port', 'Centre', 'Galeries', 'Parc', 'Placeta', 'Muntanya']
>>> for i in range(len(l1)-1):
...     a, b = l1[i], l1[i+1]
...     print(a, b, g[a][b])
Port Centre {'linia': 'L1', 'temps': 150}
Centre Galeries {'linia': 'L1', 'temps': 150}
Galeries Parc {'linia': 'L1', 'temps': 150}
Parc Placeta {'linia': 'L1', 'temps': 150}
Placeta Muntanya {'linia': 'L1', 'temps': 150}

Disposeu de més jocs de proves al fitxer tests-temps.txt.

1.2. Funció parada_mes_llunyana (1.5 punts)

Donada una parada de metro, volem saber quina és la parada de metro més apartada en temps d’ella, és a dir, aquella altra parada a la qual trigarem més a arribar prenent el camí més ràpid possible. Al mateix mòdul metro3 (fitxer metro3.py), implementeu-hi la funció següent:

metro3.parada_mes_llunyana(g, np)

Paràmetres:

• g (networkx.Graph) – Graf que representa la xarxa de metro d’una ciutat

• np (str) – Nom d’una parada de metro

Retorna:

Tupla amb dues components: nom de la parada més apartada de np i quants segons es triga a arribar-hi (en el millor dels casos). Si hi hagués dues o més parades igualment apartades, la funció retorna el nom de qualsevol d’elles.

Per exemple, si g és el graf de l’exemple de més amunt, aquesta funció ha de respondre així:

>>> from metro3 import parada_mes_llunyana
>>> from crea import crea_graf
>>> g = crea_graf()  # Crea el graf de l'exemple

>>> parada_mes_llunyana(g, 'Centre') # 530 = 40 + 120 + 80 + 290
('Universitat', 530)
>>> parada_mes_llunyana(g, 'Muntanya') # 715 = 110 + 100 + 90 + 80 + 115 + 220
('Raval', 715)

Suggeriment

Es recomana fer servir la funció shortest_path_length(). Fixeu-vos en els diferents valors opcionals dels paràmetres de què disposa, en concret que pot tenir en compte el valor d’un atribut per a calcular la longitud dels camins.

Disposeu de més jocs de proves al fitxer tests-llunyana.txt.