1. Grafs: Sistema fluvial (4 Punts)

../../../../_images/concaAmazones.png

Representarem un sistema fluvial, és a dir, un conjunt de rius més els seus afluents, com un graf dirigit de networkx (un DiGraph). En aquest graf, els nodes són els noms dels rius i una aresta indica que un riu és afluent d’un altre. La direcció de l’aresta va de l’afluent, que és més petit, al riu al qual desemboca, que és més gran, tal com es mostra al dibuix.

Un riu que aporta les seves aigües, directa o indirectament, a les d’un altre se l’anomena tributari. Per exemple, els rius Jari, Juruena, i Arinos són tributaris de l’Amazones.

../../../../_images/rius.svg

En el següent exemple, el graf gr representa una petita part del sitema fluvial dels rius Amazones i Orinoco, el que està dibuixat més amunt:

>>> import networkx as nx

>>> lrius = [ ['Jari', 'Amazones'], ['Xingú', 'Amazones'], ['Iriri', 'Xingú'],
...  ['Paru', 'Amazones'], ['Tapajós', 'Amazones'], ['Teles Pires', 'Tapajós'],
...  ['Juruena', 'Tapajós'], ['Arinos', 'Juruena'], 
...  ['Guaviare', 'Orinoco'], ['Inírida', 'Guaviare'], ['Arauca', 'Orinoco'] ]
>>> gr = nx.DiGraph()
>>> gr.add_edges_from(lrius)

1.1. Funció confluencia

Al mòdul rius (fitxer rius.py), implementeu-hi la funció següent:

rius.confluencia(gr, n1, n2)
Paràmetres:

  • gr – graf de NetworkX que representa un sistema fluvial.

  • n1 – nom d’un riu de gr.

  • n2 – nom d’un altre riu de gr.

Retorna:

Un enter que valdrà: 1 si el riu n1 és afluent de n2; 2 si el riu n1 és tributari de n2 però no hi desemboca directament; 0 en qualsevol altre cas.

Per exemple, si gr és el graf de més amunt, aquesta funció ha de respondre així:


>>> confluencia(gr, 'Jari', 'Amazones')
1
>>> confluencia(gr, 'Iriri', 'Amazones')
2
>>> confluencia(gr, 'Amazones', 'Tapajós')
0
>>> confluencia(gr, 'Tapajós', 'Arinos')
0
>>> confluencia(gr, 'Xingú', 'Paru')
0

Disposeu de més jocs de proves al fitxer tests-confluencia.txt.

1.2. Funció recorregut

Al mateix mòdul rius (fitxer rius.py), implementeu-hi la funció següent:

rius.recorregut(gr, nriu)
Paràmetres:

  • gr – graf de NetworkX que representa un sistema fluvial.

  • nriu – nom d’un riu.

Retorna:

Llista ordenada de noms de rius que cal seguir per arribar des de nriu fins al riu principal que desemboca al mar. O sigui, en aquesta llista cada riu és afluent del següent riu de la llista, i el darrer nom de la llista és el riu principal, que no és afluent de cap altre.

Per exemple, si gr és el graf de més amunt, aquesta funció ha de respondre així:


>>> recorregut(gr, 'Arinos')
['Arinos', 'Juruena', 'Tapajós', 'Amazones']
>>> recorregut(gr, 'Paru')
['Paru', 'Amazones']
>>> recorregut(gr, 'Orinoco')
['Orinoco']

Disposeu de més jocs de proves al fitxer tests-recorregut.txt.