MungingData

Directed Acyclic Graphs (DAGs) zijn een kritieke datastructuur voor data science / data engineering workflows. DAG’s worden uitgebreid gebruikt door populaire projecten zoals Apache Airflow en Apache Spark.

In deze blogpost leer je hoe je een DAG in Python kunt bouwen met de networkx-bibliotheek en belangrijke grafiekalgoritmen kunt uitvoeren.

Als je eenmaal vertrouwd bent met DAG’s en ziet hoe gemakkelijk ze zijn om mee te werken, zul je allerlei analyses vinden die goede kandidaten zijn voor DAG’s. DAGs zijn voor veel analyses net zo belangrijk als datastructuren als woordenboeken en lijsten.

Eenvoudig voorbeeld

Beschouw de volgende DAG:

wortel, a, b, c, d, en e worden nodes genoemd. De pijlen die de knooppunten met elkaar verbinden, worden randen genoemd. Een grafiek is een verzameling knooppunten die door ribben met elkaar zijn verbonden. Een gerichte acyclische grafiek is een speciaal type grafiek met eigenschappen die in dit bericht zullen worden uitgelegd.

Hier ziet u hoe we onze voorbeeldgrafiek kunnen construeren met de networkx-bibliotheek.

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

DiGraph is een afkorting voor “gerichte grafiek”.

De gerichte grafiek wordt gemodelleerd als een lijst van tupels die de knooppunten met elkaar verbinden. Onthoud dat deze verbindingen in de grafieknomenclatuur “edges” worden genoemd. Kijk nog eens naar de afbeelding van de grafiek en zie hoe alle argumenten voor add_edges_from overeenkomen met de pijlen in de grafiek.

networkx is slim genoeg om de knooppunten af te leiden uit een verzameling randen.

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

Met algoritmen kunt u krachtige analyses op grafieken uitvoeren. In deze blogpost wordt ingegaan op het gebruik van de ingebouwde algoritmen van networkx.

Kortste pad

Het kortste pad tussen twee knooppunten in een grafiek is de snelste manier om van het beginknooppunt naar het eindknooppunt te reizen.

Laten we het kortste pad-algoritme gebruiken om de snelste weg van wortel naar e te berekenen.

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

Je zou ook van wortel => a => b => d => e kunnen gaan om van wortel naar e te komen, maar dat zou langer zijn.

Langste pad

De methode dag_longest_path geeft het langste pad in een DAG.

nx.dag_longest_path(graph) # => 

Topologisch sorteren

Knooppunten in een DAG kunnen topologisch gesorteerd worden zodanig dat voor elke gerichte rand uv van knooppunt u naar knooppunt v, u voor v komt in de ordening.

Onze grafiek heeft knopen (a, b, c, enzovoort) en gerichte kanten (ab, bc, bd, de, enzovoort). Hier volgen een paar eisen waaraan onze topologische sortering moet voldoen:

• voor ab moet a voor b komen in de ordening
• voor bc, b moet voor c komen
• voor bd, b moet voor d komen
• voor de, d moet voor e komen

Laten we het algoritme uitvoeren en kijken of aan al onze eisen is voldaan:

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

Observeer dat a voor b komt, b voor c komt, b voor d komt, en d voor e komt. De topologische sortering voldoet aan alle ordeningsvereisten.

Geldigheid controleren

We kunnen controleren of de grafiek gericht is.

nx.is_directed(graph) # => True

We kunnen ook controleren of het een gerichte acyclische grafiek is.

nx.is_directed_acyclic_graph(graph) # => True

Gerichte grafiek die niet acyclisch is

Laten we eens een grafiek maken die wel gericht is, maar niet acyclisch. Een “niet acyclische grafiek” wordt gewoonlijk een “cyclische grafiek” genoemd.

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

Een acyclische grafiek is als een knooppunt zichzelf niet kan bereiken. Deze grafiek is niet acyclisch omdat knooppunten zichzelf kunnen bereiken (bijvoorbeeld 3 kan deze reis maken 3 => 4 => 1 => 2 => 3 en weer bij zichzelf uitkomen.

Gerichte grafieken die niet acyclisch zijn, kunnen niet topologisch gesorteerd worden.

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

Laten we de topologische sorteereisen nog eens bekijken en nagaan waarom cyclisch gerichte grafieken niet topologisch gesorteerd kunnen worden. Onze grafiek heeft de knopen 1, 2, 3, 4 en de gerichte ribben 12, 23, 34, en 41. Hier volgen de eisen voor topologisch sorteren:

• voor 12 moet 1 voor 2 komen in de ordening
• voor 23 moet 2 voor 3 komen
• voor 34 moet 3 voor 4 komen
• voor 41 moet 4 voor 1 komen

Aan de eerste drie eisen is gemakkelijk te voldoen en kan worden voldaan met een 1, 2, 3 sortering. Maar aan de laatste eis is onmogelijk te voldoen. 4 moet voor 1 komen, maar 4, 1, 2, 3 is niet mogelijk omdat 3 voor 4 moet komen.

Topologisch sorteren van cyclische grafieken is onmogelijk.

Grafiek die noch gericht noch acyclisch is

We hebben tot nu toe de klasse DiGraph gebruikt om grafieken te maken die gericht zijn. U kunt de klasse Graph gebruiken om ongerichte grafieken te maken. Alle randen in een ongedirigeerde grafiek zijn bidirectioneel, dus pijlen zijn niet nodig in visuele weergaven van ongedirigeerde grafieken.

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

U moet andere algoritmen gebruiken als u interactie hebt met bidirectionele grafieken. Blijf bij DAG’s terwijl je begint 😉

Meervoudige wortels

Een DAG kan meerdere wortelknopen hebben.

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

Een gerichte grafiek kan meerdere geldige topologische sorteringen hebben. m, n, o, p, q is een andere manier om deze grafiek topologisch te sorteren.

Grafiek van een DAG

Het is eenvoudig om netwerkx-grafieken te visualiseren met matplotlib.

Hier ziet u hoe we de eerste DAG uit deze blogpost kunnen visualiseren:

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

Hier ziet u hoe we onze gerichte, cyclische grafiek kunnen visualiseren.

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

Volgende stappen

Nu u bekend bent met DAG’s en kunt zien hoe eenvoudig ze te maken en te beheren zijn met networkx, kunt u eenvoudig beginnen met het opnemen van deze datastructuur in uw projecten.

Ik heb onlangs een project gemaakt genaamd unicron dat PySpark transformaties in een DAG modelleert, om gebruikers een elegante interface te geven voor het uitvoeren van opdrachtafhankelijke functies. Je zult in staat zijn om mooie abstracties zoals deze te maken wanneer je vertrouwd bent met de DAG-datastructuur.

Kijk eens naar deze blogpost over het opzetten van een PySpark-project met Poetry als je geïnteresseerd bent in het leren hoe je massieve datasets kunt verwerken met PySpark en netwerkx-algoritmen kunt gebruiken op schaal.