Grafi, diagrammi di flusso e database

Scopo di questo articolo è quello di riflettere sul concetto di grafo, sulla relazione che i grafi hanno con i diagrammi di flusso (flow chart) e con le basi di dati (database), infine sul cominciare ad immaginare una nuova modalità di rappresentazione grafica degli algoritmi e delle basi di dati: una modalità che sia al tempo stesso descrittiva e operativa.

Cosa sono i grafi

In estrema sintesi un grafo è un insieme di punti che possono essere collegati tra loro.

Tra le tante possibili definizioni, in questo articolo chiameremo i punti con il termine nodi e i collegamenti con quello di archi.

Identificando un generico grafo con la lettera maiuscola G, l’insieme dei nodi con la lettera maiuscola N e l’insieme degli archi con la lettera maiuscola A, avremo la formula:

G(N,A)

Cosa possiamo rappresentare con un grafo?

Dalla definizione data, è facile immaginare che un grafo può rappresentare molte strutture reali o astratte, per esempio:

Codice sorgente

  • i nodi potrebbero identificare le singole istruzioni di un programma informatico;
  • gli archi potrebbero identificare la sequenza delle istruzioni descrivendo quindi tutte le possibili diramazioni.

Questo esempio ci suggerisce che il classico diagramma di flusso (flow chart) può essere assimilabile ad un grafo.

È utile ricordare che il paradigma della programmazione strutturata fa largo uso dei diagrammi di flusso per rappresentare i suoi tre elementi fondamentali:

Base di dati (database)

  • i nodi potrebbero identificare i singoli concetti;
  • gli archi potrebbero identificare le relazioni tra i concetti e definirne la tipologia e la direzione.

Tipologie dei grafi

Si possono avere diverse tipologie di grafi in base ad alcune caratteristiche dei nodi o degli archi.

Grafo orientato

Se gli archi che collegano i vari nodi hanno un verso di percorrenza, allora il grafo si dice orientato, altrimenti viene definito non orientato.

Data questa definizione è facile capire che un diagramma di flusso rientra tra i grafi orientati, così come una base di dati a grafo dove la tipologia di relazione tra due concetti esprime anche una direzione.

Nomenclatura

Nei grafi orientati i vari elementi prendono le seguenti definizioni:

nodo di partenza (i): coda (o predecessore di j)
nodo di arrivo (j): testa (o successore di i)

Grafo e multigrafo

Se in un grafo vi è la presenza di almeno due nodi collegati tra loro da più archi, allora il grafo prende il nome di multigrafo.

Il diagramma di flusso è quindi un grafo orientato completo.

Una base di dati a grafo può essere sia un grafo che un multigrafo orientato completo.

L’indicazione completo ci informa che non vi sono nodi isolati: ovvero privi di un arco di collegamento con altri nodi.

Rappresentazione di un grafo con un linguaggio di programmazione

Esistono diverse possibilità per rappresentare un grafo attraverso un qualsiasi linguaggio di programmazione.

Una di queste è la lista di adiacenza.

Lista di adiacenza

Per costruire una lista di adiacenza che rappresenti un generico grafo, possiamo sfruttare due costrutti tipici della maggior parte dei linguaggi di programmazione:

E adesso? Che si fa?

Adesso è arrivato il momento di mettersi al lavoro per cercare di tradurre in codice FreeBASIC le idee che abbiamo raccolto sin qui.

Abbiamo di fronte a noi due obiettivi molto difficili:

  1. Sviluppare una applicazione per la rappresentazione grafica sia di una generica base di dati che degli algoritmi. Una rappresentazione che metta insieme l’arte (colori e figure) e la scienza (concetti e idee), e che sia inoltre operativa: ovvero che si possano eseguire gli algoritmi sulla base dati.
  2. Che questa applicazione non si limiti ad essere un altro modo per fare programmazione visuale, ma che sia una educazione pratica del pensiero.

Ogni progetto ha bisogno di un nome. Eccolo: RIMIRO. 🙂

Come possiamo far fare qualcosa al computer sulla base di una serie di concetti interconnessi?

Nel precedente articolo abbiamo identificato i due soli elementi che riteniamo debbano essere necessari e sufficienti per permetterci di programmare con i concetti.

I due elementi sono: i concetti e le connessioni tra loro.

Siccome nell’Informatica, come anche in tanti altri campi, bisogna evitare di reinventare la ruota, se riflettiamo in maniera approfondita sull’idea di una rete di concetti interconnessi, arriviamo, prima o poi, a toccare il concetto di grafo.

Concentriamoci ora sulla definizione semplificata di grafo:

Un grafo è un insieme di elementi detti nodi che possono essere collegati fra loro da linee chiamate archi.

