RIMIRO: versione alfa

Nell’articolo Cos’è RIMIRO? avevamo definito una prima struttura schematica delle procedure di base della versione alfa del progetto.

Il nostro Modello (comportamento o logica del programma) prevedeva:

  • creazione, attivazione/disattivazione ed eliminazione di un nodo
  • creazione ed eliminazione di un arco
  • spostamento di un nodo
  • salvataggio/caricamento di un grafo

A distanza di quasi tre mesi il codice è pronto.

Ovviamente il programma manca ancora della parte operativa: ovvero non è ancora in grado di eseguire alcun algoritmo.

Quello che però già possiamo fare è creare e modificare un generico grafo come quello più sotto.

Guida ai comandi disponibili

Nel prossimo articolo ragioneremo su come rendere operativo il grafo.

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:

  • sequenza (il percorso logico che segue un algoritmo o, più in generale, un generico programma)
  • selezione (o alternativa)
  • ciclo (o iterazione)

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.