PortLab

Un flusso è un grafo, non una gerarchia

Questa pagina somiglia a quella dei diagrammi a blocchi e ne condivide metà del codice, ma sotto ha un motore diverso, e la ragione vale la pena di essere detta perché è la stessa che decide quali strumenti si somigliano e quali no.

Un diagramma a blocchi è una gerarchia: livelli, riquadri, sottoriquadri. La disposizione cade fuori dall'annidamento — si misura dal basso, si posiziona dall'alto — e le frecce sono decorazione sopra una struttura già decisa. Un diagramma di flusso è un grafo: la struttura sono i collegamenti. Un rombo apre due rami che scendono in parallelo per qualche passo e poi si ricongiungono; e questo è precisamente l'allineamento in colonne fra righe diverse che nell'altro motore non esiste.

Ne segue una conseguenza pratica, ed è la scelta di fondo di questa pagina: la posizione dei blocchi non si modifica, si calcola. Nell'altro editor decidere a mano è il punto — è una figura da pubblicare. Qui sarebbe una condanna: un flusso si modifica inserendo un passo in mezzo, che è esattamente il momento in cui rifare a mano la disposizione diventa insostenibile.

La disposizione in quattro passi

Lo schema è quello proposto da Sugiyama, Tagawa e Toda nel 1981 per i grafi gerarchici, ed è lo stesso che sta dietro a dot di Graphviz.

1. I livelli, per cammino più lungo

Prima si cercano gli archi all'indietro, quelli che chiudono un ciclo: in un flusso sono i «riprova», e non sono un errore ma il caso normale. Si mettono da parte, e quel che resta è un grafo aciclico.

Su quello, il livello di ogni nodo è il cammino più lungo che lo raggiunge. Più lungo, non più corto, ed è la differenza che conta: con il cammino più corto un nodo raggiungibile sia in un passo sia in tre finirebbe al primo livello, e la freccia lunga dovrebbe risalire. Con il più lungo ogni nodo sta sotto tutti i suoi predecessori, e nessuna freccia in avanti punta all'indietro.

2. I nodi fittizi: il passo che sembra un dettaglio

Un arco che salta più di un livello riceve un segnaposto in ciascun livello attraversato. Da quel momento tutti gli archi collegano livelli adiacenti; i segnaposto partecipano all'ordinamento come se fossero nodi veri, e quindi si prendono una colonna; e l'arco non può passare sopra un blocco per costruzione.

Vale la pena confrontarlo con l'altra soluzione che in questo sito esiste già. Il visualizzatore dello schema del database risolve lo stesso problema — una linea che deve andare da qui a lì senza attraversare i riquadri — con un router A* su griglia di Hanan: cerca la strada. Fa così perché lì le tabelle le mette l'utente dove vuole, e gli ostacoli sono dove sono. Qui le posizioni le decidiamo noi, e possiamo riservare il corridoio in anticipo invece di cercarlo. Quando controlli la disposizione, il cammino minimo non ti serve.

3. L'ordine dentro il livello

Si riordinano i nodi di ogni livello per ridurre gli incroci, con il metodo del baricentro: ciascuno si mette vicino alla media delle posizioni dei suoi vicini nel livello accanto, alternando una passata verso il basso e una verso l'alto. È un'euristica, e si dichiara come tale: trovare il numero minimo di incroci è un problema NP-difficile, e non è più facile nemmeno nel caso a due soli livelli che il metodo affronta. Il baricentro non azzera gli incroci, ne toglie la gran parte a costo lineare — che per una figura leggibile basta.

4. Le coordinate, e il raddrizzamento

I nodi si distribuiscono nel livello e la fila si centra. Poi qualche passata di raddrizzamento tira ciascuno verso la media dei vicini, ristabilendo ogni volta la distanza minima con due scansioni, una per verso. Serve a far venire dritte le catene, che sono la maggior parte di un flusso: una catena storta si legge male anche quando è corretta.

Tutto questo lavora su coordinate astratte — una lungo il flusso, una di traverso — e si mappa su x e y solo alla fine. È il motivo per cui la direzione dall'alto in basso e quella da sinistra a destra non sono due disposizioni ma la stessa, letta su assi scambiati.

Le forme, e il rombo che non ci sta

I simboli sono quelli convenzionali dei diagrammi di flusso (ISO 5807): stadio per l'inizio e la fine, rettangolo per l'elaborazione, rombo per la decisione, parallelogramma per i dati, cilindro per l'archivio, esagono per la preparazione, e così via.

