El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Aplicacions dels Grafs

Següent ►
►

Ja tenim tota la teoria del mòdul: recorreguts (07-03), camins mínims (07-04) i arbres d'expansió (07-05). Aquesta lliçó no introdueix ni un algorisme nou: els posa a treballar en aplicacions completes i recognoscibles. Primer, el plat fort: el planificador de TaskFlow, que combina ordre topològic, detecció de cicles, paral·lelització per nivells i el càlcul de la ruta crítica del projecte. Després sortirem de TaskFlow per veure dos clàssics: el suggeriment de col·laboradors d'una xarxa social (amics-d'amics amb BFS) i un PageRank en miniatura, l'algorisme que va fer enlairar Google. Tanquem amb un panorama dels grafs en producció. Tot el codi corre sobre la classe Graf de la 07-02.

Contingut

  1. El planificador de TaskFlow complet
    • Validar: detecció de cicles
    • Ordenar: ordre topològic
    • Paral·lelitzar: tasques per nivells
    • Estimar: la ruta crítica del projecte
  2. Suggeriment de col·laboradors: amics-d'amics
  3. PageRank simplificat
  4. Grafs en producció: panorama breu

El planificador de TaskFlow complet

Partim del graf dependencies i de l'índex tasques de la 07-02 (recorda: cada tasca és un dict amb id, titol, prioritat, estat i hores; l'aresta A → B significa "B depèn d'A"). El planificador ha de respondre, en aquest ordre, quatre preguntes: és executable el projecte?, en quin ordre?, què es pot fer en paral·lel?, quantes hores durarà com a mínim?

Validar: detecció de cicles

Res no té sentit si hi ha un cicle, així que el planificador comença reutilitzant hi_ha_cicle (blanc/gris/negre, 07-03) com a guàrdia d'entrada:

def planificar(graf, tasques):
    if hi_ha_cicle(graf):
        raise ValueError("Dependències circulars: revisa el projecte")
    return {
        "ordre": ordre_topologic(graf),          # 07-03, Kahn
        "nivells": nivells_parallels(graf),      # nou, a sota
        "durada": ruta_critica(graf, tasques),   # nou, a sota
    }

En una aplicació real aquesta validació correria també abans d'acceptar cada nova dependència, que és més barat que deixar que l'error s'acumuli.

Ordenar: ordre topològic

ordre_topologic (Kahn, 07-03) ja ens dóna una seqüència vàlida d'execució per a un sol treballador. Res de nou a afegir — llevat de notar que un ordre en sèrie desaprofita l'equip: si dissenyar_esquema i dissenyar_ui no depenen entre si, per què esperar-se?

Paral·lelitzar: tasques per nivells

La versió per capes de Kahn agrupa les tasques en nivells: el nivell 0 són les tasques sense dependències; el nivell k, les que queden llestes quan acaben els nivells anteriors. Totes les tasques d'un mateix nivell es poden executar en paral·lel:

from collections import deque

def nivells_parallels(graf):
    graus = graf.graus_entrada()
    nivell_actual = [v for v, g in graus.items() if g == 0]
    nivells = []
    while nivell_actual:
        nivells.append(nivell_actual)
        seguent = []
        for v in nivell_actual:                # "acabem" tot el nivell alhora
            for vei in graf.veins(v):
                graus[vei] -= 1
                if graus[vei] == 0:
                    seguent.append(vei)
        nivell_actual = seguent
    return nivells

for i, nivell in enumerate(nivells_parallels(dependencies)):
    print(f"Nivell {i}: {nivell}")
# Nivell 0: ['dissenyar_esquema', 'configurar_servidor', 'dissenyar_ui']
# Nivell 1: ['migrar_bd', 'implementar_ui']
# Nivell 2: ['desplegar_api']
# Nivell 3: ['proves_integracio']
# Nivell 4: ['llancament']

És el mateix Kahn de la 07-03, però processant la cua per tandes en lloc d'element a element — compara-ho amb el recorregut per nivells del mòdul 6, que feia exactament aquesta maniobra sobre arbres. Lectura de gestió: amb prou gent, el projecte necessita 5 tandes; tres persones poden arrencar el dilluns alhora.

Estimar: la ruta crítica del projecte

Pregunta final: amb paral·lelisme il·limitat, quantes hores com a mínim dura el projecte? No és la suma de totes les hores (hi ha paral·lel), ni el camí mínim de la 07-04. És el camí més llarg del DAG comptant les hores de cada tasca: la ruta crítica. Qualsevol retard en ella endarrereix el projecte sencer; les altres tasques tenen marge.

