MungingData

Směrované acyklické grafy (DAG) jsou kritickou datovou strukturou pro datovou vědu / datové inženýrství. DAGy jsou hojně využívány v populárních projektech, jako je Apache Airflow a Apache Spark.

V tomto příspěvku se naučíte vytvářet DAGy v jazyce Python pomocí knihovny networkx a spouštět důležité grafové algoritmy.

Jakmile se s DAGy seznámíte a zjistíte, jak snadno se s nimi pracuje, najdete nejrůznější analýzy, které jsou pro DAGy vhodnými kandidáty. Pro mnoho analýz jsou DAG stejně důležité jako datové struktury, jako jsou slovníky a seznamy.

Jednoduchý příklad

Považujte následující DAG:

kořen, a, b, c, d a e jsou označovány jako uzly. Šipky, které spojují uzly, se nazývají hrany. Graf je soubor uzlů, které jsou propojeny hranami. Směrovaný acyklický graf je speciální typ grafu s vlastnostmi, které budou vysvětleny v tomto příspěvku.

Podívejte se, jak můžeme zkonstruovat náš ukázkový graf pomocí knihovny networkx.

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

DiGraph je zkratka pro „směrovaný graf“.

Směrovaný graf je modelován jako seznam uzlů, které spojují uzly. Nezapomeňte, že tato spojení se v názvosloví grafů označují jako „hrany“. Podívejte se ještě jednou na obrázek grafu a všimněte si, jak se všechny argumenty příkazu add_edges_from shodují se šipkami v grafu.

networkx je dostatečně inteligentní na to, aby ze souboru hran odvodil uzly.

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

Algoritmy umožňují provádět výkonné analýzy grafů. Tento příspěvek na blogu se zaměřuje na to, jak používat vestavěné algoritmy networkx.

Nejkratší cesta

Nejkratší cesta mezi dvěma uzly v grafu je nejrychlejší cesta z počátečního uzlu do koncového.

Použijeme algoritmus nejkratší cesty k výpočtu nejrychlejší cesty z kořene do e.

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

Mohli byste také jít z kořene => a => b => d => e, abyste se dostali z kořene do e, ale to by bylo delší.

Nejdelší cesta

Metoda dag_longest_path vrací nejdelší cestu v DAG.

nx.dag_longest_path(graph) # => 

Topologické řazení

Uzly v DAG lze topologicky seřadit tak, že pro každou směrovanou hranu uv z uzlu u do uzlu v je u v řazení před v. V případě, že se jedná o uzel, který se nachází v DAG, může být tato metoda použita.

Náš graf má uzly (a, b, c atd.) a směrované hrany (ab, bc, bd, de atd.). Zde je několik požadavků, které musí naše topologické třídění splňovat:

• pro ab, a musí být v uspořádání před b
• pro bc, b musí být před c
• pro bd, b musí být před d
• pro de, d musí být před e

Pustíme algoritmus a zjistíme, zda jsou všechny naše požadavky splněny:

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

Všimněte si, že a je před b, b je před c, b je před d a d je před e. Topologické třídění splňuje všechny požadavky na uspořádání.

Kontrola platnosti

Můžeme zkontrolovat, zda je graf směrovaný.

nx.is_directed(graph) # => True

Můžeme se také ujistit, že jde o směrovaný acyklický graf.

nx.is_directed_acyclic_graph(graph) # => True

Směrovaný graf, který není acyklický

Udělejme graf, který je směrovaný, ale není acyklický. Graf, který není acyklický, se častěji označuje jako „cyklický graf“.

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

O acyklickém grafu mluvíme tehdy, když uzel nemůže dosáhnout sám sebe. Tento graf není acyklický, protože uzly mohou dosáhnout samy sebe (například 3 může podniknout tuto cestu 3 => 4 => 1 => 2 => 3 a dojít zpět k sobě samému.

Řízené grafy, které nejsou acyklické, nelze topologicky třídit.

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

Vraťme se k požadavkům na topologické třídění a prozkoumejme, proč cyklické směrované grafy nelze topologicky třídit. Náš graf má uzly 1, 2, 3, 4 a směrované hrany 12, 23, 34 a 41. V tomto grafu se nacházejí uzly 1, 2, 3, 4 a směrované hrany 1, 2, 3, 4. Zde jsou požadavky na topologické třídění:

• pro 12, 1 musí být v pořadí před 2
• pro 23, 2 musí být před 3
• pro 34, 3 musí být před 4
• pro 41, 4 musí být před 1

První tři požadavky jsou snadno splnitelné a lze je splnit tříděním 1, 2, 3. V případě, že se jedná o 1, 2, 3, je nutné, aby byly splněny. Poslední požadavek však splnit nelze. 4 musí být před 1, ale 4, 1, 2, 3 není možné, protože 3 musí být před 4.

Topologické třídění cyklických grafů je nemožné.

Graf, který není ani směrovaný, ani acyklický

Dosud jsme používali třídu DiGraph k vytváření grafů, které jsou směrované. K vytváření neorientovaných grafů můžete použít třídu Graph. Všechny hrany v neorientovaném grafu jsou obousměrné, takže ve vizuální reprezentaci neorientovaných grafů nejsou šipky potřeba.

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

Při práci s obousměrnými grafy je třeba použít jiné algoritmy. Dokud začínáte, držte se DAGů 😉

Více kořenů

DAG může mít více kořenových uzlů.

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

Směrový graf může mít více platných topologických třídění. m, n, o, p, q je další způsob, jak tento graf topologicky třídit.

Vizualizace grafu DAG

Pomocí programu matplotlib lze snadno vizualizovat grafy networkx.

Takto můžeme vizualizovat první graf DAG z tohoto příspěvku:

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

Takto můžeme vizualizovat náš směrový, cyklický 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()

Další kroky

Teď, když jste se seznámili s DAG a vidíte, jak snadno se vytvářejí a spravují pomocí networkx, můžete snadno začít tuto datovou strukturu začleňovat do svých projektů.

Nedávno jsem vytvořil projekt unicron, který modeluje transformace PySparku v DAG, aby uživatelům poskytl elegantní rozhraní pro spouštění funkcí závislých na pořadí. Takové pěkné abstrakce budete moci vytvářet, až se s datovou strukturou DAG sžijete.

Podívejte se na tento příspěvek na blogu o nastavení projektu PySpark s Poetry, pokud vás zajímá, jak zpracovávat obrovské datové sady pomocí PySparku a používat algoritmy networkx ve velkém měřítku.