Una forma però richiede attenzione, e non trattarla rompe il disegno. In un rombo l'area utile è metà del riquadro che lo contiene: un rettangolo di semilati p e q ci sta solo se p/A + q/B ≤ 1, dove A e B sono le semidiagonali. Il rombo di area minima che contiene un testo w×h è quindi 2w×2h: il doppio in entrambe le direzioni. Senza questo conto le decisioni escono minuscole con il testo che sborda dai vertici.

C'è un correttivo: su una riga sola quel conto darebbe una losanga schiacciata, che non somiglia a un rombo di diagramma. Si impone allora anche un'altezza minima legata alla larghezza. Allargare è sempre sicuro — più spazio del necessario non fa danno — mentre stringere no.

Un motore del testo solo

La misura calibrata delle stringhe, l'interprete dei tag in linea con i pedici, il disegno dei <tspan> con la contabilità degli spostamenti della linea di base: tutto questo non è stato riscritto. Vive in diagramma.js, che lo espone, e questa pagina lo usa. Sono cose delicate, e una correzione fatta una volta deve valere per entrambi i disegni.

Lo stesso per l'impalcatura: annullamento, copia di scorta nel browser, esportazione con i caratteri incorporati e i dpi scritti nel PNG, zoom, tavolozza. Nessuna di queste cose sa che cosa sia un diagramma, e sta in js/common/editor_svg.js. La terza pagina di questo tipo costerà l'interfaccia e basta.

Bibliografia

• K. Sugiyama, S. Tagawa, M. Toda, Methods for visual understanding of hierarchical system structures, IEEE Transactions on Systems, Man, and Cybernetics 11(2), 109–125, 1981. DOI 10.1109/TSMC.1981.4308636
• E. R. Gansner, E. Koutsofios, S. C. North, K.-P. Vo, A Technique for Drawing Directed Graphs, IEEE Transactions on Software Engineering 19(3), 214–230, 1993. DOI 10.1109/32.221135 — i nodi fittizi e l'assegnazione delle coordinate come li fa dot.
• M. R. Garey, D. S. Johnson, Crossing Number is NP-Complete, SIAM Journal on Algebraic and Discrete Methods 4(3), 312–316, 1983. DOI 10.1137/0604033
• ISO 5807:1985, Information processing — Documentation symbols and conventions for data, program and system flowcharts, program network charts and system resources charts — i simboli usati qui.
• W3C, Scalable Vector Graphics (SVG) 2, Candidate Recommendation. www.w3.org/TR/SVG2/

A che serve

A costruire diagrammi di flusso — procedure, algoritmi, pipeline — e a portarseli via come SVG o come PNG a una risoluzione scelta. Il diagramma si salva come file JSON e si riapre quando serve: non c'è niente nel database, il documento è il file.

La differenza con i diagrammi a blocchi è che qui non si posizionano i blocchi: si dice quali sono e come sono collegati, e la disposizione la calcola il programma. Si lavora sul contenuto, non sulle coordinate.

Le tre parti della pagina

A sinistra l'elenco dei Blocchi, raggruppati per livello — il livello è il risultato del calcolo, non un comando: guardarlo è il modo più diretto di capire perché il disegno è venuto così. Sotto le Proprietà di quello che si è selezionato; il pulsante Diagramma in cima riporta alle proprietà generali. A destra il disegno, che si rifà a ogni modifica, e sotto la tabella dei Collegamenti. Un blocco si seleziona dall'elenco oppure cliccandolo nel disegno: il selezionato è contornato di azzurro tratteggiato.

Con Ctrl (o Cmd) premuto il clic aggiunge alla selezione invece di sostituirla, e ripremuto la toglie. Con più blocchi selezionati i campi mostrano i valori dell'ultimo toccato — quello col contorno pieno — ma ogni modifica si applica a tutti: è il modo di dare lo stesso colore a sei blocchi in una volta sola.

La casella in cima all'elenco filtra: restano visibili solo le voci che contengono il testo cercato.

Da tastiera: ↑ e ↓ scorrono all'elenco nell'ordine in cui si vede, filtro compreso; Invio porta il cursore nel testo di quello scelto; Canc lo elimina — tutti, se la selezione è multipla.

Costruire un flusso

