MungingData

I Directed Acyclic Graphs (DAGs) sono una struttura di dati critica per la scienza dei dati / flussi di lavoro di ingegneria dei dati. I DAG sono ampiamente utilizzati da progetti popolari come Apache Airflow e Apache Spark.

Questo post del blog vi insegnerà come costruire un DAG in Python con la libreria networkx ed eseguire importanti algoritmi di grafi.

Una volta che vi sarete trovati a vostro agio con i DAG e avrete visto quanto sono facili da usare, troverete tutti i tipi di analisi che sono buoni candidati per i DAG. I DAG sono importanti quanto le strutture di dati come dizionari e liste per molte analisi.

Semplice esempio

Considerate il seguente DAG:

radice, a, b, c, d, ed e sono chiamati nodi. Le frecce che collegano i nodi sono chiamate bordi. Un grafo è un insieme di nodi collegati da spigoli. Un grafo aciclico diretto è un tipo speciale di grafo con proprietà che saranno spiegate in questo post.

Ecco come possiamo costruire il nostro grafo di esempio con la libreria networkx.

import networkx as nxgraph = nx.DiGraph()graph.add_edges_from()

DiGraph è l’abbreviazione di “grafo diretto”.

Il grafico diretto è modellato come una lista di tuple che collegano i nodi. Ricordate che queste connessioni sono chiamate “bordi” nella nomenclatura dei grafi. Date un’altra occhiata all’immagine del grafico e osservate come tutti gli argomenti di add_edges_from corrispondono alle frecce nel grafico.

networkx è abbastanza intelligente da dedurre i nodi da un insieme di bordi.

graph.nodes() # => NodeView(('root', 'a', 'b', 'e', 'c', 'd'))

Gli algoritmi vi permettono di eseguire potenti analisi sui grafi. Questo post del blog si concentra su come utilizzare gli algoritmi integrati in networkx.

Percorso più breve

Il percorso più breve tra due nodi in un grafico è il modo più veloce per viaggiare dal nodo iniziale al nodo finale.

Utilizziamo l’algoritmo del percorso più breve per calcolare il modo più veloce per andare da root a e.

nx.shortest_path(graph, 'root', 'e') # => 

Si potrebbe anche andare da root => a => b => d => e per andare da root a e, ma sarebbe più lungo.

Percorso più lungo

Il metodo dag_longest_path restituisce il percorso più lungo in un DAG.

nx.dag_longest_path(graph) # => 

Ordinamento topologico

I nodi in un DAG possono essere ordinati topologicamente in modo che per ogni bordo diretto uv dal nodo u al nodo v, u viene prima di v nell’ordinamento.

Il nostro grafico ha nodi (a, b, c, ecc.) e bordi diretti (ab, bc, bd, de, ecc.). Ecco un paio di requisiti che il nostro ordinamento topologico deve soddisfare:

• per ab, a deve venire prima di b nell’ordinamento
• per bc, b deve venire prima di c
• per bd, b deve venire prima di d
• per de, d deve venire prima di e

Facciamo funzionare l’algoritmo e vediamo se tutti i nostri requisiti sono soddisfatti:

list(nx.topological_sort(graph)) # => 

Osservate che a viene prima di b, b viene prima di c, b viene prima di d, e d viene prima di e. L’ordinamento topologico soddisfa tutti i requisiti di ordinamento.

Controllo della validità

Possiamo controllare che il grafo sia diretto.

nx.is_directed(graph) # => True

Possiamo anche assicurarci che sia un grafo aciclico diretto.

nx.is_directed_acyclic_graph(graph) # => True

Grafo diretto non aciclico

Facciamo un grafo che sia diretto, ma non aciclico. Un “grafo non aciclico” è più comunemente chiamato “grafo ciclico”.

graph = nx.DiGraph()graph.add_edges_from()nx.is_directed(graph) # => Truenx.is_directed_acyclic_graph(graph) # => False