Camí més llarg? Sona a invertir Dijkstra (negar pesos... només vàlid sense cicles), però en un DAG hi ha una via més neta i sense trampes: ordre topològic + programació dinàmica. Recorrent les tasques en ordre topològic, quan arribem a una tasca ja coneixem el moment de fi de totes les seves dependències, així que:

fi(v) = hores(v) + max(fi(u) per a cada dependencia u de v; 0 si no en te)
def ruta_critica(graf, tasques):
    fi = {}           # id -> hora de finalitzacio mes primerenca possible
    pare_critic = {}
    for v in ordre_topologic(graf):            # garanteix fi(u) ja calculat
        millor, culpable = 0, None
        for u in graf.vertexs():               # dependències de v: arestes u -> v
            if graf.existeix_aresta(u, v) and fi[u] > millor:
                millor, culpable = fi[u], u
        fi[v] = millor + tasques[v]["hores"]
        pare_critic[v] = culpable              # la dependència que marca el ritme

    ultim = max(fi, key=fi.get)                # la tasca que acaba mes tard
    cami, actual = [], ultim                   # reconstruir cap enrere (07-04)
    while actual is not None:
        cami.append(actual)
        actual = pare_critic[actual]
    return {"hores": fi[ultim], "ruta": cami[::-1]}

print(ruta_critica(dependencies, tasques))
# {'hores': 17,
#  'ruta': ['dissenyar_ui', 'implementar_ui', 'proves_integracio', 'llancament']}

Comprovació a mà dels moments de fi: dissenyar_ui 5 → implementar_ui 5+8=13; per l'altra branca, migrar_bd acaba en 5 i desplegar_api en 7. proves_integracio espera la més lenta: max(13, 7) + 3 = 16, i llancament tanca en 17 hores. La ruta crítica passa per la interfície: accelerar migrar_bd no avançaria el projecte ni un minut (té 6 hores de marge), però cada hora guanyada a implementar_ui és una hora de projecte.

graph LR
    A[dissenyar_esquema 3h] --> B[migrar_bd 2h]
    S[configurar_servidor 1h] --> C
    B --> C[desplegar_api 2h]
    C --> D
    U[dissenyar_ui 5h] ==> I[implementar_ui 8h]
    I ==> D[proves_integracio 3h]
    D ==> L[llancament 1h]
    style U stroke:#c00,stroke-width:3px
    style I stroke:#c00,stroke-width:3px
    style D stroke:#c00,stroke-width:3px
    style L stroke:#c00,stroke-width:3px

Nota d'eficiència: el doble bucle amb existeix_aresta és O(n · a) per claredat didàctica; amb el graf invertit de la 07-03 (exercici 2) quedaria en O(n + a). Amb això, el planificador és complet: validació, ordre, paral·lelisme i estimació en unes 60 línies sobre estructures que ja teníem.

Suggeriment de col·laboradors: amics-d'amics

Canviem de domini. TaskFlow afegeix un toc social: suggerir col·laboradors a cada usuari. L'heurística clàssica de les xarxes socials: suggerir els que són a distància exactament 2 — col·laboradors dels meus col·laboradors que encara no són meus — ordenats per quants contactes comuns tenim. És un BFS limitat a dues capes sobre un graf no dirigit:

def suggerir_collaboradors(graf, usuari, maxim=3):
    directes = set(graf.veins(usuari))                # distància 1
    candidats = {}                                    # candidat -> contactes comuns
    for amic in directes:
        for segon in graf.veins(amic):                # distància 2
            if segon != usuari and segon not in directes:
                candidats[segon] = candidats.get(segon, 0) + 1
    return sorted(candidats, key=candidats.get, reverse=True)[:maxim]

social = Graf(dirigit=False)
for a, b in [("anna", "bruno"), ("anna", "carla"), ("bruno", "david"),
             ("carla", "david"), ("carla", "elena"), ("david", "ferran")]:
    social.afegir_aresta(a, b)

print(suggerir_collaboradors(social, "anna"))   # ['david', 'elena']

A l'anna se li suggereix david abans que elena perquè comparteix amb ell dos contactes (bruno i carla) i amb elena només un. Aquí no va caldre ni la cua: en ser exactament dues capes, dos bucles imbricats són el BFS truncat — però conceptualment és bfs_distancies (exercici 1 de la 07-03) filtrant distància 2. Així funcionen, amb molts refinaments a sobre, els "potser coneixes" de LinkedIn o Facebook.

