El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

Vam tancar el mòdul anterior amb una confessió: tots els nostres arbres amagaven un supòsit silenciós, el que cada node té un sol pare. Tan bon punt una tasca de TaskFlow depèn de diverses alhora —"desplegar l'API" necessita que acabin tant "migrar la BD" com "configurar el servidor"— la jerarquia es queda curta. I si a més algú crea una dependència circular per error, l'arbre directament no ho pot representar. L'estructura que sí que pot amb tot això és el graf: la més general del curs, la que engloba llistes i arbres com a casos particulars, i la que modela xarxes socials, mapes, la web o les dependències d'un projecte. En aquesta lliçó n'aprendrem el vocabulari; encara sense codi de representació (això arriba a la lliçó següent) ni algorismes (que esperen a la 07-03 amb el visitats promès al mòdul 5).

Contingut

De l'arbre al graf: per què necessitem alguna cosa més general
Definició formal: vèrtexs i arestes
Terminologia essencial (amb diagrames)
L'arbre com a cas particular de graf
Modelar les dependències de TaskFlow com a graf dirigit
Grafs al món real

De l'arbre al graf: per què necessitem alguna cosa més general

Recordem les dues limitacions concretes amb què vam ensopegar al final del mòdul 6:

Diversos pares: en un arbre, "desplegar l'API" només podria penjar de "migrar la BD" o de "configurar el servidor", mai de totes dues. Però en un projecte real depèn de les dues.
Cicles possibles: res no impedeix que un usuari de TaskFlow declari que A depèn de B, B de C i C d'A. Un arbre no ho pot ni expressar; un graf sí, i a més ens donarà algorismes per detectar-ho i avisar l'usuari.

Un graf elimina totes dues restriccions: qualsevol node es pot connectar amb qualsevol altre, en qualsevol direcció, fins i tot formant cicles. A canvi, perdem les garanties còmodes de l'arbre (arrel única, absència de cicles, un sol camí entre dos nodes), i per això els algorismes sobre grafs hauran de ser més curosos. Aquest és el preu de la generalitat.

Definició formal: vèrtexs i arestes

Un graf és un parell G = (V, E) on:

V és un conjunt de vèrtexs (també anomenats nodes): les entitats. A TaskFlow, les tasques.
E és un conjunt d'arestes (edges): les relacions entre parells de vèrtexs. A TaskFlow, les dependències.

Per exemple, amb tres tasques:

V = { migrar_bd, configurar_servidor, desplegar_api }
E = { (migrar_bd, desplegar_api), (configurar_servidor, desplegar_api) }

Fixa't que aquí les arestes són parells ordenats: (migrar_bd, desplegar_api) no és el mateix que (desplegar_api, migrar_bd). Això ens porta directament a la terminologia.

Terminologia essencial (amb diagrames)

Dirigit i no dirigit

En un graf dirigit (o digraf), cada aresta té sentit: va d'un origen a un destí i es dibuixa amb fletxa. "Migrar la BD desbloqueja desplegar l'API" no és simètric.
En un graf no dirigit, l'aresta és mútua: si A està connectada amb B, B ho està amb A. "L'Anna i en Bruno són amics".

graph LR
    subgraph Dirigit
        A[migrar_bd] --> B[desplegar_api]
    end
    subgraph No dirigit
        C[Anna] --- D[Bruno]
    end

Ponderat i no ponderat

Un graf és ponderat quan cada aresta porta associat un número (el seu pes): cost, distància, hores... A TaskFlow, el pes d'una aresta podrà ser les hores que costa completar la transició entre dues tasques. Si només ens importa si hi ha connexió, el graf és no ponderat.

graph LR
    A[dissenyar_esquema] -->|3 h| B[migrar_bd]
    B -->|2 h| C[desplegar_api]

Grau d'un vèrtex

El grau mesura quantes arestes toquen un vèrtex. En grafs dirigits es divideix en dos:

Concepte	Definició	Lectura a TaskFlow
Grau d'entrada	Arestes que arriben al vèrtex	Quantes tasques ha d'esperar aquesta tasca
Grau de sortida	Arestes que surten del vèrtex	Quantes tasques desbloqueja en acabar
Grau (no dirigit)	Arestes incidents	Nombre de connexions

Al diagrama de "desplegar l'API": grau d'entrada 2 (espera dues tasques), grau de sortida el que desbloquegi després.

Camí i cicle

Un camí és una seqüència de vèrtexs connectats per arestes consecutives: dissenyar_esquema → migrar_bd → desplegar_api. La seva longitud és el seu nombre d'arestes (2 a l'exemple).
Un cicle és un camí que comença i acaba al mateix vèrtex sense repetir arestes. En un graf de dependències, un cicle és un error fatal: ningú no pot començar.

