Amistats ======== .. py:module:: amistats Una aplicació habitual dels grafs és la representació de `xarxes socials `__ de relació entre persones. L'objectiu d'aquest exercici és treballar amb l'estructura de dades graf sobre una representació simplificada d'una xarxa social. Representarem una xarxa social com un graf en què els nodes seran persones i les arestes relacions d'amistat entre aquestes. Anomenarem aquestes estructures de dades **grafs d'amistats**. Quan hi hagi una aresta entre dos nodes del graf direm que les dues persones corresponents tenen una relació d'amistat **directa**. Si dues persones no tenen una relació d'amistat directa però tenen amics a través dels quals és possible relacionar-les, direm que tenen una amistat **indirecta**. .. "en el què" substituït per "en què" seguint les recomanacions de: http://aplicacions.llengua.gencat.cat/llc/AppJava/index.html?action=Principal&method=detall&input_cercar=en+el+que&numPagina=1&database=FITXES_PUB&idFont=10695&idHit=10695&tipusFont=Fitxes+de+l%27Optimot&numeroResultat=8&databases_avansada=&categories_avansada=&clickLink=detall&titol=oracions+de+relatiu+adjectives+%2F+relatiu+locatiu%3A+en+el+qu%E8%2C+on%2C+en+qu%E8+o+en+el+qual%3F+%2F+lloc+a+qu%E8+o+lloc+en+qu%E8%3F%2C+lloc+al+qual+o+lloc+en+el+qual%3F%2C+lloc+a+on+o+lloc+on%3F&tematica=&tipusCerca=cerca.tot Per implementar la pràctica, utilitzarem les classes i els mètodes de la llibreria de grafs :ref:`networkx `. En concret, un graf d'amistats el representarem com una instància d'un :py:class:`~networkx.Graph` de networkx. Deseu les funcions d'aquest exercici al mòdul :file:`amistats.py`. Utilitzeu la biblioteca `matplotlib `__ per a pintar els grafs a fi de comprovar que el que fan les diferents funcions és correcte. #. Dissenyeu la funció següent: .. py:function:: relacions (ls, lt) A partir d'una llista de *strings* (corresponents als noms de les persones d'un grup), *ls* i d'una llista de tuples, *lt*, de parelles de persones del grup que tenen una relació directa d'amistat, retorna un graf d'amistats (:py:class:`~networkx.Graph`). .. literalinclude:: test-amistats.txt :language: python :lines: 1-8 Vegeu :doc:`el tutorial de networkx ` si teniu dubtes sobre com crear un graf, afegir-hi nodes o afegir-hi arestes. #. Dissenyeu la funció següent: .. py:function:: amistats_directes(grup, persona) Donat un graf d'amistats *grup* i un *string* *persona*, corresponent al nom d'una persona del grup, retorna una llista amb totes les persones que tenen una amistat directa amb la donada. Cal que la llista estigui ordenada alfabèticament. .. literalinclude:: test-amistats.txt :language: python :lines: 9-14 Per a resoldre aquest apartat n'hi ha prou amb fer servir les :doc:`funcions bàsiques de consulta de networkx ` per accedir als veïns d'un node. #. Dissenyeu la funció següent: .. py:function:: son_amistat(grup, p1, p2) Donat un graf d'amistats *grup* i dos *strings* *p1* i *p2* corresponents al nom de dues persones del grup, retorna una tupla formada per un booleà i un enter. El booleà serà *True* si hi ha una amistat directa o indirecta entre les dues persones. En aquest cas, l'enter retornat serà el nombre mínim de persones per les que hem de passar per anar d'amistat en amistat de *p1* a *p2*, sense incloure ni *p1* ni *p2*. Si les dues persones no tenen cap amistat en comú directa o indirectament, la funció ha de retornar *False* i el valor *None* en lloc de l'enter. .. literalinclude:: test-amistats.txt :language: python :lines: 15-22 Per a resoldre aquest apartat es recomana utilitzar les funcions de :doc:`camins mínims `. #. Dissenyeu la funció següent: .. py:function:: nombre_grups(g) Donat un graf d'amistats, *g*, retorna el nombre de grups independents de persones, és a dir, el nombre de grups tals que no hi ha cap relació entre una persona d'un grup i una persona d'un altre grup. .. literalinclude:: test-amistats.txt :language: python :lines: 23-24 Per a resoldre aquest apartat es recomana utilitzar les funcions de :doc:`components connexes `. #. Dissenyeu la funció següent: .. py:function:: solitaries(g) Donat un graf d'amistats, *g*, retorna la llista ordenada alfabèticament de persones que no estan relacionades amb ningú. .. literalinclude:: test-amistats.txt :language: python :lines: 25-26 Per a resoldre aquest apartat es recomana utilitzar les funcions de :doc:`nodes aïllats `. #. Dissenyeu la funció següent: .. py:function:: amistats_totals(g, persona) Donada una instància d'un graf d'amistats, *g*, i un *string* que representa una persona, *persona*, retorna una llista ordenada alfabèticament de totes les persones del grup que són amistats directa o indirecta de la persona. La llista no ha d'incloure la pròpia persona. .. literalinclude:: test-amistats.txt :language: python :lines: 27-38 .. note:: Disposeu de jocs de prova al fitxer :download:`test-amistats.txt`, d'una solució a :download:`amistats.py` i d'un fitxer de comandes per a dibuixar el graf d'amistats de l'exemple a :download:`dibuixaamistats.txt`.