PageRank simplificat

La web és un graf dirigit (pàgines → enllaços, lliçó 07-01). La pregunta de Google el 1998: quines pàgines són importants? La idea de PageRank: una pàgina és important si l'enllacen pàgines importants — definició circular que es resol per iteració. Model del "navegant aleatori": amb probabilitat d (≈ 0,85) segueix un enllaç a l'atzar de la pàgina actual; amb 1 − d salta a una pàgina qualsevol. El rang d'una pàgina és la fracció de temps que el navegant hi passa:

def pagerank(graf, d=0.85, iteracions=30):
    vertexs = graf.vertexs()
    n = len(vertexs)
    rang = {v: 1 / n for v in vertexs}            # arrencada: tots iguals
    for _ in range(iteracions):
        nou = {v: (1 - d) / n for v in vertexs}       # el salt aleatori
        for v in vertexs:
            sortides = graf.grau_sortida(v)
            if sortides == 0:                     # pagina sense enllacos:
                for desti in vertexs:             # reparteix entre totes
                    nou[desti] += d * rang[v] / n
            else:
                for desti in graf.veins(v):       # reparteix el seu rang
                    nou[desti] += d * rang[v] / sortides
        rang = nou
    return rang

web = Graf(dirigit=True)
for origen, desti in [("blog", "docs"), ("blog", "home"), ("docs", "home"),
                      ("forum", "home"), ("home", "docs")]:
    web.afegir_aresta(origen, desti)

for pagina, r in sorted(pagerank(web).items(), key=lambda x: -x[1]):
    print(f"{pagina}: {r:.3f}")
# home: 0.470
# docs: 0.455
# blog: 0.038
# forum: 0.038

Lectura del codi: a cada iteració, cada pàgina reparteix el seu rang entre els seus enllaços sortints (d * rang / sortides), i totes reben a més l'engruna del salt aleatori ((1 - d) / n). Després d'unes desenes d'iteracions els valors s'estabilitzen (convergeix a un punt fix). home guanya perquè l'enllacen les altres tres; docs la segueix molt de prop amb un únic enllaç entrant, perquè qui l'enllaça és la importantíssima home — aquí hi ha la circularitat resolta: no compta només quants enllaços reps, sinó de qui. blog i forum, sense enllaços entrants, es queden amb l'engruna del salt aleatori. A TaskFlow, la mateixa idea aplicada al graf de dependències invertit assenyalaria les tasques "estructuralment centrals" del projecte.

Grafs en producció: panorama breu

Per acabar, on viuen els grafs en sistemes reals (sense codi, només mapa):

Àmbit Què modela el graf Què s'hi executa a sobre
Bases de dades de grafs (Neo4j, Neptune) Entitats i relacions com a ciutadans de primera Consultes de patrons i camins (Cypher, Gremlin)
Recomanació (Amazon, Netflix, Spotify) Usuaris ↔ productes, bipartit Veïnatge, passejades aleatòries, filtratge col·laboratiu
CI/CD i build (Make, Gradle, Airflow) Passos i les seves dependències: un DAG Ordre topològic i paral·lelització — el nostre planificador, a escala
Mapes i logística Cruïlles i trams ponderats Dijkstra i variants amb heurístiques (A*)
Detecció de frau Comptes, targetes, dispositius compartits Components connexes i patrons sospitosos

La moralitat: el que hem construït aquest mòdul no és un exercici acadèmic; és la versió petita i comprensible de la maquinària que orquestra pipelines, rutes i recomanacions diàriament. Quan l'escala creix, canvien els motors (bases de dades de grafs, processament distribuït), però els conceptes —adjacència, BFS, ordre topològic, camins— són exactament aquests.

Errors Comuns i Consells

  • Confondre ruta crítica amb camí mínim. La ruta crítica és el camí més LLARG del DAG: marca la durada inevitable del projecte. Minimitzar (07-04) i maximitzar (aquí) responen preguntes oposades; la programació dinàmica sobre ordre topològic només és vàlida per maximitzar perquè el DAG no té cicles.
  • Calcular la ruta crítica sense validar abans el DAG. Amb un cicle, ordre_topologic llança una excepció (bé); si fessis servir una altra implementació silenciosa, la programació dinàmica llegiria valors no calculats. Valida sempre primer.
  • Oblidar el cas "sense enllaços sortints" a PageRank. Sense aquest repartiment, el rang dels carrerons sense sortida s'evapora a cada iteració i la suma total deixa de ser 1 — un bug clàssic difícil de notar perquè el rànquing relatiu pot continuar semblant raonable.
  • Suggerir amics amb graf dirigit sense voler. Si construeixes la xarxa social amb dirigit=True (el valor per defecte de la nostra classe), "amics dels meus amics" només mirarà en un sentit. Per a amistats, Graf(dirigit=False) explícit.
  • Consell: fixa't en el patró d'aquesta lliçó: cap aplicació no va necessitar estructures noves, només compondre les existents. Aquesta composició és l'habilitat que distingeix qui "sap algorismes" de qui resol problemes.

