.. py:module:: castell

Les habitacions del castell
===========================

L'objectiu d'aquest exercici és treballar amb l'estructura de dades
Graf. Treballarem amb grafs no dirigits. Per això utilitzarem les classes
i els mètodes que trobareu a la llibreria de grafs
:ref:`NetworkX <networkx:contents>`.

Dissenyeu el mòdul :py:mod:`castell` que contingui les funcions que
es detallen tot seguit. Utilitzeu la biblioteca
`matplotlib <https://matplotlib.org/>`__ per a pintar els
grafs a fi de comprovar que el que fan les diferents funcions és
correcte. Les funcions que s'implementaran donaran informació sobre les
habitacions que hi ha en un castell i els accessos entre aquestes.

Deseu les funcions següents al fitxer :file:`castell.py`.

#. Dissenyeu la funció següent:

   .. py:function:: habitacions(lnoms, laccessos)

      A partir de la llista `lnoms` (que conté els noms de les
      habitacions del castell) i de la llista de parelles d'habitacions
      consecutives `laccessos`, és a dir que hi ha una porta entre les
      dues habitacions de la parella, retorna una instància d'un graf
      simètric o no dirigit que representi les habitacions del castell i
      els accessos d'unes a les altres. Per exemple:
   
      .. literalinclude:: castell-1.txt
         :language: python
         :lines: 1-
   	      
   .. note:: Disposeu de jocs de prova al fitxer :download:`castell-1.txt<castell-1.txt>`
	  
#. Dissenyeu la funció següent:

   .. py:function:: hab_veina(hcastell, habitacio)

      Retorna una llista amb els noms de les habitacions del graf
      *hcastell* que són veïnes de l'*habitacio* donada (string). Cal que
      la llista de noms d'habitacions retornada estigui ordenada
      lexicogràficament. Per exemple:
   
      .. literalinclude:: castell-2.txt
         :language: python
         :lines: 6-
   	      
   .. note:: Disposeu de jocs de prova al fitxer :download:`castell-2.txt<castell-2.txt>`

#. Dissenyeu la funció següent:

   .. py:function:: hi_puc_anar(hcastell, hab1, hab2)

      Retorna una tupla formada per un booleà i un enter.
   
      El booleà tindrà per valor ``True`` si podem anar de la primera
      habitació *hab1* a la segona *hab2* i ``False`` en cas contrari, en
      el castell representat pel graf *hcastell*.
   
      L'enter, en cas que es pugui anar d'una habitació a l'altra, serà el
      nombre d'habitacions per les que hem de passar, sense comptar la
      primera habitació. En el cas que no s'hi pugui anar, l'enter serà
      zero.
   
      Per exemple:
   
      .. literalinclude:: castell-3.txt
         :language: python
         :lines: 6-20
   
   Per implementar aquesta funció, podeu usar la funció:
   :py:func:`~networkx.algorithms.shortest_paths.generic.shortest_path_length`
       
   .. note:: Disposeu de jocs de prova al fitxer :download:`castell-3.txt<castell-3.txt>`
	  
#. Dissenyeu la funció següent:

   .. py:function:: subcastells(hcastell)

      Retorna el nombre de subcastells independents que es poden crear a
      partir del castell *hcastell*. Les habitacions de cada subcastell
      estan totes comunicades però, en canvi, no es pot anar des de cap
      habitació d'un subcastell a cap habitació d'un altre
      subcastell. Per exemple:
   
      .. literalinclude:: castell-4.txt
         :language: python
         :lines: 1-11
   	      
   Per implementar aquesta funció, podeu usar la funció:
   :py:func:`~networkx.algorithms.components.number_connected_components`
	      
   .. note:: Disposeu de jocs de prova al fitxer :download:`castell-4.txt<castell-4.txt>`

#. Dissenyeu la funció següent:

   .. py:function:: per_on_passem(hcastell, habitacio)

      Retorna un subgraf de *hcastell* amb aquelles habitacions de
      *hcastell* a les quals es pot arribar a partir d'*habitacio*
      
      .. literalinclude:: castell-5.txt
         :language: python
         :lines: 1-15
   	      
   Per implementar aquesta funció, podeu usar la funció:
   :py:func:`~networkx.algorithms.components.node_connected_component`
	      
   .. note:: Disposeu de jocs de prova al fitxer :download:`castell-5.txt<castell-5.txt>`

.. note:: Disposeu de més jocs de prova per totes les funcions al fitxer :download:`castell.txt <castell.txt>`.
	  
.. rubric:: Solució
	       
Disposeu d'una solució a :download:`castell.py <solucio/castell.py>`.