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 far entrare in relazione più concetti?

Nei due precedenti articoli abbiamo riflettuto sulla possibilità di fare coding con i concetti e poi abbiamo iniziato a vedere come definire un concetto nel nostro codice.

Adesso dobbiamo tentare di dare una risposta a questa domanda:

Come possiamo far entrare in relazione più concetti?

Per farlo dobbiamo chiarirci le idee su cosa intendiamo per relazione.

Domandiamoci quindi:

Cos’è una relazione?

Nel Vocabolario Treccani troviamo, tra le varie definizioni, questa:

Connessione o corrispondenza che intercorre, in modo essenziale o accidentale, tra due o più enti (oggetti e fatti, situazioni e attività, persone e gruppi, istituzioni e categorie, fenomeni, grandezze, valori, ecc.).

Una relazione è quindi una connessione tra due o più enti: quindi tra due o più concetti.

Proviamo allora a riformulare la nostra prima domanda in questo modo:

Come possiamo creare una rete di concetti interconnessi?

Interconnessione concettuale

Se proviamo ad immaginare una rete di concetti interconnessi, è probabile che tra le immagini che si formano nella nostra fantasia ci sia quella di una ragnatela.

Ecco allora che potremmo identificare i fili com le connessioni e i punti di contatto dei vari fili con i concetti.

E il ragno? Che ruolo potremmo dare al ragno?

Il ragno sarà il nostro pensare che pazientemente deve tessere la tela che unisce i vari concetti.

Ma la similitudine con la ragnatela può spingersi oltre. Domandiamoci: chi è la preda?

La preda è l’obiettivo del pensare.

La preda che viene intrappolata nella tela dei nostri concetti interconnessi non è altro che l’idea. Un’idea che si illumina nella mente del programmatore mentre con il suo pensare connette i concetti.

Un esempio pratico

''
''esempio di connessione tra tre concetti
''

''definiamo il tipo di dato "concetto*"
type concetto
  id_1 as integer ''identificativo del concetto
  etichetta as string
  id_2 as integer ''identificativo del concetto connesso
end type
''dimensioniamo e creiamo il vettore dei concetti
''del tipo di dato "concetto"
dim vettore_concetti(1 to 3) as concetto

''**********

''valorizziamo i membri dei diversi concetti
vettore_concetti(1).id_1 = 1
vettore_concetti(1).etichetta = "pioppo"
vettore_concetti(1).id_2 = 2
vettore_concetti(2).id_1 = 2
vettore_concetti(2).etichetta = "albero"
vettore_concetti(2).id_2 = 3
vettore_concetti(3).id_1 = 3
vettore_concetti(3).etichetta = "pianta"
vettore_concetti(3).id_2 = 0

''**********

''esplora tutte le connessioni che si diramano dal primo concetto
''presente nel vettore dei concetti e stampa a video tutti i
''concetti interconnessi
cls
dim as integer id_1, id_2
id_1 = vettore_concetti(1).id_1
id_2 = vettore_concetti(1).id_2

print vettore_concetti(id_1).etichetta;

do until id_2 = 0

  print " ---> " & vettore_concetti(id_2).etichetta;

  id_1 = vettore_concetti(id_2).id_1
  id_2 = vettore_concetti(id_2).id_2

loop

Nel prossimo articolo affronteremo il terzo quesito:

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