Exercicis

Exercici 1: marge d'una tasca

Amplia ruta_critica per calcular el marge de cada tasca: quantes hores pot endarrerir-se sense afectar la durada total. Pista: calcula també l'instant més tardà de fi permès, recorrent l'ordre topològic al revés des de la durada total; marge = tardà − primerenc.

Exercici 2: col·laboradors a distància 3

Generalitza suggerir_collaboradors a collaboradors_a_distancia(graf, usuari, k) fent servir bfs_distancies (exercici 1 de la 07-03) per retornar els usuaris a distància exactament k.

Exercici 3: la tasca més central

Aplica pagerank al graf dependencies invertit (amb invertir de la 07-03) i raona per què la tasca amb major rang és la que és.

Solucions

Solució 1:

def marges(graf, tasques):
    dades = ruta_critica(graf, tasques)
    total = dades["hores"]
    fi = {}
    for v in ordre_topologic(graf):
        previ = max((fi[u] for u in graf.vertexs()
                     if graf.existeix_aresta(u, v)), default=0)
        fi[v] = previ + tasques[v]["hores"]

    tardana = {}
    for v in reversed(ordre_topologic(graf)):     # del final cap al principi
        successors = [tardana[s] - tasques[s]["hores"] for s in graf.veins(v)]
        tardana[v] = min(successors, default=total)  # sense successors: la fi del projecte
    return {v: tardana[v] - fi[v] for v in fi}

print(marges(dependencies, tasques))
# {'dissenyar_esquema': 6, 'configurar_servidor': 10, 'migrar_bd': 6,
#  'desplegar_api': 6, 'dissenyar_ui': 0, 'implementar_ui': 0,
#  'proves_integracio': 0, 'llancament': 0}

Les tasques amb marge 0 són exactament la ruta crítica; configurar_servidor pot endarrerir-se fins a 10 hores sense moure el llançament. Aquesta és l'anàlisi PERT/CPM dels manuals de gestió de projectes, construïda amb les nostres peces.

Solució 2:

def collaboradors_a_distancia(graf, usuari, k):
    distancies = bfs_distancies(graf, usuari)     # 07-03, exercici 1
    return [v for v, d in distancies.items() if d == k]

print(collaboradors_a_distancia(social, "anna", 2))  # ['david', 'elena']
print(collaboradors_a_distancia(social, "anna", 3))  # ['ferran']

Tota la lògica ja era a bfs_distancies: l'aplicació és un filtre d'una línia. (Es perd el desempat per contactes comuns; combinar-ho amb el recompte de la versió original queda com a millora opcional.)

Solució 3: En invertir, les fletxes apunten de cada tasca cap a les seves dependències, així que el rang flueix des del final del projecte cap als seus fonaments. Guanya dissenyar_esquema o configurar_servidor... no: recorrent el flux, el rang s'acumula a les tasques de les quals més es depèn transitivament — amb aquest graf, dissenyar_esquema i dissenyar_ui reben el rang que baixa per les seves cadenes, i la més beneficiada és dissenyar_ui, de la qual penja la branca més pesant (tota la UI i, a través de les proves, el llançament). Executar-ho confirma la intuïció: les tasques "arrel" de les cadenes llargues són les estructuralment crítiques, coherent amb la ruta crítica de la secció 1.

Conclusió

Hem vist els grafs guanyar-se el sou: el planificador de TaskFlow (validar amb cicles, ordenar amb Kahn, paral·lelitzar per nivells, estimar amb la ruta crítica — el camí més llarg del DAG per programació dinàmica), els suggeriments socials per distància 2 i un PageRank de joguina que destil·la la idea que va ordenar la web. Res d'això no va requerir algorismes nous: només compondre BFS, DFS, Kahn i Dijkstra amb les estructures dels mòduls anteriors. Queda l'últim pas del mòdul, i és tot teu: una lliçó íntegra d'exercicis per consolidar grafs de cap a cap, del modelatge als algorismes, un altre cop amb TaskFlow com a camp de proves.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats