Línies de metro

Volem utilitzar un graf per a representar la xarxa de metro d’una ciutat. La xarxa metropolitana està organitzada en línies de metro que s’aturen en diverses parades. Tant les línies com les parades tenen un nom que la identifica (per exemple, la parada 'Verdaguer' o la línia 'L5'). Assumirem que totes les línies són de doble sentit de circulació, que no hi ha dues línies de metro que comparteixin un mateix trajecte entre dues estacions i que en totes les parades per les quals hi passa més d’una línia de metro els viatgers poden fer transbordament de l’una a l’altra.

En conseqüència, hem triat de representar la xarxa de línies de metro mitjançant un graf no dirigit de networkx en el qual els nodes són les parades i les arestes estan etiquetades amb un atribut 'linia', corresponent al nom de la línia entre les dues parades.

Per exemple, el metro de Barcelona quedaria representat amb aquest graf:

../../../_images/Metrobcn.svg

Deseu totes les funcions d’aquest exercici en el mòdul de nom metro.py.

  1. Dissenyeu la funció modificadora següent:

    metro.afegir_linia(g, noml, lparades)

    Donat un graf que representa una xarxa de metro, el nom de línia i una llista de parades, afegeix a g la línia de nom noml que recorre les parades de lparades en l’ordre en que apareixen a la llista. A més a més d’afegir-hi els nodes i arestes adients, cal que totes les arestes entre parades de la línia quedin etiquetades amb la línia (tinguin assignat l’string noml com a l’atribut 'linia'):

    >>> import networkx as nx

>>> from metro import afegir_linia
>>> g = nx.Graph()
>>> afegir_linia(g, 'A1', ['Rotonda', 'Mercat', 'Barri vell'])
>>> g.has_edge('Barri vell', 'Mercat') and g.has_edge('Rotonda', 'Mercat')
True
>>> g['Rotonda']['Mercat']['linia']
'A1'
>>> g['Mercat']['Barri vell']['linia']
'A1'

  2. Dissenyeu la funció següent:

    metro.crea_xarxa_metro(nomf)

    Donat un nom d’un fitxer que conté la descripció de totes les línies de metro d’una ciutat en aquest format, crea i retorna el graf corresponent a la xarxa metropolitana descrita en el fitxer. Per exemple, amb el fitxer metrobcn.txt, la funció ha de retornar un graf com el de la figura anterior.

    >>> from metro import crea_xarxa_metro
>>> mb = crea_xarxa_metro('metrobcn.txt')
>>> mb.number_of_nodes()
118
>>> mb.number_of_edges()
133

    Cal que la funció crea_xarxa_metro() cridi la funció modificadora afegir_linia().

  3. Utilitzeu les utilitats de matplotlib.pyplot per a dibuixar el graf de la xarxa metropolitana de Barcelona. Si voleu que les estacions quedin situades al mapa amb una distribució semblant a la de la figura, necessitareu un diccionari de posicions com el que trobareu aquí.

  4. Dissenyeu la funció següent:

    metro.cjt_parades(g, linia)

    Donat un graf que representa una xarxa de metro, i el nom d’una línia (string), retorna el conjunt de parades per on passa la línia.

    Per exemple, essent mb el graf del metro de Barcelona generat a partir del fitxer metrobcn.txt, aquesta funció hauria de respondre així:

    >>> from metro import cjt_parades
>>> cjt_parades(mb, 'FM') == set(['Parc de Montjuic', 'Paral.lel'])
True
>>> cjt_parades(mb, 'L3') == set(['Sants Estacio', 'Les Corts', 'Lesseps', 'Liceu', 'Vallcarca', "Vall d'Hebron", 'Mundet', 'Paral.lel', 'Diagonal', 'Penitents', 'Tarragona', 'Passeig de Gracia', 'Poble Sec', 'Drassanes', 'Fontana', 'Placa del Centre', 'Espanya', 'Canyelles', 'Roquetes', 'Catalunya', 'Palau Reial', 'Montbau', 'Zona Universitaria', 'Trinitat Nova', 'Maria Cristina', 'Valldaura'])
True

  5. Dissenyeu la funció següent:

    metro.cjt_linies(g, parada)

    Donat un graf que representa una xarxa de metro i una parada, retorna el conjunt de línies que passen per la parada.

    Per exemple, essent mb el graf del metro de Barcelona generat a partir del fitxer metrobcn.txt, aquesta funció hauria de respondre així:

    >>> from metro import cjt_linies
>>> cjt_linies(mb, 'Montbau') == set(['L3'])
True
>>> cjt_linies(mb, 'Passeig de Gracia') == set(['L4', 'L2', 'L3'])
True
>>> cjt_linies(mb, 'Placa de Sants') == set(['L5', 'L1'])
True

  6. Dissenyeu la funció següent:

    metro.recorregut(g, pini, pfi)

    Donat un graf que representa una xarxa de metro, un parada inicial i una parada final, retorna una llista de parades corresponent al camí més curt, en nombre de parades, per anar amb metro de pini a pfi. En el cas que hi hagi més d’un camí mínim, la funció retorna qualsevol dels més curts. Si no és possible d’anar des de pini a pfi, la llista retornada és buida.

    Per exemple, essent mb el graf del metro de Barcelona generat a partir del fitxer metrobcn.txt, aquesta funció hauria de respondre així:

    >>> from metro import recorregut
>>> recorregut(mb, 'Valldaura', 'Fontana')
['Valldaura', 'Mundet', 'Montbau', "Vall d'Hebron", 'Penitents', 'Vallcarca', 'Lesseps', 'Fontana']
>>> recorregut(mb, 'Girona','Clot')
['Girona', 'Verdaguer', 'Sagrada Familia', 'Encants', 'Clot']
>>> r = recorregut(mb, 'La Pau', 'Espanya')
>>> len(r)
13

  7. Dissenyeu la funció següent:

    metro.llista_parades(g, linia)

    Donat un graf que representa una xarxa de metro i una línia, retorna la llista de les parades per on passa la línia, ordenades segons el seu recorregut. Fixeu-vos que si considerem el subgraf de g tal que només conté les arestes etiquetades amb linia, totes les parades d’aquest subgraf tenen dos veïns excepte la parada inicial i final, que només en tenen un. Doncs bé, la primera parada de la llista retornada ha de ser, de les dues possibles (inicial o final), la que és més petita segons l’ordre lexicogràfic.

    Per exemple, essent mb el graf del metro de Barcelona generat a partir del fitxer metrobcn.txt, aquesta funció hauria de respondre així:

    >>> from metro import llista_parades
>>> llista_parades(mb, 'FM')
['Paral.lel', 'Parc de Montjuic']
>>> llista_parades(mb, 'L11')
['Can Cuias', 'Ciutat Meridiana', 'Torre Baro / Vallbona', "Casa de l'Aigua", 'Trinitat Nova']
>>> llista_parades(mb, 'L4')
['La Pau', 'Besos', 'Besos Mar', 'El Maresme / Forum', 'Selva de Mar', 'Poblenou', 'Llacuna', 'Bogatell', 'Ciutadella / Vila Olimpica', 'Barceloneta', 'Jaume I', 'Urquinaona', 'Passeig de Gracia', 'Girona', 'Verdaguer', 'Joanic', 'Alfons X', 'Guinardo / Hospital de Sant Pau', 'Maragall', 'Llucmajor', 'Via Julia', 'Trinitat Nova']

Nota

Disposeu de jocs de prova al fitxer metro.txt i d’una solució a metro.py.