Mapa polític

Utilitzarem un Graph per a representar el mapa polític d’un territori, és a dir, la divisió del territori en diferents zones (països, comarques, diòcesis…), identificades pel seu nom. Cada node del graf correspondrà a una zona del graf, i dues zones estaran unides per una aresta sempre que siguin limítrofs, és a dir, quan comparteixin una frontera terrestre. Vegeu-ne un exemple:

Mapa d’un territori fictici dividit en zones i graf corresponent.

Es demana que en el mòdul mapes (fitxer mapes.py), hi implementeu les funcions següents:

mapes.fusiona_zones(gm, z1, z2, z3)

Donat un graf d’un territori gm i el nom de tres zones z1 i z2, modifica el graf de manera que representi el mateix territori on la zona z1 i z2 s’han unificat en una de sola, de nom z3.

Per exemple, amb el territori de la figura, s’han fusionat les zones 'Ashari' i 'Samari' en la nova regió de nom 'Ashamari'.

Disposeu de jocs de proves més complets al fitxer test-fusiona.txt.

mapes.zones_de_pas(gm, za, zb)

Donat un graf d’un territori gm i el nom de dues zones za i zb, retorna el conjunt (un set de Python) de noms de zones de gm tals que s’hagi de passar ineludiblement per anar per terra de la zona za fins a la zb. Si no hi ha cap manera d’anar per terra d’una a l’altra zona, la funció retornarà el conjunt {'IMPOSSIBLE'}. Per exemple, amb el graf del territori de la primera figura, la funció ha de respondre així:

>>> from mapes import zones_de_pas
>>> zones_de_pas(g, 'Besnak', 'Loweh')
{'Miland'}
>>> zones_de_pas(g, 'Krko', 'Filite')
{'IMPOSSIBLE'}
>>> zones_de_pas(g, 'Ashari', 'Miland')
set()

Disposeu de jocs de proves al fitxer test-zones.txt i d’una solució al fitxer mapes.py.