3. Grafs: Encara més linies de metro (2 punts)

En aquest problema treballarem amb un graf que representa la xarxa de metro d’una ciutat , que ja coneixeu.

L’entitat que gestiona el metro vol saber quin és el trajecte alternatiu més curt entre dues parades consecutives d’una línia en el cas que hi hagi una avaria entre aquestes dues parades.

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

mes_metro.trajecte_alternatiu(g, p1, p2)
Paràmetres:

  • g – graf de NetworkX que representa una xarxa de línies metro

  • p1 – nom d’una parada de metro

  • p2 – nom d’una segona parada de metro, unida amb p1 per una aresta.

Retorna:

Llista de parades amb el trajecte alternatiu més curt, en nombre de parades, en el cas que el tram que va de p1 fins a p2 hagi sofert una avaria. Si no existeix aquest trajecte alternatiu, la funció ha de retornar la llista buida. La llista retonada ha d’estar ordenada en l’ordre del trajecte. En el cas que hi hagi més d’un camí alternatiu d’igual llargada, la funció retornarà qualsevol d’ells.

Tingueu en compte que després de cridar a aquesta funció el graf ha de quedar de la mateixa manera que abans de cridar-se, perquè és una operació de consulta.

Per exemple, si g és el graf de les línies de metro de Barcelona, el de l’exemple de l’enunciat original del problema, aquesta funció ha de respondre així:


>>> from mes_metro import trajecte_alternatiu
>>> trajecte_alternatiu(g, 'Clot', 'Navas')
['Clot', 'Encants', 'Sagrada Familia', 'Sant Pau / Dos de Maig', "Camp de l'Arpa", 'La Sagrera', 'Navas']
>>> trajecte_alternatiu(g, 'Les Corts', 'Maria Cristina')
[]
>>> trajecte_alternatiu(g, 'Llucmajor', 'Via Julia')
['Llucmajor', 'Maragall', 'Virrei Amat', 'Vilapicina', 'Horta', 'El Carmel', 'El Coll / La Teixonera', "Vall d'Hebron", 'Montbau', 'Mundet', 'Valldaura', 'Canyelles', 'Roquetes', 'Trinitat Nova', 'Via Julia']

Per fer proves, podeu utilitzar la funció crea_xarxa_metro() que està al mòdul creametrobcn (fitxer creametrobcn.py). Aquesta funció utilitza el fitxer metrobcn.txt. Descarregueu els fitxers creametrobcn.py i metrobcn.txt, però no el pugeu a la tasca (pugeu només mes_metro.py). NO feu import d’aquest mòdul dins del vostre codi. Tampoc podeu importar mòduls amb solucions d’altres exercicis de la col.lecció.

Disposeu de més jocs de proves al fitxer tests-trajectealternatiu.txt que utilitza tant la funció creametrobcn.py com el fitxer metrobcn.txt.