Teoria dei Grafi, Matrici di Adiacenza, QGIS

Connessione di punti appartenenti ad un gruppo, mediante un insieme di archi . I Virtual Layer di QGIS.

by internet

Il Caso

“Dato un numero di punti, connetterli tra loro mediante un insieme di archi, utilizzando come criterio il raggruppamento effettuato in base al valore contenuto in un campo della tabella attributi ad essi aggregata”.

Analisi e scomposizione

1. Definizione dei gruppi di punti, in base al valore contenuto in un campo.
2. Connessione tra tutti quei punti che appartengono ad un determinato gruppo individuato al punto 1), mediante un insieme finito di archi.

Discretizzazione

a) Collettivo (insieme dei punti) {U}

b) Carattere (qualitativo, quantitativo) che si esprime mediante la sua modalità,il valore del campo che ne individua la classe di appartenenza {Gruppo}

c) Struttura algoritmica che definisce la tipologia di connessione tra i punti appartenenti a U {Grafo G}

Nozioni introduttive

Il punto 2) e il punto c) meritano un approfondimento , che porta a considerare quella che viene definita la teoria dei grafi, quel campo della matematica che studia gli insiemi finiti e che comprende la geometria combinatoria, ovvero una struttura relazionale costituita da un insieme di oggetti detti nodi o vertici e da un insieme di relazioni tra coppie di oggetti, detti archi o spigoli.

Detto G il grafo, la notazione e’ del tipo G(N,A) con N=Nodi, A=Archi.

Definizioni

• Grafo completo: costituito da N nodi a due a due adiacenti e connessi tra loro da un arco.
• Grafo semplice: non contiene né archi multipli né loops o cappi.
• Cappi: sono costituiti da archi con estremi coincidenti.
• Fortemente connesso: se per ogni coppia di vertici esiste un cammino che li unisce.
• Grafo connesso: ogni nodo è collegato a tutti i nodi rimanenti.
• Grafo non orientato: ogni arco è individuato da una coppia di vertici indipendentemente dal loro ordine.

I grafi semplici sono detti logicamente equivalenti alle relazioni simmetriche. Questo significa matematicamente che vi è simmetria in una relazione binaria tra due elementi x e y, se e solo se vale la condizione che, se x e’ in relazione con y, allora anche y è in relazione con x.

Nel problema posto, si richiede che per ogni coppia di nodi esista un solo arco che li congiunga senza alcun orientamento, pertanto diviene indifferente descriverne l’arco con (1,2) o (2,1). Se ne deduce che il Grafo risulta essere completo, semplice, fortemente connesso, non orientato.

Dimensionamento del Grafo G (N,A)

La dimensione di un Grafo G completo e semplice, composto da N nodi, è stabilita dal numero di archi o spigoli pari a :

ovvero, il numero massimo di combinazioni possibili tra gli N nodi, presi a due a due. In pratica gli archi non sono altro che il risultato di una corrispondenza biunivoca tra i sottoinsiemi {X} e {Y} di due elementi di N e il loro numero e’ determinato dal coefficiente binomiale, mentre il range dimensionale per qualsiasi grafo semplice è definito come :

Tutto ciò, porta in argomento a quella che viene definita matrice delle adiacenze, che e’ alla base degli algoritmi che generano i grafi e della loro rappresentazione. Nel caso del grafo semplice oggetto di studio, trattasi di una matrice binaria simmetrica quadrata, come da Fig.1 , avente per indici di righe e colonne i Nodi del Grafo, ed e’ caratterizzata dal fatto che gli elementi ( i , j ), possono valere solo (1) o (0) mentre gli elementi della diagonale principale sono nulli.

Fig.1 — Matrice delle adiacenze di un Grafo G Semplice indiretto (non orientato) con N=6 e A=15

Data la matrice delle adiacenze, preso un casuale collettivo U di punti (N= 6), la rappresentazione del grafo è la seguente :

Fig. 2— Grafo completo non orientato o indiretto con N=6 e A=15

Tabella a doppia entrata rappresentazione cartesiana tra due insiemi, {X} e {Y}

Attraverso il prodotto cartesiano tra due insiemi finiti {X} e {Y}, che nel caso specifico vale {X}={Y}, e’ stato possibile determinarne l’insieme di tutte quelle coppie ordinate (x,y) di Nodi, con x appartenente ad {X} ed y a {Y}.

Elencazione degli elementi A (archi):

A {(1,2);(1,3);(1,4);(1,5);(1,6);(2,3);(2,4);(2,5);(2,6);(3,4);(3,5);(3,6);(4,5);(4,6);(5,6)}

L’elencazione degli elementi A, mostra tutte le coppie ordinate derivanti dalla rappresentazione cartesiana di Fig. 3, tolta la ridondanza e gli archi con estremi coincidenti (cappi), ottenendo la numerosita’ pari a 15, degli archi A del grafo G.

Fig.3 — Rappresentazione Cartesiana {X}x{Y}

Grafo pesato

