Graph IN-OUT
IN-OUT Graph (G IN-OUT) è un algoritmo adatto a filtrare una matrice quadrata di pesi, con la diagonale principale nulla, generata da un qualsiasi altro algoritmo.
La matrice dei pesi viene analizzata dall’algoritmo G IN-OUT che ne filtra i valori e produce un grafo pesato con caratteristiche specifiche:
1. il grafo risultante è un grafo diretto quando la matrice originale non è simmetrica;
2. il grafo risultante potrebbe essere sparso, cioè composto da vari grafi non collegati tra loro.
La logica dell’algoritmo G IN-OUT è semplice; se consideriamo una matrice di connessioni asimmetrica e quadrata, in cui le colonne rappresentano i nodi che ricevono le connessioni pesate e le righe rappresentano gli stessi nodi che inviano le loro connessioni ponderate, allora:
- Ogni nodo delle colonne è collegato ad un solo nodo delle righe della sua colonna, laddove il peso è il più forte; di conseguenza, ogni nodo di colonna invierà un arco (connessione) ad un solo nodo della riga; cioè per ogni nodo di colonna vi sarà una sola uscita (OOU);
- Ogni nodo delle righe è collegato ad un solo altro nodo delle colonne della sua riga, laddove il peso è il più forte; di conseguenza, ogni nodo di riga riceverà un arco (connessione) da un solo nodo della colonna; cioè per ogni nodo di riga vi sarà un solo ingresso (OOI).
L’arco OOI rappresenta la connessione di Input maggiore che ogni nodo di colonna riceve tra tutti gli altri nodi presenti, mentre l’arco OOU rappresenta la connessione di Output maggiore che il nodo delle righe invia agli altri nodi di colonna.