Il modo più rapido è selezionare un blocco e premere Passo successivo: ne aggiunge uno sotto, già collegato. Ripetendolo si scrive la catena principale senza mai toccare la tabella dei collegamenti.

Per una diramazione: si seleziona il rombo, si preme Passo successivo due volte (i due rami), e nella tabella si scrive sì e no nelle rispettive etichette. Il motore fa uscire i due rami da lati diversi del rombo, così le due scritte non si sovrappongono.

Aggiungi un blocco (nelle proprietà del diagramma) ne crea uno scollegato; Duplica copia il selezionato con tutto il suo stile; Elimina lo toglie insieme ai collegamenti che lo nominano, per non lasciare riferimenti rotti.

L'identificatore è il nome con cui i collegamenti chiamano il blocco. Cambiandolo, i collegamenti vengono aggiornati da soli.

Le forme

La casella Forma sceglie fra i simboli convenzionali: avvio e fine (stadio), processo (rettangolo), sottoprocesso (con le barre laterali), decisione (rombo), ingresso e uscita (parallelogramma), documento (fondo ondulato), archivio (cilindro), preparazione (esagono), manuale (trapezio), connettore (cerchio). Ogni forma ha un colore predefinito che si può cambiare, da sola o con le combinazioni di colore.

I collegamenti e i ritorni

Ogni collegamento va Da un blocco A un altro, e può avere un'etichetta — il sì e il no di una decisione. Tratto, colore, spessore e punta si scelgono per collegamento.

Un collegamento che risale, cioè che chiude un ciclo, viene riconosciuto da solo e la sua riga si colora di giallo: è un ritorno. Non è un errore — è il «riprova» di ogni procedura. I ritorni non scendono fra i blocchi: corrono in una corsia lungo il margine, e la colonna Ritorno permette di scegliere se a sinistra o a destra.

Quando la disposizione non piace

Nelle proprietà di un blocco ci sono due campi che fissano la sua posizione:

• Livello: la riga (o la colonna, se il flusso scorre in orizzontale) in cui metterlo. Lasciandolo vuoto lo decide il programma. Un blocco fissato porta una puntina nell'elenco.
• Ordine nel livello: la posizione dentro la riga, contata da zero.

Fissare un blocco non blocca gli altri: chi lo segue viene spinto sotto, e il resto si sistema attorno. Se si chiede l'impossibile — un blocco fissato sopra uno da cui dipende — la pagina lo dice in rosso sotto il disegno e disegna comunque.

