Serveis socials

Un departament de serveis socials d’una administració realitza diversos serveis domiciliaris a persones dependents. Disposa d’un 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 'servei' que és un string indicant el tipus de servei que requereix la persona i un altre atribut anomenat '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 'temps' que és també un enter i que indica el temps (minuts) de desplaçament entre els dos nodes.

En el mòdul serveis_socials (fitxer serveis_socials.py), implementeu les funcions següents:

serveis_socials.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 exemple_graf_serveis.txt que permet crear un graf de serveis amb 10 nodes i 45 arestes.

Exemple:

>>> nomf = 'exemple_graf_serveis.txt'
>>> gs = crea_graf(nomf)
>>> gs.order()
10
>>> gs.size()
45

>>> gs.nodes['Anna']['servei']
'toaleta'
>>> gs.nodes['Anna']['temps']
60
>>> ddata = [('Anna', {'servei': 'toaleta', 'temps': 60}),
...          ('Joan', {'servei': 'toaleta', 'temps': 60}),
...          ('Cisco', {'servei': 'toaleta', 'temps': 75}),
...          ('Carme', {'servei': 'toaleta', 'temps': 75}),
...          ('Pere', {'servei': 'passeig', 'temps': 85}),
...          ('Quima', {'servei': 'passeig', 'temps': 45}),
...          ('Pau', {'servei': 'dinar', 'temps': 75}),
...          ('Julia', {'servei': 'dinar', 'temps': 75}),
...          ('Gloria', {'servei': 'dinar', 'temps': 120}),
...          ('Maria', {'servei': 'dinar', 'temps': 120})]
>>> list(gs.nodes(data = True)) == ddata
True

>>> gs['Anna']['Joan']['temps']
53
>>> gs['Anna']['Maria']['temps']
40
>>> gs['Joan']['Cisco']['temps']
34
>>> gs['Joan']['Gloria']['temps']
42
>>> gs['Gloria']['Maria']['temps']
44

Si analitzem el fitxer 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):

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':

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

serveis_socials.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:

>>> sg1 = subgraf_serveis_tipus(gs, 'toaleta')
>>> sgn1 = set(sg1.nodes())
>>> if sgn1 != {'Joan', 'Cisco', 'Anna', 'Carme'}:
...     print(sgn1)
>>> sg1.size()
6

En aquest exemple s’obté el subgraf vist a la figura anterior, corresponent al servei toaleta.

serveis_socials.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:

>>> temps_serveis(gs)
790
>>> temps_serveis(sg1)
270

En aquests exemples g és el graf inicial i sg1 és el subgraf corresponent al servei toaleta.

serveis_socials.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:

>>> temps_despl_cami(sg1, ['Anna', 'Carme', 'Joan', 'Cisco'])
121

serveis_socials.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 temps_despl_cami().

Exemple:

>>> cami_mes_rapid(sg1, 'Anna', 'Cisco')
(['Anna', 'Carme', 'Joan', 'Cisco'], 121)

serveis_socials.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 subgraf_serveis_tipus(), temps_serveis() i cami_mes_rapid().

Exemple:

>>> serveis(gs, 'toaleta', 'Anna', 'Cisco')
(['Anna', 'Carme', 'Joan', 'Cisco'], 391)

>>> serveis(gs, 'dinar', 'Pau', 'Julia')
(['Pau', 'Gloria', 'Maria', 'Julia'], 518)

Nota

Disposeu de més jocs de proves al fitxer test-serveis_socials.txt i d’una solució al fitxer serveis_socials.py