Ma allora, se equipariamo i nostri concetti ai nodi e le nostre connessioni agli archi, siamo forse sulla buona strada per tradurre in codice informatico la nostra rete di concetti interconnessi.

Nel prossimo articolo approfondiremo la relazione tra i grafi, i diagrammi di flusso e i database.

Come possiamo definire un concetto nel nostro codice?

Ci eravamo lasciati nel precedente articolo dicendo che se vogliamo esplorare la possibilità di fare coding con i concetti, dobbiamo risolvere tre problemi, il primo dei quali è legato proprio alla domanda scelta come titolo per questo articolo:

Come possiamo definire un concetto nel nostro codice?

Sempre nell’articolo già citato abbiamo definito il concetto* di concetto** in questo modo:

Un concetto può essere visto come una etichetta che rimanda ad una entità reale o astratta.

In questo senso l’etichetta concetto* potrebbe rimandare all’entità astratta “cerchio” (concetto**) che a sua volta potrebbe rimandare all’entità reale “ruota avente raggio di 22cm”.

Proviamo a partire con le nostre riflessioni proprio dalla definizione che abbiamo dato.

Innanzitutto suddividiamola nelle sue parti costitutive per verificare se possiamo tradurle in codice:

  • un concetto è identificato da una etichetta;
  • un concetto rimanda ad una entità reale o astratta.

Concentriamoci per il momento sulla sola prima frase e facciamo entrare nel flusso dei nostri pensieri anche gli argomenti trattati nella nostra Guida al FreeBASIC. Sappiamo che uno dei sinonimi del verbo identificare è far coincidere. Facendo ora un parallelo con quanto abbiamo imparato studiando il FreeBASIC, ci dovrebbe venire in mente l’articolo dedicato alla dichiarazione delle variabili: ad una variabile, infatti, coincide uno spazio in memoria. In altri termini, all’etichetta scelta come nome della variabile corrisponderà un certo valore: quindi una certa informazione.

Tenendo a mente questa idea e passando alla seconda frase, il rimando ad entità reali o astratte porta il nostro pensiero al tema più specifico della dichiarazione di un tipo di dato definito ad hoc che possa rappresentare queste entità.

Attenzione! Nell’ambito dell’informatica, rappresentare una qualsiasi cosa significa, in ultima analisi, costruire un modello.

Le nostre riflessioni ci hanno quindi per ora condotto ad un altro concetto, quello di modellizzazione.

Il processo di modellizzazione avviene attraverso l’interazione tra l’atto dell’osservazione e l’atto del pensare. Questa interazione permette di creare un modello, cioè una classe generica (concetto**) che rappresenta una certa entità astratta che a sua volta rappresenta idealmente una entità reale o astratta (cioè il cosiddetto oggetto o istanza della classe).

Esprimendo il problema in questi termini ci sembra di giungere come logica conseguenza al paradigma della programmazione orientata agli oggetti.

Ma allora questo ipotetico nuovo paradigma di programmazione per concetti che andiamo vagheggiando non è altro, in realtà, che l’arcinoto paradigma di programmazione ad oggetti?

Apparentemente sembrerebbe di sì, ma cè un aspetto che facilmente può sfuggire ad una prima analisi.

Proviamo ad approfondire la questione dicendo quanto segue:

Nella programmazione per concetti non si vogliono creare dei modelli, ovvero delle classi al fine di istanziarle per ottenere degli oggetti con cui lavorare, ma si vuole rimanere al solo livello concettuale del tipo (type), e solo con questo lavorare. Non si creano quindi delle classi e non si istanziano oggetti.

Si abbandona quindi l’idea della rappresentazione: ovvero la creazione arbitraria e soggettiva di un modello (concetto**), nella convinzione che il modello non potrà mai essere la realtà.

Si persegue invece l’idea dello sviluppo dinamico di una rete di concetti* interconnessi.

Nel nuovo paradigma di programmazione per concetti che andiamo definendo il ruolo fondamentale spetta alla riflessione del programmatore: sarà il suo pensare riflessivo che creerà dinamicamente le connessioni concettuali che sveleranno l’idea che di volta in volta informa una determinata realtà.

Un esempio pratico

''definiamo il tipo di dato "concetto*"
type concetto
  id as integer ''identificativo del concetto
  etichetta as string
end type

''dimensioniamo e creiamo il vettore dei concetti
''del tipo di dato "concetto"
dim vettore_concetti(1 to 2) as concetto

''valorizziamo i membri dei diversi concetti
vettore_concetti(1).id = 1
vettore_concetti(1).etichetta = "albero"
vettore_concetti(2).id = 2
vettore_concetti(2).etichetta = "pioppo"

Bene. Possiamo per oggi fermarci qui.

Nel prossimo articolo affronteremo il secondo quesito:

Come possiamo far entrare in relazione più concetti?