Nelle proprietà del diagramma si regolano la direzione del flusso (dall'alto in basso o da sinistra a destra) e le due distanze, fra i livelli e fra i blocchi: allargare la seconda è spesso quello che serve quando un ramo viene stretto.

Testo e caratteri

Carattere, corpo, colori e tratto si impostano sul diagramma e scendono a tutti i blocchi; un blocco ridefinisce solo ciò che deve cambiare, e Torna allo stile ereditato cancella le sue eccezioni. Vale anche la spunta Escape HTML: toltala, dentro i blocchi funzionano <b>, <i>, <u>, <s>, <sub>, <sup> e <br> — è così che si scrivono PM_2.5 o m³. Tutto il resto resta visibile come testo.

I corpi hanno un comando unico, nel gruppo Dimensioni dei caratteri del diagramma: Titoli, Testi ed Etichette dei collegamenti, per cambiare insieme tutti i campi di testo dello stesso genere. I testi sono il corpo di base; titoli ed etichette lo seguono finché il loro campo resta vuoto — i titoli alla stessa dimensione, le etichette a 0,86 volte — e il valore in vigore si legge in grigio dentro il campo. Scritto un numero, il campo vale da sé; cancellato, torna a seguire i testi. Un blocco con un corpo suo non viene raggiunto: il gruppo dice quanti sono, e Applica a tutti toglie quelle eccezioni. Sul singolo blocco il campo Corpo cambia il testo; il titolo lo segue solo finché i titoli del diagramma sono vuoti.

Annullare, esportare, non perdere il lavoro

Le due frecce curve annullano e rifanno, anche con Ctrl+Z e Ctrl+Y; si torna indietro di sessanta passi e una raffica di tasti nella stessa casella conta come un passo solo. Nuovo, Esempio e Apri JSON chiedono conferma se c'è del lavoro non salvato, il browser avvisa alla chiusura, e una copia di scorta resta nel browser: dopo un ricaricamento involontario una barra gialla offre di riprenderla.

SVG è il formato da preferire: vettoriale, con i caratteri incorporati. PNG serve quando il vettoriale non è accettato; il campo dpi stabilisce la risoluzione e viene scritta dentro il file, così l'immagine si inserisce in un documento già alla dimensione fisica giusta. Accanto allo zoom si legge la dimensione in pixel e in centimetri: quella in centimetri non dipende dai dpi, che cambiano la nitidezza e non la misura.

I due pulsanti con la graffetta copiano negli appunti invece di scaricare: quello accanto a SVG copia il codice, quello accanto a PNG copia l'immagine alla risoluzione scelta, pronta da incollare in un documento o in un messaggio. Servono una connessione sicura, che il sito ha.

Il campo cm impone la larghezza con cui la figura esce. Non ridisegna niente: cambia la misura dichiarata nel file lasciando intatto il sistema di coordinate — con il vettoriale è esatto, non si perde nulla — e il PNG segue con i suoi dpi. Lasciato vuoto vale la dimensione naturale; quando è impostato, accanto alle misure compare una freccina.

PDF è il formato che le riviste chiedono per le figure (con l'EPS, che se ne ricava): vettoriale, con i caratteri incorporati come sottoinsiemi e la pagina della misura esatta della figura — quella in cm, se è impostata. Lo produce il server con rsvg-convert, che usa i caratteri di sistema e non quelli incorporati nell'SVG: se una famiglia non è installata sul server, la sostituzione viene segnalata subito, dopo il download. La pagina Diagnostica ha il controllo corrispondente, con il comando di installazione.

Su più pagine. Il menu accanto a Esporta PDF sceglie il foglio: una pagina, della misura della figura come sopra, oppure A4 o A3, orizzontale o verticale. Con un foglio scelto il disegno non si rimpicciolisce: esce alla misura del campo cm (o alla naturale) e si divide in una griglia di pagine, da sinistra a destra e poi sotto, con margini di 1 cm. La barra dice prima quante pagine servono, e il piede di ognuna porta il nome del file, il numero e — se la griglia ha più righe e più colonne — la riga e la colonna, per riaccostarle. I tagli cadono fra i nodi, dove se ne attraversano meno; una freccia, invece, si può tagliare. Oltre 100 pagine il PDF non si fa: si riduce la larghezza in cm o si sceglie un foglio più grande.

Un file JSON si può anche trascinare direttamente sul disegno per aprirlo.

Il JSON

Il pannello in fondo mostra il modello per esteso. La forma è questa:

{
  "stile":  { "font": "IBM Plex Sans, Arial, sans-serif", "dim": 13 },
  "pagina": { "direzione": "verticale", "gap_livelli": 44, "gap_nodi": 26 },
  "nodi": [
    { "id": "inizio", "tipo": "avvio",     "testo": "Avvio" },
    { "id": "leggi",  "tipo": "processo",  "testo": "Leggi i dati" },
    { "id": "ok",     "tipo": "decisione", "testo": "Dati validi?" },
    { "id": "errore", "tipo": "processo",  "testo": "Segnala", "livello": 3 }
  ],
  "archi": [
    { "da": "inizio", "a": "leggi" },
    { "da": "leggi",  "a": "ok" },
    { "da": "ok",     "a": "errore", "etichetta": "no" },
    { "da": "errore", "a": "leggi",  "tratto": "tratteggiato", "lato": "sinistra" }
  ]
}

Le chiavi omesse prendono il valore ereditato, e un flusso valido può essere lungo quattro righe. Premere Applica per portarlo nel disegno. Nello stile del diagramma, dim_titolo e dim_etichetta fissano i corpi dei titoli e delle etichette dei collegamenti; omesse, seguono dim.

Limiti da conoscere

• Gli incroci si riducono, non si azzerano: trovarne il minimo è un problema NP-difficile. Su un grafo molto intrecciato conviene spezzare il diagramma o usare i connettori.
• La posizione non si trascina. È una scelta, non una mancanza: si fissa con Livello e Ordine.
• Il diagramma non si salva sul server. La copia di scorta nel browser copre lo scivolone ma non è un archivio: ce n'è una sola, e sta su questa macchina.
• Nel PNG si incorporano solo le quattro famiglie ospitate dal sito (IBM Plex Sans, Nunito, Roboto, JetBrains Mono).