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:

../../../../_images/metro-temps1.svg

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ó parada_mes_propera (2 punts)

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

metro4.parada_mes_propera(g, np)
Paràmetres:

  • g (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 propera en temps de np i segons que es triga per anar-hi. Si la parada més propera no és única, 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 metro4 import parada_mes_propera
>>> from crea import crea_graf
>>> g = crea_graf()  # Crea el graf de l'exemple

>>> parada_mes_propera(g, 'Centre')
('Ajuntament', 40)
>>> parada_mes_propera(g, 'Universitat')
('Aeroport', 270)

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

1.2. Funció nombre_de_transbordaments (1.5 punts)

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

metro4.nombre_de_transbordaments(g, p1, p2)
Paràmetres:

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

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

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

Retorna:

Nombre de transbordaments que cal fer per anar des de p1 fins a p2 seguint el trajecte més ràpid en temps. Si el camí més ràpid no és únic, retorna el nombre de transbordaments de qualsevol d’ells.

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


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

>>> nombre_de_transbordaments(g, 'Ronda', 'Universitat')
0
>>> nombre_de_transbordaments(g, 'Ajuntament', 'Galeries')
1
>>> nombre_de_transbordaments(g, 'Muntanya', 'Mercat')
2

Suggeriment

Es recomana fer servir les funcions de camins mínims de networkx (networkx.algorithms.shortest_paths.generic). Fixeu-vos en els diferents valors opcionals dels paràmetres de què disposen, en concret que poden 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-transbordaments.txt.