Enviament de correus electrònics ================================ .. py:module:: graf 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 [#n1]_. Les arestes del multi-digraf tenen tres :term:`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. .. image:: relacions.svg :align: center :height: 500 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. .. literalinclude:: graf.txt :language: python :lines: 29-35 Deseu les funcions següents al fitxer :file:`graf.py`. En tots els casos suposeu que els noms del clients són vàlids diferents de ''. #. Dissenyeu la funció següent: .. py:function:: 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``, ``hora`` i ``minut`` amb els valors dels paràmetres *codi*, *hora* i *minut* corresponents. Per exemple: .. literalinclude:: graf.txt :language: python :lines: 1-19 #. Dissenyeu la funció *crear_MultiDiGraf*. .. py:function:: 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: .. literalinclude:: graf.txt :language: python :lines: 22-26 #. Dissenyeu la funció *filtrar_MultiDiGraf*. .. py:function:: 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: .. literalinclude:: graf.txt :language: python :lines: 38-39 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*. .. py:function:: primer_enviament(g, client, codi) Retorna una tupla formada per un booleà, dos enters i un *string*. El booleà tindrà per valor ``True`` si en el multi-digraf de comunicació *g*, el *client* ha enviat un missatge amb el *codi* donat, i ``False`` en 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: .. literalinclude:: graf.txt :language: python :lines: 41-49 #. Dissenyeu la funció *primera_recepcio*. .. py:function:: primera_recepcio(g, client, codi) Retorna una tupla formada per un booleà, dos enters i un *string*. El booleà tindrà per valor ``True`` si en el multi-digraf de comunicació *g*, el *client* ha rebut un missatge amb el *codi* donat, i ``False`` en 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: .. literalinclude:: graf.txt :language: python :lines: 51-52 #. Dissenyeu la funció *origen_missatge*. .. py:function:: origen_missatge(g, client, codi) Retorna ``True`` si el *client* ha estat l'iniciador del missatge *codi* en el multi-digraf de comunicació *g* i ``False`` altrament. Per exemple: .. literalinclude:: graf.txt :language: python :lines: 54-59 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*. .. py:function:: 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: .. literalinclude:: graf.txt :language: python :lines: 61-70 Per implementar aquesta funció es recomana utilitzar :py:func:`~networkx.algorithms.dag.descendants`. #. Dissenyeu la funció *recorregut_missatge_MultiDiGraf*. .. py:function:: 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: .. literalinclude:: graf.txt :language: python :lines: 72-77 Una primera estratègia per resoldre aquest problema és utilitzar :py:func:`~networkx.algorithms.dag.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*. .. note:: Disposeu de jocs de prova al fitxer :download:`graf.txt` i d'una solució al fitxer :download:`graf.py`. .. [#n1] Vegeu `formats de missatges `_.