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.

Per implementar la pràctica, utilitzarem les classes i els mètodes de la llibreria de grafs networkx. En concret, un graf d’amistats el representarem com una instància d’un Graph de networkx.

Deseu les funcions d’aquest exercici al mòdul amistats.py. Utilitzeu la biblioteca matplotlib per a pintar els grafs a fi de comprovar que el que fan les diferents funcions és correcte.

  1. Dissenyeu la funció següent:

    amistats.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 (Graph).

    >>> import amistats
>>> l = ['pere', 'andreu', 'laia', 'ernest', 'jordina', 'angela', 'marga', 'nuria', 'laura', 'eric', 'sarah', 'robert', 'lluis', 'albert', 'loli']
>>> r = [('pere', 'andreu'), ('sarah', 'lluis'), ('sarah', 'eric'), ('sarah', 'albert'), ('sarah', 'laia'), ('sarah', 'marga'), ('sarah', 'laura'), ('laura', 'nuria'), ('laura', 'eric'), ('laura', 'ernest'), ('angela', 'robert'), ('eric', 'robert'), ('robert', 'loli')]
>>> g = amistats.relacions(l, r)
>>> sorted(g.nodes)
['albert', 'andreu', 'angela', 'eric', 'ernest', 'jordina', 'laia', 'laura', 'lluis', 'loli', 'marga', 'nuria', 'pere', 'robert', 'sarah']
>>> sorted(g.edges)
[('angela', 'robert'), ('eric', 'robert'), ('eric', 'sarah'), ('ernest', 'laura'), ('laia', 'sarah'), ('laura', 'eric'), ('laura', 'sarah'), ('marga', 'sarah'), ('nuria', 'laura'), ('pere', 'andreu'), ('robert', 'loli'), ('sarah', 'albert'), ('sarah', 'lluis')]

    Vegeu el tutorial de networkx si teniu dubtes sobre com crear un graf, afegir-hi nodes o afegir-hi arestes.

  2. Dissenyeu la funció següent:

    amistats.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.

    >>> amistats.amistats_directes(g, 'angela')
['robert']
>>> amistats.amistats_directes(g, 'eric')
['laura', 'robert', 'sarah']
>>> amistats.amistats_directes(g, 'laura')
['eric', 'ernest', 'nuria', 'sarah']

    Per a resoldre aquest apartat n’hi ha prou amb fer servir les funcions bàsiques de consulta de networkx per accedir als veïns d’un node.

  3. Dissenyeu la funció següent:

    amistats.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.

    >>> amistats.son_amistat(g, 'sarah', 'eric')
(True, 0)
>>> amistats.son_amistat(g, 'sarah', 'pere')
(False, None)
>>> amistats.son_amistat(g, 'sarah', 'robert')
(True, 1)
>>> amistats.son_amistat(g, 'sarah', 'loli')
(True, 2)

    Per a resoldre aquest apartat es recomana utilitzar les funcions de camins mínims.

  4. Dissenyeu la funció següent:

    amistats.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.

    >>> amistats.nombre_grups(g)
3

    Per a resoldre aquest apartat es recomana utilitzar les funcions de components connexes.

  5. Dissenyeu la funció següent:

    amistats.solitaries(g)

    Donat un graf d’amistats, g, retorna la llista ordenada alfabèticament de persones que no estan relacionades amb ningú.

    >>> amistats.solitaries(g)
['jordina']

    Per a resoldre aquest apartat es recomana utilitzar les funcions de nodes aïllats.

  6. Dissenyeu la funció següent:

    amistats.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.

    >>> amistats.amistats_totals(g, 'jordina')
[]
>>> amistats.amistats_totals(g, 'pere')
['andreu']
>>> amistats.amistats_totals(g, 'andreu')
['pere']
>>> amistats.amistats_totals(g, 'laura')
['albert', 'angela', 'eric', 'ernest', 'laia', 'lluis', 'loli', 'marga', 'nuria', 'robert', 'sarah']
>>> amistats.amistats_totals(g, 'sarah')
['albert', 'angela', 'eric', 'ernest', 'laia', 'laura', 'lluis', 'loli', 'marga', 'nuria', 'robert']
>>> amistats.amistats_totals(g, 'eric')
['albert', 'angela', 'ernest', 'laia', 'laura', 'lluis', 'loli', 'marga', 'nuria', 'robert', 'sarah']

Nota

Disposeu de jocs de prova al fitxer test-amistats.txt, d’una solució a amistats.py i d’un fitxer de comandes per a dibuixar el graf d’amistats de l’exemple a dibuixaamistats.txt.