MungingData

Riktade acykliska grafer (DAGs) är en kritisk datastruktur för datavetenskap och datatekniska arbetsflöden. DAGs används flitigt av populära projekt som Apache Airflow och Apache Spark.

Detta blogginlägg kommer att lära dig att bygga en DAG i Python med networkx-biblioteket och köra viktiga algoritmer för grafer.

När du väl känner dig bekväm med DAGs och ser hur enkla de är att arbeta med, kommer du att hitta alla typer av analyser som är bra kandidater för DAGs. DAGs är lika viktiga som datastrukturer som ordböcker och listor för många analyser.

Enkel exempel

Tänk på följande DAG:

Rot, a, b, c, d och e kallas noder. Pilarna som förbinder noderna kallas för kanter. En graf är en samling noder som är sammankopplade med kanter. En riktad acyklisk graf är en speciell typ av graf med egenskaper som kommer att förklaras i det här inlägget.

Här ser du hur vi kan konstruera vår exempelgraf med networkx-biblioteket.

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

DiGraph är en förkortning för ”directed graph”.

Den riktade grafen modelleras som en lista med tupler som förbinder noderna. Kom ihåg att dessa förbindelser kallas ”kanter” i grafenomenklaturen. Ta en ny titt på grafbilden och observera hur alla argument till add_edges_from stämmer överens med pilarna i grafen.

networkx är tillräckligt smart för att härleda noderna från en samling kanter.

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

Algoritmer gör att du kan utföra kraftfulla analyser på grafer. Det här blogginlägget fokuserar på hur du använder de inbyggda networkx-algoritmerna.

Kortsta vägen

Den kortaste vägen mellan två noder i en graf är det snabbaste sättet att resa från startnoden till slutnoden.

Låt oss använda algoritmen för kortaste vägen för att beräkna den snabbaste vägen från roten till e.

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

Du skulle också kunna gå från roten => a => b => d => e för att komma från roten till e, men det skulle bli längre.

Längsta vägen

Metoden dag_longest_path returnerar den längsta vägen i en DAG.

nx.dag_longest_path(graph) # => 

Topologisk sortering

Noderna i en DAG kan vara topologiskt sorterade på så sätt att för varje riktad kant uv från nod u till nod v, kommer u före v i ordningen.

Vår graf har noder (a, b, c, etc.) och riktade kanter (ab, bc, bd, de, etc.). Här är ett par krav som vår topologiska sortering måste uppfylla:

• För ab måste a komma före b i ordningen
• För bc måste b komma före c
• För bd måste b komma före d
• För de måste d komma före e

Låt oss köra algoritmen och se om alla våra krav är uppfyllda:

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

Observera att a kommer före b, b kommer före c, b kommer före d och d kommer före e. Den topologiska sorteringen uppfyller alla ordningskrav.

Kontroll av giltighet

Vi kan kontrollera att grafen är riktad.

nx.is_directed(graph) # => True

Vi kan också kontrollera att det är en riktad acyklisk graf.

nx.is_directed_acyclic_graph(graph) # => True

Riktad graf som inte är acyklisk

Låt oss göra en graf som är riktad, men inte acyklisk. En ”inte acyklisk graf” kallas vanligen för en ”cyklisk graf”.

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

En acyklisk graf är när en nod inte kan nå sig själv. Den här grafen är inte acyklisk eftersom noder kan nå sig själva (till exempel kan 3 ta den här resan 3 => 4 => 1 => 2 => 3 och komma tillbaka till sig själv.

Dirigerade grafer som inte är acykliska kan inte topologiskt sorteras.

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

Låtsas vi återgå till de topologiska sorteringskraven och undersöka varför cykliska riktade grafer inte kan topologiskt sorteras. Vår graf har noderna 1, 2, 3, 4 och riktade kanter 12, 23, 34 och 41. Här är kraven för topologisk sortering:

• för 12 måste 1 komma före 2 i ordningen
• för 23 måste 2 komma före 3
• för 34 måste 3 komma före 4
• för 41 måste 4 komma före 1

De tre första kraven är lätta att uppfylla och kan tillgodoses med en 1, 2, 3 sortering. Men det sista kravet är omöjligt att uppfylla. 4 måste komma före 1, men 4, 1, 2, 3 är inte möjligt eftersom 3 måste komma före 4.

Topologisk sortering av cykliska grafer är omöjlig.

Graft som varken är riktad eller acyklisk

Vi har hittills använt klassen DiGraph för att göra grafer som är riktade. Du kan använda klassen Graph för att göra oriktade grafer. Alla kanter i en odirigerad graf är dubbelriktade, så pilar behövs inte i visuella representationer av odirigerade grafer.

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

Du måste använda olika algoritmer när du interagerar med dubbelriktade grafer. Håll dig till DAGs när du kommer igång 😉

Flera rötter

En DAG kan ha flera rotnoder.

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

En riktad graf kan ha flera giltiga topologiska sorteringar. m, n, o, p, q är ett annat sätt att topologiskt sortera denna graf.

Graphing a DAG

Det är lätt att visualisera networkx grafer med matplotlib.

Här är hur vi kan visualisera den första DAG:n från det här blogginlägget:

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()

Här är hur vi visualiserar vår riktade, cykliska graf.

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

Nästa steg

Nu när du är bekant med DAGs och kan se hur enkla de är att skapa och hantera med networkx kan du enkelt börja införliva den här datastrukturen i dina projekt.

Jag har nyligen skapat ett projekt som heter unicron och som modellerar PySpark-transformationer i en DAG, för att ge användarna ett elegant gränssnitt för att köra orderberoende funktioner. Du kommer att kunna göra fina abstraktioner som dessa när du känner dig bekväm med DAG-datastrukturen.

Kolla in det här blogginlägget om hur man sätter upp ett PySpark-projekt med Poetry om du är intresserad av att lära dig hur man bearbetar massiva datamängder med PySpark och använder nätverksalgoritmer i stor skala.