Enviament de correus electrònics¶
El departament de comunicació d’una empresa multinacional vol analitzar com circula la informació a través dels correus electrònics entre els seus clients. Per això, es defineix el concepte de multi-digraf de comunicació: un graf dirigit que permet tenir més d’una aresta entre dos nodes. En aquest multi-digraf, els nodes són els noms dels clients de l’empresa i les arestes entre dos nodes s’estableixen quan el client origen de l’aresta ha enviat un e-mail al client destí. És un multi-digraf perquè una persona pot enviar més d’un e-mail a una altra i per tant poden existir múltiples arestes entre nodes.
Cada e-mail té un codi identificatiu únic que es genera quan es crea
i s’envia per primer cop. Aquest codi es manté quan l”e-mail es
reenvia. D’aquesta manera es pot seguir la distribució d’un missatge a
través de la xarxa de clients. A tot e-mail també hi consta l’hora i
els minuts en els que s’ha enviat. Aquesta informació es pot extreure
dels missatges [1]. Les arestes del multi-digraf tenen tres
atributs: codi, hora i minut. Per
simplificar, en aquest problema, suposarem que el seguiment dels
e-mails es fa durant un dia de manera que només caldrà guardar
l’hora i minuts d’enviament en els atributs corresponents.
Vegeu un exemple de multi-digraf de comunicació a la figura adjunta. A la figura no es mostren els nom de les tres etiquetes, només els valors. S’han enviat 3 missatges diferents, de codis “A4R”, “B7K” i “C6J”. El missatge “A4R” l’ha enviat per primer cop Lopez a Perez i a Chen. Perez l’ha reenviat a Chen i a Pons, Pons a Riad i finalment, Riad li ha reenviat a Lopez. Jones ha creat el missatge “B7K” i l’ha enviat a Rull que l’ha reenviat a Tort i, finalment Tort l’ha enviat a Pons i aquest a Riad. El tercer missatge no ha tingut gaire recorregut: l’ha enviat Rull a Tort i prou. Observeu que entre Pons i Riad, i entre Rull i Tort, hi ha dues arestes corresponents a dos e-mails diferents. Es tracta efectivament d’un multi-digraf.
Les consultes que es mostren a continuació s’han aplicat sobre el
multi-digraf de comunicació g representat a la figura. Observeu que
les arestes ('Rull', Tort') i ('Pons', 'Riad') hi apareixen
dos cops. Vegeu també com es consulta el valor de l’etiqueta de les
arestes entre dos nodes.
>>> sorted(g.edges())
[('Jones', 'Rull'), ('Lopez', 'Chen'), ('Lopez', 'Perez'), ('Perez', 'Chen'), ('Perez', 'Pons'), ('Pons', 'Riad'), ('Pons', 'Riad'), ('Riad', 'Lopez'), ('Rull', 'Tort'), ('Rull', 'Tort'), ('Tort', 'Pons')]
>>> for i in sorted(g['Pons']['Riad']): # Escriu els valors dels atributs 'codi', 'hora' i 'minut' de totes les areste entre 'Pons' i 'Riad'
... print(g['Pons']['Riad'][i]['codi'], g['Pons']['Riad'][i]['hora'], g['Pons']['Riad'][i]['minut'])
...
A4R 18 23
B7K 17 23
Deseu les funcions següents al fitxer graf.py. En tots els casos suposeu que els noms del clients són vàlids diferents de “”.
Dissenyeu la funció següent:
- graf.afegir_aresta(g, origen, destí, codi, hora, minut)¶
Afegeix una nova aresta entre els nodes origen i destí al multidigraf g que tindrà els atributs
codi,horaiminutamb els valors dels paràmetres codi, hora i minut corresponents.
Per exemple:
>>> import graf >>> import networkx as nx >>> g = nx.MultiDiGraph() >>> graf.afegir_aresta(g, 'A', 'B', 'A-B', 8, 20) >>> g['A']['B'][0]['codi'] 'A-B' >>> g['A']['B'][0]['hora'] 8 >>> g['A']['B'][0]['minut'] 20 >>> graf.afegir_aresta(g, 'A', 'B', 'A-B', 9, 27) >>> g['A']['B'][1]['codi'] 'A-B' >>> g['A']['B'][1]['hora'] 9 >>> g['A']['B'][1]['minut'] 27
Dissenyeu la funció crear_MultiDiGraf.
- graf.crear_MultiDiGraf(clients, missatges)¶
Retorna un multi-digraf de comunicació amb clients com a nodes i missatges com a arestes.
El paràmetre clients és una llista de noms dels clients de l’empresa i missatges és una llista de tuples (client_emissor, client_receptor, codi_missatge, hora, minuts).
Per exemple:
>>> nodes = ['Lopez', 'Perez', 'Rull', 'Tort', 'Chen', 'Pons','Riad', 'Jones'] >>> arestes = [('Lopez', 'Perez', 'A4R', 12, 5), ('Lopez', 'Chen', 'A4R', 12, 7), ('Perez', 'Chen', 'A4R', 12, 6), ('Perez', 'Pons', 'A4R', 13, 23), ('Pons', 'Riad', 'A4R', 18, 23) , ('Riad', 'Lopez', 'A4R', 18, 30) , ('Jones', 'Rull', 'B7K', 9, 45) , ('Rull', 'Tort', 'B7K', 10, 45), ( 'Tort', 'Pons', 'B7K', 11, 52), ('Pons', 'Riad', 'B7K', 17, 23), ('Rull', 'Tort', 'C6J', 9, 7)] >>> g = graf.crear_MultiDiGraf(nodes, arestes) >>> sorted(g.degree) [('Chen', 2), ('Jones', 1), ('Lopez', 3), ('Perez', 3), ('Pons', 4), ('Riad', 3), ('Rull', 3), ('Tort', 3)]
Dissenyeu la funció filtrar_MultiDiGraf.
- graf.filtrar_MultiDiGraf(g)¶
Retorna la llista dels noms dels clients (nodes del multi-digraf de comunicació g) que reben més e-mails que no pas n’envien. La llista ha d’estar ordenada lexicogràficament.
Per exemple:
>>> graf.filtrar_MultiDiGraf(g) ['Chen', 'Riad', 'Tort']
Recordeu que a la documentació de networkx hi podeu trobar funcions que retornen el grau d’entrada i de sortida dels nodes d’un multi-digraf.
Dissenyeu la funció primer_enviament.
- graf.primer_enviament(g, client, codi)¶
Retorna una tupla formada per un booleà, dos enters i un string.
El booleà tindrà per valor
Truesi en el multi-digraf de comunicació g, el client ha enviat un missatge amb el codi donat, iFalseen cas contrari.Els dos enters seran l’hora i minut del primer enviament d’aquest missatge, per part d’aquest client (0 i 0 si el client no ha enviat cap missatge amb aquest codi).
L”string serà el nom del receptor del missatge amb aquest codi (l”string buit si no hi ha tal missatge).
Per exemple:
>>> e = graf.primer_enviament(g, 'Jones', 'A4R') >>> e[0] False >>> graf.primer_enviament(g, 'Jones', 'B7K') (True, 9, 45, 'Rull') >>> graf.primer_enviament(g, 'Lopez', 'A4R') (True, 12, 5, 'Perez') >>> graf.primer_enviament(g, 'Perez', 'A4R') (True, 12, 6, 'Chen')
Dissenyeu la funció primera_recepcio.
- graf.primera_recepcio(g, client, codi)¶
Retorna una tupla formada per un booleà, dos enters i un string.
El booleà tindrà per valor
Truesi en el multi-digraf de comunicació g, el client ha rebut un missatge amb el codi donat, iFalseen cas contrari.Els dos enters seran l’hora i minut de la primera recepció d’aquest missatge, per part d’aquest client (0 i 0 si el client no ha rebut cap missatge amb aquest codi).
L”string serà el nom de l’emissor del missatge amb aquest codi (l”string buit si no hi ha tal missatge).
Per exemple:
>>> graf.primera_recepcio(g, 'Lopez', 'A4R') (True, 18, 30, 'Riad')
Dissenyeu la funció origen_missatge.
- graf.origen_missatge(g, client, codi)¶
Retorna
Truesi el client ha estat l’iniciador del missatge codi en el multi-digraf de comunicació g iFalsealtrament.
Per exemple:
>>> graf.origen_missatge(g, 'Lopez', 'A4R') True >>> graf.origen_missatge(g, 'Perez', 'A4R') False >>> graf.origen_missatge(g, 'Jones', 'B7K') True
Tingueu en compte que per saber si un client és l’iniciador d’un missatge, cal comprovar que el client hagi enviat el missatge i que, si l’ha tornat a rebre, sempre ha estat en hores posteriors al seu primer enviament.
Dissenyeu la funció recorregut_MultiDiGraf.
- graf.recorregut_MultiDiGraf(g, client)¶
Retorna la llista amb el conjunt de destinataris a qui el client donat ha enviat e-mails, directa o indirectament, és a dir, a través d’altres persones, en el multi-digraf de comunicació g. Cal que la llista retornada estigui ordenada per ordre lexicogràfic.
Per exemple:
>>> graf.recorregut_MultiDiGraf(g, 'Jones') ['Chen', 'Lopez', 'Perez', 'Pons', 'Riad', 'Rull', 'Tort'] >>> graf.recorregut_MultiDiGraf(g, 'Rull') ['Chen', 'Lopez', 'Perez', 'Pons', 'Riad', 'Tort'] >>> graf.recorregut_MultiDiGraf(g, 'Pons') ['Chen', 'Lopez', 'Perez', 'Riad'] >>> graf.recorregut_MultiDiGraf(g, 'Perez') ['Chen', 'Lopez', 'Pons', 'Riad'] >>> graf.recorregut_MultiDiGraf(g, 'Chen') []
Per implementar aquesta funció es recomana utilitzar
descendants().Dissenyeu la funció recorregut_missatge_MultiDiGraf.
- graf.recorregut_missatge_MultiDiGraf(g, emissor, codi)¶
Retorna la llista dels clients que han rebut el missatge codi del que emissor és el primer emissor en el multi-digraf g. Aquesta llista ha d’estar ordenada per ordre lexicogràfic. Podem suposar que emissor és el primer emissor del missatge codi.
Per exemple:
>>> graf.recorregut_missatge_MultiDiGraf(g, 'Lopez', 'A4R') ['Chen', 'Perez', 'Pons', 'Riad'] >>> graf.recorregut_missatge_MultiDiGraf(g, 'Jones', 'B7K') ['Pons', 'Riad', 'Rull', 'Tort'] >>> graf.recorregut_missatge_MultiDiGraf(g, 'Rull', 'C6J') ['Tort']
Una primera estratègia per resoldre aquest problema és utilitzar
descendants()i després quedar-se amb els clients que han rebut el missatge de codi donat.Una segona estratègia és crear un nou graf que contingui només les arestes amb el codi de missatge donat. Sobre aquest nou graf podeu calcular el resultat cridant a la funció recorregut_MultiDiGraf.
