Línies de metro
===============

.. py:module:: metro

.. toctree::
   :hidden:

   diccionari_de_posicions_de_les_estacions_de_Barcelona
   format_dels_fitxer_d_entrada


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 :ref:`networkx <networkx:contents>`
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:

.. image:: Metrobcn.svg
   :align: center
   :height: 800

Deseu totes les funcions d'aquest exercici en el mòdul de nom :file:`metro.py`.

#. Dissenyeu la funció **modificadora** següent:

   .. py:function:: 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'``):

   .. literalinclude:: metro.txt
      :language: python
      :lines: 1-11

#. Dissenyeu la funció següent:

   .. py:function:: crea_xarxa_metro(nomf)

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

   .. literalinclude:: metro.txt
      :language: python
      :lines: 15-20

   Cal que la funció :py:func:`crea_xarxa_metro` cridi la funció
   modificadora :py:func:`afegir_linia`.

#. Utilitzeu les :ref:`utilitats de matplotlib.pyplot <drawing>` 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 :doc:`el que trobareu aquí
   <diccionari_de_posicions_de_les_estacions_de_Barcelona>`.

#. Dissenyeu la funció següent:

   .. py:function:: 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 :download:`metrobcn.txt`, aquesta funció hauria de
   respondre així:

   .. literalinclude:: metro.txt
      :language: python
      :lines: 22-26

#. Dissenyeu la funció següent:

   .. py:function:: 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 :download:`metrobcn.txt`, aquesta funció hauria de
   respondre així:

   .. literalinclude:: metro.txt
      :language: python
      :lines: 28-34

#. Dissenyeu la funció següent:

   .. py:function:: 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 :download:`metrobcn.txt`, aquesta funció hauria
   de respondre així:

   .. literalinclude:: metro.txt
      :language: python
      :lines: 36-43

#. Dissenyeu la funció següent:

   .. py:function:: 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 :download:`metrobcn.txt`, aquesta funció hauria
   de respondre així:

   .. literalinclude:: metro.txt
      :language: python
      :lines: 45-51

.. note::

   Disposeu de jocs de prova al fitxer :download:`metro.txt` i d'una solució a   :download:`metro.py <solucio/metro.py>`.