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 NetworkX.

Dissenyeu el mòdul castell que contingui les funcions que es detallen tot seguit. Utilitzeu la biblioteca matplotlib 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 castell.py.

1. Dissenyeu la funció següent:

   castell.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:

   >>> import castell  
   
   >>> lhabs = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
   >>> lportes = [(0, 12), (0, 4), (0, 13), (1, 3), (1, 13), (3, 13), (4, 13), (7, 14)]
   >>> c = castell.habitacions(lhabs, lportes)
   >>> list(c.nodes)
   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
   >>> c.number_of_edges()
   8
   >>> c.has_edge(1, 3)
   True
   >>> c.has_edge(3, 4)
   False
   

   Nota

   Disposeu de jocs de prova al fitxer castell-1.txt

2. Dissenyeu la funció següent:

   castell.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:

   >>> castell.hab_veina(c, 0)  
   [4, 12, 13]
   >>> castell.hab_veina(c, 1)  
   [3, 13]
   >>> castell.hab_veina(c, 2)  
   []
   >>> castell.hab_veina(c, 3)  
   [1, 13]
   >>> castell.hab_veina(c, 4)  
   [0, 13]
   >>> castell.hab_veina(c, 5)  
   []
   

   Nota

   Disposeu de jocs de prova al fitxer castell-2.txt

3. Dissenyeu la funció següent:

   castell.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:

   >>> p, q = castell.hi_puc_anar(c, 0, 1)  
   >>> p
   True
   >>> q
   2
   >>> p, q = castell.hi_puc_anar(c, 0, 2)  
   >>> p
   False
   >>> q
   0
   >>> p, q = castell.hi_puc_anar(c, 1, 13)  
   >>> p
   True
   >>> q
   1
   

   Per implementar aquesta funció, podeu usar la funció: shortest_path_length()

   Nota

   Disposeu de jocs de prova al fitxer castell-3.txt

4. Dissenyeu la funció següent:

   castell.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:

   >>> import castell  
   
   >>> lhabs = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
   >>> lportes = [(0, 12), (0, 4), (0, 13), (1, 3), (1, 13), (3, 13), (4, 13), (7, 14)]
   >>> c = castell.habitacions(lhabs, lportes)
   >>> castell.subcastells(c)
   9
   >>> mes_portes = [(5, 6), (6, 9), (6, 10), (7, 8), (11, 2)]
   >>> c.add_edges_from(mes_portes)
   >>> castell.subcastells(c)
   4
   

   Per implementar aquesta funció, podeu usar la funció: number_connected_components()

   Nota

   Disposeu de jocs de prova al fitxer castell-4.txt

5. Dissenyeu la funció següent:

   castell.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

   >>> import castell  
   
   >>> lhabs = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
   >>> lportes = [(0, 12), (0, 4), (0, 13), (1, 3), (1, 13), (3, 13), (4, 13), (7, 14)]
   >>> c = castell.habitacions(lhabs, lportes)
   >>> y = castell.per_on_passem(c, 0)  
   >>> l = list(y.nodes)  
   >>> l.sort()  
   >>> l
   [0, 1, 3, 4, 12, 13]
   >>> y = castell.per_on_passem(c, 7)  
   >>> l = list(y.nodes)  
   >>> l.sort()  
   >>> l
   [7, 14]
   

   Per implementar aquesta funció, podeu usar la funció: node_connected_component()

   Nota

   Disposeu de jocs de prova al fitxer castell-5.txt

Nota

Disposeu de més jocs de prova per totes les funcions al fitxer castell.txt.

Solució

Disposeu d’una solució a castell.py.