.. py:module:: serveis_socials Serveis socials =============== Un departament de serveis socials d'una administració realitza diversos serveis domiciliaris a persones dependents. Disposa d'un :py:class:`~networkx.Graph` no dirigit i complet on els nodes indiquen el nom de la persona (string) i tenen dos `atributs de node de networkx `_, un atribut anomenat :py:attr:`'servei'` que és un string indicant el tipus de servei que requereix la persona i un altre atribut anomenat :py:attr:`'temps'` que és un enter que indica el temps (minuts) que cal per dur a terme el servei. Les arestes també tenen un `atribut d'aresta de networkx `_, anomenat :py:attr:`'temps'` que és també un enter i que indica el temps (minuts) de desplaçament entre els dos nodes. En el mòdul :mod:`serveis_socials` (fitxer :file:`serveis_socials.py`), implementeu les funcions següents: .. function:: crea_graf(nomf) Retorna un graf de serveis socials a partir de la informació del fitxer `nomf`. Aquest fitxer conté una primera línia amb un enter que indica el nombre de nodes del graf. A continuació hi ha una línia per cada node amb tres dades: el nom de la persona (string), el servei que requereix (string) i el temps en minuts necessari per fer el servei (enter), separats per una coma i un espai, ``', '``. Després hi ha una línia per cada aresta del graf també amb tres dades: el nom de dues persones ( strings) i el temps en minuts (enter) pel desplaçament entre els domicilis d'aquestes dues persones, separats per una coma i un espai, ``', '``. Com exemple d'aquest tipus de fitxer, disposeu del fitxer :download:`exemple_graf_serveis.txt` que permet crear un graf de serveis amb 10 nodes i 45 arestes. Exemple: .. literalinclude:: test-serveis_socials.txt :language: python :lines: 7-40 Si analitzem el fitxer :download:`exemple_graf_serveis.txt` i el graf generat podem observar que en els nodes hi ha tres tipus de servei: `toaleta`, `passeig` i `dinar`. La figura següent mostra un subgraf del graf de l'exemple anterior amb els nodes corresponents a dos dels serveis (6 nodes i 15 arestes): .. image:: graf_serveis.svg :align: center Algunes de les persones que fan el treball social estan especialitzades en un determinat tipus de servei i també demanen poder indicar per quina persona dependent volen començar i per quina volen acabar. Aquest fet ha portat a definir el problema següent: Es parteix d'un graf de serveis socials com l'indicat, d'un determinat tipus de servei i de les dues persones dependents per les que es vol començar i acabar, respectivament. El que es vol obtenir és un camí que passi per totes les persones dependents que requereixen aquest tipus de servei, que comenci i acabi per les dues persones dependents indicades, i que, de tots els camins que compleixen aquests dos requeriments, sigui el que tingui un cost de desplaçament mínim. Un cop es trobi aquest camí també es vol saber el temps total necessari per dur a terme tots els serveis del camí i els desplaçaments. La figura següent mostra el subgraf del graf de l'exemple anterior corresponent al servei ``'toaleta'``: .. image:: graf_serveis_toaleta.svg :align: center Per aquest tipus de servei i suposant que els nodes inicial i final del camí fossin ``'Anna'`` i ``'Cisco'``, respectivament, el camí que requereix menys desplaçaments és: ``['Anna', 'Carme', 'Joan', 'Cisco']`` i el temps total és de 391 minuts resultants de sumar el temps dels serveis (270 minuts) i el temps dels desplaçaments (121 minuts). Com que és un problema d'una certa complexitat, l'hem desglossat en diversos subproblemes que resoldrem a continuació. .. function:: subgraf_serveis_tipus(g, tipus) Retorna un subgraf del graf de serveis socials `g` amb el subconjunt de nodes de `g` que són del `tipus` indicat. Exemple: .. literalinclude:: test-serveis_socials.txt :language: python :lines: 45-50 En aquest exemple s'obté el subgraf vist a la figura anterior, corresponent al servei `toaleta`. .. function:: temps_serveis(g) Retorna un enter corresponent a la suma dels temps (minuts) de tots els serveis (nodes) del graf de serveis socials `g`. Exemple: .. literalinclude:: test-serveis_socials.txt :language: python :lines: 67-70 En aquests exemples `g` és el graf inicial i `sg1` és el subgraf corresponent al servei `toaleta`. .. function:: temps_despl_cami(g, cami) Retorna un enter corresponent a la suma dels temps (minuts) de les arestes de `cami`: un camí (llista de nodes) d'un graf de serveis socials. Exemple: .. literalinclude:: test-serveis_socials.txt :language: python :lines: 79-80 .. function:: cami_mes_rapid(g, n1, n2) Retorna el camí (llista de nodes) que passa per tots els nodes de `g`, que parteix del node `n1` i acaba en el node `n2` del graf `g`, i que, de tots els possibles camins d'aquestes característiques, és el que necessita un temps mínim de desplaçaments. També retorna aquest temps mínim (minuts, enter). Aquesta funció ha de cridar la funció anterior :py:func:`temps_despl_cami`. Exemple: .. literalinclude:: test-serveis_socials.txt :language: python :lines: 91-92 .. function:: serveis(g, tipus, n1, n2) Retorna un camí (llista de nodes) del subgraf `sg` del graf `g` amb el subconjunt de nodes de `g` que són del `tipus` indicat. Aquest camí ha de passar per tots els nodes de `sg`, començar pel node `n1` i acabar en el node `n2` i, de tots els possibles camins d'aquestes característiques, és el que necessita un temps mínim de desplaçaments. Aquesta funció també retorna el temps total (minuts, enter) corresponent a la suma del temps dels desplaçaments d'aquest camí més el temps necessari per dur a terme tots els serveis del camí. Aquesta funció ha de cridar les funcions anteriors :py:func:`subgraf_serveis_tipus`, :py:func:`temps_serveis` i :py:func:`cami_mes_rapid`. Exemple: .. literalinclude:: test-serveis_socials.txt :language: python :lines: 103-107 .. note:: Disposeu de més jocs de proves al fitxer :download:`test-serveis_socials.txt` i d'una solució al fitxer :download:`serveis_socials.py`