Un grafo aciclico è quando un nodo non può raggiungere se stesso. Questo grafico non è aciclico perché i nodi possono raggiungere se stessi (per esempio 3 può fare questo viaggio 3 => 4 => 1 => 2 => 3 e tornare a se stesso.

I grafi diretti che non sono aciclici non possono essere ordinati topologicamente.

list(nx.topological_sort(graph)) # throws this error - networkx.exception.NetworkXUnfeasible: Graph contains a cycle or graph changed during iteration

Ripercorriamo i requisiti di ordinamento topologico ed esaminiamo perché i grafi diretti ciclici non possono essere ordinati topologicamente. Il nostro grafico ha i nodi 1, 2, 3, 4 e i bordi diretti 12, 23, 34 e 41. Ecco i requisiti per l’ordinamento topologico:

• per 12, 1 deve venire prima di 2 nell’ordinamento
• per 23, 2 deve venire prima di 3
• per 34, 3 deve venire prima di 4
• per 41, 4 deve venire prima di 1

I primi tre requisiti sono facili da soddisfare e possono essere soddisfatti con un ordinamento 1, 2, 3. Ma l’ultimo requisito è impossibile da soddisfare. 4 deve essere prima di 1, ma 4, 1, 2, 3 non è possibile perché 3 deve venire prima di 4.

L’ordinamento topologico dei grafi ciclici è impossibile.

Grafo che non è né diretto né aciclico

Finora abbiamo usato la classe DiGraph per fare grafi che sono diretti. Puoi usare la classe Graph per fare grafi indiretti. Tutti i bordi in un grafo indiretto sono bidirezionali, quindi le frecce non sono necessarie nelle rappresentazioni visive dei grafi indiretti.

graph = nx.Graph()graph.add_edges_from()nx.is_directed(graph) # => Falsenx.is_directed_acyclic_graph(graph) # => False

È necessario utilizzare algoritmi diversi quando si interagisce con grafi bidirezionali. Rimanete con i DAG mentre iniziate 😉

Radici multiple

Un DAG può avere più nodi radice.

graph = nx.DiGraph()graph.add_edges_from()nx.is_directed(graph) # => Truenx.is_directed_acyclic_graph(graph) # => Truelist(nx.topological_sort(graph)) # => 

Un grafico diretto può avere più ordinamenti topologici validi. m, n, o, p, q è un altro modo per ordinare topologicamente questo grafico.

Grafico di un DAG

E’ facile visualizzare i grafici networkx con matplotlib.

Ecco come possiamo visualizzare il primo DAG di questo post:

from matplotlib import pyplot as pltg1 = nx.DiGraph()g1.add_edges_from()plt.tight_layout()nx.draw_networkx(g1, arrows=True)plt.savefig("g1.png", format="PNG")# tell matplotlib you're done with the plot: https://stackoverflow.com/questions/741877/how-do-i-tell-matplotlib-that-i-am-done-with-a-plotplt.clf()

Ecco come visualizzare il nostro grafico diretto e ciclico.

g2 = nx.DiGraph()g2.add_edges_from()plt.tight_layout()nx.draw_networkx(g2, arrows=True)plt.savefig("g2.png", format="PNG")plt.clf()

Passi successivi

Ora che hai familiarità con i DAG e puoi vedere come sono facili da creare e gestire con networkx, puoi facilmente iniziare ad incorporare questa struttura dati nei tuoi progetti.

Ho recentemente creato un progetto chiamato unicron che modella le trasformazioni di PySpark in un DAG, per dare agli utenti un’interfaccia elegante per eseguire funzioni dipendenti dall’ordine. Sarete in grado di fare belle astrazioni come queste quando sarete a vostro agio con la struttura dati DAG.

Scoprite questo post sul blog su come impostare un progetto PySpark con Poetry se siete interessati a imparare come elaborare massicci set di dati con PySpark e utilizzare algoritmi di rete in scala.