| 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 |
Es representen les línies d'una companyia de autobusos com un MultiDiGraph dirigit networkx. Els nodes representen les ciutats en les que té parada una línia de la xarxa de bus. Cada aresta correspon a un trajecte entre dues ciutats i està etiquetada amb l'atribut linia que és un string format per un codi que identifica la línia.
Vegeu, per exemple el MultiDiGraph dirigit següent,
el qual representa tres línies de bus, codificades per AL, BS i PR respectivament. Observeu que entre dues ciutats hi pot haver més d'una aresta, ja que hi poden haver dues línies que vagin des d'una ciutat a l'altra. El MultiDiGraph anterior ha estat creat amb la seqüència d'operacions en Python,
>>> import networkx as nx
>>> g=nx.MultiDiGraph()
>>> l=['Barcelona', 'Cervera', 'Esparraguera', 'Igualada', 'Tarrega']
>>> g.add_edge('Barcelona', 'Igualada', linia='AL')
>>> g.add_edge('Igualada', 'Cervera', linia='AL')
>>> g.add_edge('Cervera', 'Tarrega', linia='AL')
>>> g.add_edge('Tarrega', 'Igualada', linia='BS')
>>> g.add_edge ('Igualada', 'Esparraguera', linia='BS')
>>> g.add_edge('Esparraguera', 'Barcelona', linia='BS')
>>> g.add_edge('Tarrega', 'Igualada', linia='PR')
Dissenyeu la funció una_linia(xarxa, linia), que donat un MultiDiGraph de les línies de bus com el descrit, i donat un string que representa l'identificador de la línia, retorna un DiGraph que té com a nodes totes les poblacions per les que passa la línia i com arestes els trajectes de la línia. Les arestes del DiGraph no han d'estar etiquetades.
Vegeu per exemple:
>>> import ex1
>>> t=ex1.una_linia(g, 'BS')
>>> l=t.edges()
>>> l.sort()
>>> l
[('Esparraguera', 'Barcelona'), ('Igualada', 'Esparraguera'), ('Tarrega', 'Igualada')]
>>> a=t.nodes()
>>> a.sort()
>>> a
['Barcelona', 'Esparraguera', 'Igualada', 'Tarrega']
>>> t=ex1.una_linia(g, 'AL')
>>> a=t.nodes()
>>> a.sort()
>>> a
['Barcelona', 'Cervera', 'Igualada', 'Tarrega']
Deseu la funció al fitxer ex1.py.
Dissenyeu la funció parades(digraf, origen, desti), que donat un DiGraph d'una línia de bus, donats dos strings corresponents a una població d'origen i una de destí, retorni el nombre mínim de parades que haurem de fer per anar de la població d'origen a la de destí i la llista de parades, sense incloure la d'origen ni la de destí. En cas que no hi hagi camí, la funció ha de retornar -1 i la llista buida.
Vegeu per exemple:
>>> import networkx as nx
>>> g=nx.DiGraph()
>>> g.add_edge('Barcelona', 'Igualada')
>>> g.add_edge('Igualada', 'Cervera')
>>> g.add_edge('Cervera', 'Tarrega')
>>> import ex2 >>> ex2.parades(g, 'Barcelona', 'Cervera') (1, ['Igualada']) >>> ex2.parades(g, 'Barcelona', 'Tarrega') (2, ['Igualada', 'Cervera']) >>> ex2.parades(g, 'Barcelona', 'Cerveraaa') (-1, [])
Per resoldre aquest problema recomanem que llegiu detingudament la documentació de camins mínims de networkx
Deseu la funció al fitxer ex2.py.