La caratteristica dei grafi pesati, sta nell’avere per ogni suo arco, una label associata detta peso (weight), espressa in numeri reali, razionali o interi a seconda della tipologia di grafo che si vuole andare a rappresentare. Nell’esempio contenuto in questo articolo, il campo peso e’ stato utilizzato per la definizione del criterio di raggruppamento dei Nodi.

Fig. 4— Grafo completo non orientato pesato (1 gruppo di appartenenza)

Qgis e i Virtual Layer

Il Virtual Layer, cosi’ come definito dalla documentazione ufficiale di QGIS, e’ una tipologia speciale di vettore, quale risultante di una query avanzata o complessa, mediante il linguaggio SQL, applicata a tutti quei vettori veri e propri esistenti e leggibili da QGIS. La cosa importante sta nel fatto che questa tipologia di layer virtuali, non gode di dati propri, ma ne rappresenta l’ elaborazione visuale derivante da altri layer.

Nota

La premessa analitico-matematica fin qui esposta, e’ stata necessaria al fine di meglio chiarire, la base del ragionamento che ha comportato la codifica della SQL Query utilizzata in un Virtual Layer di QGIS.

Analisi della Query

SELECT X.id AS Nodes_X,Y.id AS Nodes_Y,X.weight AS Weight,    shortestline (X.geometry,Y.geometry) AS geom
FROM Nodes X INNER JOIN Nodes Y ON (X.id < Y.id)
WHERE X.weight = Y.weight

La query produce fondamentalmente, il prodotto cartesiano tra due tabelle rappresentanti i due sottoinsiemi alias {X} e {Y}, derivanti dal collettivo in esame U “layer nodes”, con {X}={Y} → {{X}x{X}},dando luogo ad una matrice binaria simmetrica quadrata come da Fig.3. Trattandosi di Grafo fortemente connesso, semplice e indiretto, devono essere esclusi tutti i cappi, quindi tutte le coppie di archi {(1,1);(2,2);(3,3);(4,4);(5,5);(6,6)} e i duplicati (ridondanze), in quanto non contenente archi multipli ,ma avente un solo arco per ogni coppia definita di Nodi. Il CROSS JOIN va implementato pertanto, impostando una regola di confronto con l’operatore INNER JOIN posto nella clausola FROM in base allo standard ISO, tra tutte le colonne unite, cosí da escludere i duplicati derivanti dalla simmetria, in quanto le righe che vengono coinvolte, risultano essere un sottoinsieme delle righe di ciascuna tabella, ove la condizione posta viene soddisfatta. Senza l’opportuna forzatura condizionale, la query restituirebbe come risultato, una tabella costituita da N x N righe, contenente cappi e duplicati, sfumando gli obiettivi prefissati, si veda Fig. 5. A questo punto della query, tutti gli archi risultanti, sono raggruppati mediante pesatura, in base al valore contenuto nel campo Weight, utilizzando la clausola WHERE.

      SELECT X.id AS Nodes_X,Y.id AS Nodes_Y,X.weight AS Weight
      FROM Nodes X INNER JOIN Nodes Y 
      WHERE X.weight = Y.weight

Fig.5 — Duplicati e Cappi

Nella SELECT SQL , con la quale vengono estratti i campi di interesse, che diventeranno gli attributi del Virtual Layer in QGIS, compare:

             shortestline (X.geometry,Y.geometry) AS geom

ShortestLine e’ una SQL function , che troviamo in Spatialite, con la seguente sintassi:

    ShortestLine( geom1 Geometry , geom2 Geometry ) : Curve

ma anche in Postgis:

   ST_ShortestLine( geom1 Geometry , geom2 Geometry ) : Curve

In pratica tale funzione, permette di ottenere la linea bidimensionale piú breve tra due geometrie. Restituisce un valore NULL, nel caso gli argomenti in oggetto non fossero validi o nel caso di lunghezza zero della linea ed e’ richiamabile direttamente in SELECT SQL. In Fig. 6, la schermata esplicativa di QGIS, che mostra la creazione del Virtual Layer a partire dal Layer Nodes, il collettivo U in esame.

Fig.6 — Creazione di un Virtual Layer

A questo punto non resta altro che mettere all’opera tutta la teoria esposta sin qui, sperimentando la creazione analitica di Grafi, mediante l’uso dei Virtual Layer. Basterà dotarsi di un collettivo di punti localizzati e popolare il campo weight con i valori di interesse a seconda del tema in questione. Il Virtual Layer si occupera’ di realizzare le aggregazioni in funzione dei pesi, come mostrato in Fig.7.

I casi applicativi come potete immaginare sono molteplici.

Fig.7- Esempio di Grafi pesati

Considerazioni finali

L’idea di scrivere un articolo su questo tema, è nato leggendo un post/richiesta da parte di un iscritto al gruppo Fb GIS Italia, che ha colto da subito la mia attenzione. E’ stato davvero un piacere scriverlo e poterlo condividere, nella speranza che sia utile a qualcuno e che possa dare spunto a ulteriori approfondimenti. Ringrazio in particolare Salvatore Fiandaca, per l’apprezzamento fattomi per questa stesura e per avermi incentivato a pubblicarla. Qui ho condiviso i Files Qgis utilizzati per questa demo.