MungingData

Az irányított aciklikus gráfok (DAG) az adattudomány / adatmérnöki munkafolyamatok kritikus adatszerkezete. A DAG-okat széles körben használják olyan népszerű projektek, mint az Apache Airflow és az Apache Spark.

Ez a blogbejegyzés megtanítja, hogyan lehet DAG-ot építeni Pythonban a networkx könyvtár segítségével, és fontos gráf algoritmusokat futtatni.

Mihelyt megbarátkozol a DAG-okkal, és látod, milyen könnyű velük dolgozni, mindenféle olyan elemzést találsz, amely jó jelölt a DAG-okhoz. A DAG-ok ugyanolyan fontosak, mint az olyan adatszerkezetek, mint a szótárak és a listák számos elemzéshez.

Egyszerű példa

Megfontolandó a következő DAG:

gyökér, a, b, c, d és e csomópontoknak nevezzük. A csomópontokat összekötő nyilakat éleknek nevezzük. A gráf olyan csomópontok gyűjteménye, amelyeket élek kötnek össze. Az irányított aciklikus gráf a gráf egy speciális típusa, amelynek tulajdonságait ebben a bejegyzésben ismertetjük.

Íme, hogyan tudjuk a networkx könyvtár segítségével felépíteni a mintagráfunkat.

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

DiGraph a “directed graph” rövidítése.

Az irányított gráfot a csomópontokat összekötő tuplik listájaként modellezzük. Ne feledjük, hogy ezeket a kapcsolatokat a gráf nomenklatúrájában “éleknek” nevezzük. Nézze meg még egyszer a gráf képét, és figyelje meg, hogy a add_edges_from minden argumentuma megegyezik a gráfban lévő nyilakkal.

Anetworkx elég okos ahhoz, hogy az élek gyűjteményéből következtessen a csomópontokra.

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

Az algoritmusok segítségével hatékony elemzéseket végezhet gráfokon. Ez a blogbejegyzés a networkx beépített algoritmusainak használatára összpontosít.

Legkisebb út

A gráf két csomópontja közötti legrövidebb út a kezdőcsomópontból a végcsomópontba vezető leggyorsabb út.

Használjuk a legrövidebb út algoritmust, hogy kiszámítsuk a legrövidebb utat a gyökértől e-ig.

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

A gyökér => a => b => d => e-től is eljuthatnánk e-ig, de az hosszabb lenne.

Leghosszabb út

A dag_longest_path módszer visszaadja a DAG leghosszabb útját.

nx.dag_longest_path(graph) # => 

Topológiai rendezés

A DAG csomópontjai topológiailag úgy rendezhetők, hogy az u csomópontból a v csomópontba vezető minden uv irányított él esetén a rendezésben u a v előtt áll.

Gráfunknak vannak csomópontjai (a, b, c, stb.) és irányított élei (ab, bc, bd, de, stb.). Íme néhány követelmény, aminek a topológiai rendezésünknek meg kell felelnie:

• az ab esetében a-nak b elé kell kerülnie a sorrendben
• a bc esetében b-nek c elé kell kerülnie
• a bd esetében b-nek d elé kell kerülnie
• a de esetében d-nek e elé kell kerülnie

Futtassuk le az algoritmust, és nézzük meg, hogy minden követelményünk teljesül-e:

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

Nézzük meg, hogy a jön b előtt, b jön c előtt, b jön d előtt, és d jön e előtt. A topológiai rendezés minden sorrendezési követelménynek megfelel.

Az érvényesség ellenőrzése

Ellenőrizhetjük, hogy a gráf irányított-e.

nx.is_directed(graph) # => True

Azt is ellenőrizhetjük, hogy irányított aciklikus gráf-e.

nx.is_directed_acyclic_graph(graph) # => True

Állított gráf, ami nem aciklikus

Készítsünk egy olyan gráfot, ami irányított, de nem aciklikus. A “nem aciklikus gráfot” gyakrabban “ciklikus gráfnak” nevezik.

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

Az aciklikus gráfról akkor beszélünk, ha egy csomópont nem érheti el önmagát. Ez a gráf azért nem aciklikus, mert a csomópontok elérhetik önmagukat (például 3 megteheti ezt az utat 3 => 4 => 1 => 2 => 3 és visszaérkezhet önmagához.

A nem aciklikus irányított gráfok nem rendezhetők topológiailag.

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

Nézzük újra a topológiai rendezés követelményeit és vizsgáljuk meg, miért nem rendezhetők topológiailag a ciklikus irányított gráfok. A gráfunknak 1, 2, 3, 4 csomópontjai és 12, 23, 34 és 41 irányított élei vannak. Íme a topológiai rendezés követelményei:

• 12 esetében az 1-nek a 2 előtt kell állnia a sorrendben
• 23 esetében a 2-nek a 3 előtt kell állnia
• 34 esetében a 3-nak a 4 előtt kell állnia
• 41 esetében a 4-nek az 1 előtt kell állnia

Az első három követelmény könnyen teljesíthető, és kielégíthető az 1, 2, 3 rendezéssel. Az utolsó követelményt azonban lehetetlen teljesíteni. A 4-nek az 1 előtt kell lennie, de a 4, 1, 2, 3 nem lehetséges, mert a 3-nak a 4 elé kell kerülnie.

Ciklikus gráfok topológiai rendezése lehetetlen.

Gráf, amely sem nem irányított, sem nem aciklikus

Eddig a DiGraph osztályt használtuk irányított gráfok előállítására. Az Graph osztályt használhatjuk irányítatlan gráfok készítésére. Egy nem irányított gráfban minden él kétirányú, ezért a nem irányított gráfok vizuális ábrázolásában nincs szükség nyilakra.

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

A kétirányú gráfokkal való interakció során más algoritmusokat kell használnunk. Maradj a DAG-oknál, amíg elkezded 😉

Multiple roots

Egy DAG-nak több gyökércsomópontja is lehet.

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

Egy irányított gráfnak több érvényes topológiai rendezése is lehet. m, n, o, p, q egy másik módja a gráf topológiai rendezésének.

DAG gráf ábrázolása

Hálózatix gráfokat könnyen vizualizálhatunk a matplotlib segítségével.

Íme, így vizualizálhatjuk az első DAG-ot ebből a blogbejegyzésből:

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

Íme, így vizualizálhatjuk az irányított, ciklikus gráfunkat.

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

Következő lépések

Most, hogy már ismered a DAG-okat, és látod, milyen könnyű létrehozni és kezelni őket a networkx segítségével, könnyen elkezdheted beépíteni ezt az adatszerkezetet a projektjeidbe.

Nemrég létrehoztam egy unicron nevű projektet, amely a PySpark transzformációkat egy DAG-ban modellezi, hogy a felhasználóknak egy elegáns felületet adjon a rendfüggő függvények futtatásához. Képes leszel ilyen szép absztrakciókat létrehozni, ha már jól ismered a DAG adatszerkezetet.

Nézd meg ezt a blogbejegyzést egy PySpark projekt beállításáról a Poetry-vel, ha érdekel, hogyan lehet hatalmas adathalmazokat feldolgozni a PySparkkal és networkx algoritmusokat használni méretarányosan.