graph LR
    A[dissenyar_ui] --> B[implementar_ui]
    B --> C[revisar_doc]
    C --> A
    style A fill:#fdd,stroke:#c00
    style B fill:#fdd,stroke:#c00
    style C fill:#fdd,stroke:#c00

Aquest cicle (dissenyar_ui → implementar_ui → revisar_doc → dissenyar_ui) significa que cap de les tres tasques no pot arrencar mai. Et sona això de "detecció de cicles"? Al mòdul 2 vam detectar cicles en llistes enllaçades amb l'algorisme de Floyd; en grafs necessitarem una tècnica diferent (lliçó 07-03), però el problema és germà.

Connex i components connexes

Un graf no dirigit és connex si des de qualsevol vèrtex es pot arribar a qualsevol altre. Si no, es divideix en components connexes: "illes" de vèrtexs connectats entre si però aïllades de la resta. A TaskFlow, dues components són dos projectes que no comparteixen cap dependència.

graph LR
    subgraph Component 1
        A[tasca_a] --- B[tasca_b] --- C[tasca_c]
    end
    subgraph Component 2
        D[tasca_d] --- E[tasca_e]
    end

Dens i dispers

Un graf dens té moltes arestes: a prop del màxim possible, que amb n vèrtexs dirigits és n · (n - 1).
Un graf dispers (sparse) en té poques: de l'ordre de n.

