Graf d’un laberint

Estem fent un videojoc en el qual hi ha un laberint rectangular, amb un determinat nombre de files i columnes, i hem decidit representar-lo mitjançant un graf no orientat de networkx. En aquest graf, els nodes són tuples amb les dues coordenades de les posicions del laberint i hi haurà una aresta entre dos nodes només si són consecutius (és a dir, si els nodes estan l’un al costat de l’altre o l’un sobre l’altre) i no hi ha una paret que els separi. La figura següent mostra un exemple d’un laberint de 3 files i 5 columnes (a l’esquerra) i el seu graf corresponent (al centre):

Deseu totes les funcions d’aquest exercici en el mòdul glaber.py

1. Dissenyeu la funció següent:

   glaber.crea_graf_laberint(nf, nc)

   Donat un nombre de files i de columnes, crea i retorna un graf de networkx que representa un laberint de les dimensions donades, sense cap paret. Els nodes del graf han de ser tuples amb les dues coordenades de posició del laberint, des de la (1,1) fins la (nf, nc). Com que el laberint retornat no tindrà cap paret, tots els nodes consecutis del graf estaran units per una aresta:

   
   >>> g1 = crea_graf_laberint(4, 2)
   >>> sorted(g1.nodes())
   [(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2), (4, 1), (4, 2)]
   >>> sorted(map(sorted, g1.edges))
   [[(1, 1), (1, 2)], [(1, 1), (2, 1)], [(1, 2), (2, 2)], [(2, 1), (2, 2)], [(2, 1), (3, 1)], [(2, 2), (3, 2)], [(3, 1), (3, 2)], [(3, 1), (4, 1)], [(3, 2), (4, 2)], [(4, 1), (4, 2)]]
   >>> g = crea_graf_laberint(3, 5)
   >>> list(g.nodes)
   [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5)]
   >>> len(g.edges())
   22
   
   

2. Dissenyeu la funció:

   glaber.afegir_paret(g, a, b)

   Donat el graf d’un laberint, g, i dos nodes del graf, a i b, que han de ser consecutius, modifica el graf de manera que no es pugui anar entre els dos nodes donats. És a dir, aquesta funció elimina l’aresta entre els dos nodes del graf, si és que hi era:

   
   # continua amb el graf g del doctest anterior
   
   >>> afegir_paret(g, (1,1), (2,1))
   >>> len(g.edges())
   21
   >>> afegir_paret(g, (1,2), (2,2))
   >>> afegir_paret(g, (2,3), (2,2))
   >>> afegir_paret(g, (2,2), (3,2))
   >>> afegir_paret(g, (2,4), (1,4))
   >>> afegir_paret(g, (2,4), (3,4))
   >>> afegir_paret(g, (2,5), (3,5))
   
   # ara hauria de quedar el laberint com en l'exemple:
   >>> sorted(map(sorted,g.edges))
   [[(1, 1), (1, 2)], [(1, 2), (1, 3)], [(1, 3), (1, 4)], [(1, 3), (2, 3)], [(1, 4), (1, 5)], [(1, 5), (2, 5)], [(2, 1), (2, 2)], [(2, 1), (3, 1)], [(2, 3), (2, 4)], [(2, 3), (3, 3)], [(2, 4), (2, 5)], [(3, 1), (3, 2)], [(3, 2), (3, 3)], [(3, 3), (3, 4)], [(3, 4), (3, 5)]]
   
   
   

3. Dissenyeu la funció:

   glaber.quants_camins(g, a, b)

   Donat el graf d’un laberint, g, i dues posicions del laberint, a i b (dos nodes del graf), retorna quantes maneres diferents hi ha d’anar de a a b per dins del laberint, és a dir, el nombre de camins possibles per anar de a a b. Fixeu-vos que aquest nombre pot ser zero si no hi ha cap manera d’anar de a a b. Per exemple, sent g el graf de la figura anterior,

   
   >>> quants_camins(g, (1,1), (1,3))
   1
   >>> quants_camins(g, (1,2), (2,5))
   2
   >>> quants_camins(g, (1,1), (2,2))
   2
   >>> g.add_edge((1,2), (2,2))
   >>> quants_camins(g, (1,1), (2,2))
   3
   >>> quants_camins(g, (1,5), (2,1))
   4
   >>> g.remove_edge((1,2), (2,2))
   
   
   

4. Tot seguit, volem que en el videojoc hi hagi parelles de nodes que permetin teletransportar-se de l’un a l’altre, encara que en el laberint no siguin posicions consecutives. Això ho representarem mitjançant una aresta entre els dos nodes del graf entre els quals es pot fer el teletransport tal que tindrà l’atribut tipus amb el valor “teletransport”. Per exemple, en l’anterior dibuix, la figura de la dreta mostra el mateix laberint que el de l’esquerra al qual s’ha afegit una aresta de teletransport entre els nodes (3,1) i (2,5).

   Dissenyeu la funció:

   glaber.afegir_teletransport(g, a, b)

   Donat el graf d’un laberint, g, i dos nodes, a i b, afegeix una aresta de teletransport entre a i b. Podeu suposar que a i b no són nodes consecutius. Per exemple, sent g el graf de la figura anterior,

   
   >>> afegir_teletransport(g, (3,1), (2,5))
   >>> g[(3,1)][(2,5)]
   {'tipus': 'teletransport'}
   >>> g[(1,1)][(1,2)]
   {}
   >>> afegir_teletransport(g, (2,2), (3,5))
   >>> g[(2,2)][(3,5)]
   {'tipus': 'teletransport'}
   >>> afegir_teletransport(g, (2,3), (8,8))
   >>> g[(2,3)][(8,8)]
   {'tipus': 'teletransport'}
   
   
   

5. Dissenyeu la funció:

   glaber.millor_cami(g, a, b)

   Donat el graf d’un laberint, g, i dos nodes, a i b, retorna l’string:

   • 'IMPOSSIBLE' si en el laberint no es pot anar de a a b;

   • 'NORMAL' si el camí més curt per anar de a a b no inclou una aresta de teletransport;

   • 'TELETRANSPORT' si el camí més curt per anar de a a b passa per una o més arestes de teletransport.

   Si el camí més curt no és únic i un d’ells inclou una aresta de teletransport i l’altre no, és indiferent si aquesta funció retorna 'NORMAL' o 'TELETRANSPORT'.

   Per exemple, sent g el graf de la figura anterior,

   
   >>> millor_cami(g, (1,1), (1,2))
   'NORMAL'
   >>> millor_cami(g, (2,2), (2,4))
   'TELETRANSPORT'
   >>> millor_cami(g, (1,1), (8,8))
   'TELETRANSPORT'
   >>> millor_cami(g, (1,1), (1,5))
   'NORMAL'
   >>> g.add_nodes_from([(1,6), (2,6), (2,7)])
   >>> millor_cami(g, (1,1), (1,6))
   'IMPOSSIBLE'
   >>> millor_cami(g, (8,8), (2,6))
   'IMPOSSIBLE'
   

6. Feu una segona versió de la funció anterior tal que si entre els dos nodes donats el camí més curt no és únic, i algun d’aquests camins no inclou una aresta de teletransport, retorni 'NORMAL'.

Nota

Disposeu de jocs de proves al fitxer testgraflaber.txt.

Solució

Disposeu d’una solució al fitxer glaber.py.