Exercici 1: Grafs (5 punts)

En un joc de rol, hem representat les diferents zones de l'escenari i la forma com estan connectades mitjançant un graf (no dirigit): les zones són els nodes graf, i una aresta des de `a` fins a `b` indica que els jugadors poden anar de la zona `a` a la zona `b`. Per exemple, la següent figura representa un escenari amb vuit zones:

Es demana que, al mòdul ex1.py, escriviu la funció cami_indirecte(g, a, b, c) que, donat un graf de networkx que representa l'escenari d'un joc, i tres nodes (strings), retorni el camí més curt per anar des de a fins a b passant per c. El camí retornat ha de ser una llista de nodes. Si hi ha més d'un camí possible igual de curt, tant és el camí que es retorni. Si un dels nodes no és del graf o bé el camí demanat és impossible, la funció ha de retornar la llista buida.

Per exemple,

>>> import ex1
>>> import networkx as nx

>>> g = nx.Graph()
>>> g.add_nodes_from(['taberna','poble','cova','platja','vaixell','prat','bosc','muntanya'])
>>> g.add_edges_from([ ('poble','taberna'), ('poble','bosc'), ('bosc','muntanya'), ('poble','prat'), ('poble','platja'), ('platja','vaixell'), ('platja','cova'), ('platja','prat') ])

>>> ex1.cami_indirecte(g, 'muntanya', 'cova', 'taberna')
['muntanya', 'bosc', 'poble', 'taberna', 'poble', 'platja', 'cova']

>>> ex1.cami_indirecte(g, 'poble', 'cova', 'ajuntament')
[]

El fitxer test1.txt conté d'altres jocs de proves.

Exercici 2: Grafs (5 punts)

Al graf que representa l'escenari d'un joc de rol de l'exercici anterior hi volem afegir informació per a saber com es passa d'una zona a l'altra (amb una carretera, un pont, una porta, etc). Per això hem afegit un atribut a les arestes, de nom connexio. Ara, el graf de l'exemple anterior podria quedar així:

Es demana que, al mòdul ex2.py, escriviu la funció zones_carretera(q) que, donat un graf com el descrit, retorni el conjunt de zones del joc que estan connectades amb una carretera amb algun altre node. El valor retornat ha de ser un set de Python. Per exemple,

>>> import ex2
>>> import networkx as nx

>>> g = nx.Graph()
>>> g.add_nodes_from(['taberna','poble','cova','platja','vaixell','prat','bosc','muntanya'])
>>> g.add_path(['muntanya', 'bosc', 'prat'], connexio='carretera')
>>> g.add_path(['poble', 'prat', 'platja'], connexio='camí')
>>> g.add_path(['poble', 'platja'], connexio='carretera')
>>> g.add_edge('poble', 'taberna', connexio='porta')
>>> g.add_edge('poble', 'bosc', connexio='pont')
>>> g.add_edge('platja', 'cova', connexio='roques')
>>> g.add_edge('platja', 'vaixell', connexio='barca')

>>> ex2.zones_carretera(g) == {'bosc', 'platja', 'prat', 'muntanya', 'poble'}
True