Els grafs de dependències reals són gairebé sempre dispersos (cada tasca depèn d'1–3 tasques, no de les 200 del projecte). Aquest detall, que sembla menor, decidirà a la propera lliçó com convé representar el graf en memòria.

DAG: graf dirigit acíclic

Un DAG (Directed Acyclic Graph) és un graf dirigit sense cicles. És l'estrella d'aquest mòdul: un projecte de TaskFlow ben format és exactament un DAG. Permet diversos pares (a diferència de l'arbre) però prohibeix els cercles viciosos (a diferència del graf general).

graph LR
    A[dissenyar_esquema] --> B[migrar_bd]
    S[configurar_servidor] --> C
    B --> C[desplegar_api]
    C --> D[proves_integracio]
    U[dissenyar_ui] --> I[implementar_ui]
    I --> D
    D --> L[llancament]

Observa: "desplegar_api" i "proves_integracio" tenen diversos pares (impossible en un arbre) i tot i així no hi ha cap cicle. Aquest DAG serà *l'*exemple recurrent de tot el mòdul.

L'arbre com a cas particular de graf

Ara podem situar el mòdul 6 al mapa: un arbre és un graf connex i acíclic (i en la seva versió amb arrel, dirigit amb grau d'entrada 1 a tots els vèrtexs llevat de l'arrel, que en té 0). Tota la jerarquia d'estructures del curs hi encaixa:

Estructura	Com a graf
Llista enllaçada (mòdul 2)	Graf dirigit on cada vèrtex té grau de sortida ≤ 1: un camí
Llista circular (mòdul 2)	Un cicle simple
Arbre (mòdul 6)	Graf connex acíclic; amb arrel: cada node, un sol pare
DAG	Dirigit sense cicles; s'hi permeten diversos pares
Graf general	Sense restriccions

Cada fila relaxa una restricció de l'anterior. Els algorismes que veurem funcionen sobre grafs generals i, per tant, també sobre tots els casos particulars: BFS sobre un arbre és exactament el recorregut per nivells del mòdul 6.

Modelar les dependències de TaskFlow com a graf dirigit

Ens falta fixar un detall que arrossegarem tot el mòdul: el sentit de les fletxes. Hi ha dues convencions possibles i totes dues són legítimes; l'important és triar-ne una i no barrejar-les.

Opció A: A → B significa "A depèn de B".
Opció B: A → B significa "B depèn d'A" (A ha d'acabar abans; la fletxa apunta al que A desbloqueja).

En aquest curs adoptem l'opció B: l'aresta migrar_bd → desplegar_api es llegeix "en acabar migrar_bd s'acosta el desbloqueig de desplegar_api". És la convenció natural per als algorismes que vénen: seguir les fletxes és avançar en el temps del projecte, i l'"ordre vàlid d'execució" sortirà de recórrer-les cap endavant.

Amb aquesta convenció, i recordant que cada tasca de TaskFlow continua sent el dict de sempre (id, titol, prioritat, estat, assignada_a, etiquetes, hores), el model mental complet és:

Vèrtex: l'id d'una tasca (el dict complet viurà a part, en un diccionari id → tasca, com a l'índex del mòdul 5).
Aresta A → B: B depèn d'A.
Grau d'entrada de B: nombre de dependències pendents de B. Quan arribi a 0... B és executable. Guarda't aquesta idea: és la llavor de l'ordre topològic (07-03).
Pes de l'aresta (quan n'hi hagi): hores o cost de la transició (07-04).

Grafs al món real

El mateix vocabulari modela sistemes molt diferents; només canvia què és vèrtex i què és aresta:

Sistema	Vèrtexs	Arestes	Dirigit?	Ponderat?
Xarxa social	Persones	Amistat / "seguir"	L'amistat no; "seguir" sí	Normalment no
Mapa de carreteres	Cruïlles, ciutats	Trams de via	De vegades (sentit únic)	Sí (km, minuts)
La web	Pàgines	Enllaços	Sí	No (o rellevància)
Paquets de programari (`pip`)	Paquets	"requereix"	Sí	No
TaskFlow	Tasques	Dependències	Sí	Opcional (hores)

Fixa't que pip install resol exactament el mateix problema que TaskFlow: donat un DAG de dependències, trobar un ordre vàlid d'instal·lació i queixar-se si hi ha cicles. Quan a la 07-03 implementem l'ordre topològic, hauràs entès com funciona per dins un gestor de paquets.

Errors Comuns i Consells

Barrejar les dues convencions de fletxa. Si un dia dibuixes A → B com "A depèn de B" i un altre com "B depèn d'A", els teus algorismes donaran resultats invertits. Fixa la convenció per escrit (nosaltres: la fletxa apunta al que es desbloqueja) i sigues conseqüent.
Confondre camí amb aresta. Que existeixi un camí d'A a C no significa que existeixi l'aresta directa A → C. Són preguntes diferents i, com veurem, amb costos de càlcul molt diferents.
Assumir que tot graf dirigit és un DAG. L'absència de cicles s'ha de comprovar, no suposar; les dades reals (introduïdes per usuaris) porten cicles per error més sovint del que t'imagines.
Oblidar els vèrtexs aïllats. Una tasca sense cap dependència (ni entrant ni sortint) continua sent un vèrtex del graf. Els conjunts V i E són independents: hi pot haver vèrtexs sense arestes.
Consell: abans de programar res, dibuixa el graf (mermaid o paper). En grafs, un bon dibuix estalvia la meitat dels errors de modelatge.

Exercicis

Exercici 1: classificar grafs

Per a cada sistema, indica si el seu graf natural és dirigit o no dirigit, ponderat o no, i si esperes que sigui un DAG: (a) l'historial de "fet a partir de" entre versions d'un document; (b) vols comercials entre aeroports amb la seva durada; (c) endolls connectats per cables en una oficina.

Exercici 2: llegir un graf de dependències

Amb la convenció del curs (A → B = B depèn d'A) i el DAG de TaskFlow d'aquesta lliçó, respon: (a) quin és el grau d'entrada i de sortida de proves_integracio? (b) quines tasques poden començar el primer dia (sense esperar ningú)? (c) escriu un camí de dissenyar_esquema a llancament i la seva longitud.

Exercici 3: provocar un cicle

Partint del mateix DAG, afegeix una sola aresta que creï un cicle, i explica amb la lectura "depèn de" per què el projecte resultant és impossible d'executar.

Solucions

Solució 1:

(a) Dirigit (la relació "derivat de" té sentit), no ponderat, i és un DAG: una versió no pot derivar d'una versió futura de si mateixa.
(b) Dirigit (anada i tornada poden diferir o no existir), ponderat (durada), i no és un DAG: els cicles (Madrid → París → Madrid) no només existeixen sinó que són desitjables.
(c) No dirigit (el cable connecta en tots dos sentits), ponderat si ens importa la longitud del cable; "DAG" no aplica a grafs no dirigits.

Solució 2:

(a) Entrada 2 (desplegar_api i implementar_ui hi arriben), sortida 1 (llancament).
(b) Les de grau d'entrada 0: dissenyar_esquema, configurar_servidor i dissenyar_ui.
(c) dissenyar_esquema → migrar_bd → desplegar_api → proves_integracio → llancament, longitud 4 (quatre arestes, cinc vèrtexs).

Solució 3: Per exemple llancament → dissenyar_esquema. Lectura: "dissenyar_esquema depèn de llancament". Però llancament depèn (transitivament) de dissenyar_esquema, així que cadascuna espera l'altra a través de la cadena: cap tasca del cicle no arriba mai a grau d'entrada 0 i el projecte sencer queda bloquejat. Qualsevol aresta "cap enrere" sobre un camí existent val com a resposta.

Conclusió

Ja parlem l'idioma dels grafs: vèrtexs i arestes; dirigit, ponderat, graus, camins, cicles, components, dens davant de dispers, i el DAG com a retrat fidel d'un projecte ben format. Hem situat llistes i arbres com a grafs amb restriccions, i hem fixat la convenció que governarà tot el mòdul: la fletxa apunta a la tasca que es desbloqueja. El que encara no sabem és com desar un graf en memòria: una gran taula de "qui connecta amb qui" o un diccionari de veïns? La resposta —matriu d'adjacència davant de llista d'adjacència, amb els seus costos i la seva classe Graf reutilitzable— és exactament el tema de la propera lliçó.

Introducció als Grafs