MungingData

Directed Acyclic Graphs (DAG-uri) sunt o structură de date critică pentru fluxurile de lucru din domeniul științei datelor / ingineriei datelor. DAG-urile sunt utilizate pe scară largă de proiecte populare precum Apache Airflow și Apache Spark.

Acest articol de blog vă va învăța cum să construiți un DAG în Python cu biblioteca networkx și să rulați algoritmi importanți de graf.

După ce vă simțiți confortabil cu DAG-urile și vedeți cât de ușor este să lucrați cu ele, veți găsi tot felul de analize care sunt candidați buni pentru DAG-uri. DAG-urile sunt la fel de importante ca și structurile de date precum dicționarele și listele pentru o mulțime de analize.

Exemplu simplu

Considerați următorul DAG:

Rădăcina, a, b, c, c, d și e sunt denumite noduri. Săgețile care leagă nodurile se numesc muchii. Un graf este o colecție de noduri care sunt conectate prin muchii. Un graf aciclic dirijat este un tip special de graf cu proprietăți care vor fi explicate în această postare.

Iată cum putem construi graful nostru de probă cu ajutorul bibliotecii networkx.

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

DiGraph este prescurtarea pentru „graf dirijat”.

Graful dirijat este modelat ca o listă de tușe care conectează nodurile. Rețineți că aceste conexiuni sunt denumite „muchii” în nomenclatura grafurilor. Priviți din nou imaginea grafului și observați cum toate argumentele la add_edges_from se potrivesc cu săgețile din graf.

networkx este suficient de inteligent pentru a deduce nodurile dintr-o colecție de muchii.

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

Algoritmii vă permit să efectuați analize puternice asupra grafurilor. Această postare pe blog se concentrează pe modul de utilizare a algoritmilor încorporați în networkx.

Calea cea mai scurtă

Calea cea mai scurtă între două noduri dintr-un graf este cea mai rapidă cale de a călători de la nodul de început la nodul final.

Să folosim algoritmul celei mai scurte căi pentru a calcula cea mai rapidă cale de a ajunge de la rădăcină la e.

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

Am putea, de asemenea, să mergem de la rădăcină => a => b => d => e pentru a ajunge de la rădăcină la e, dar ar fi mai lung.

Calea cea mai lungă

Metoda dag_longest_path returnează calea cea mai lungă dintr-un DAG.

nx.dag_longest_path(graph) # => 

Sortare topologică

Nodurile dintr-un DAG pot fi sortate topologic astfel încât pentru fiecare muchie dirijată uv de la nodul u la nodul v, u să fie înaintea lui v în ordine.

Graful nostru are noduri (a, b, c, etc.) și muchii dirijate (ab, bc, bd, de, etc.). Iată câteva cerințe pe care trebuie să le îndeplinească sortarea noastră topologică:

• pentru ab, a trebuie să fie înaintea lui b în ordine
• pentru bc, b trebuie să fie înaintea lui c
• pentru bd, b trebuie să fie înaintea lui d
• pentru de, d trebuie să fie înaintea lui e

Să rulăm algoritmul și să vedem dacă toate cerințele noastre sunt îndeplinite:

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

Observați că a vine înaintea lui b, b vine înaintea lui c, b vine înaintea lui d, iar d vine înaintea lui e. Sortarea topologică îndeplinește toate cerințele de ordonare.

Verificarea validității

Puteți verifica dacă graful este dirijat.

nx.is_directed(graph) # => True

Puteți verifica, de asemenea, dacă este un graf aciclic dirijat.

nx.is_directed_acyclic_graph(graph) # => True

Graf dirijat care nu este aciclic

Să facem un graf care este dirijat, dar nu este aciclic. Un „graf neaciclic” este mai frecvent denumit „graf ciclic”.

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

Un graf aciclic este atunci când un nod nu poate ajunge la el însuși. Acest graf nu este aciclic deoarece nodurile pot ajunge la ele însele (de exemplu 3 poate face această călătorie 3 => 4 => 1 => 2 => 3 și ajunge înapoi la el însuși.

Grafele dirijate care nu sunt aciclice nu pot fi sortate topologic.

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

Să revizuim cerințele de sortare topologică și să examinăm de ce grafurile dirijate ciclice nu pot fi sortate topologic. Graful nostru are nodurile 1, 2, 3, 4 și muchii dirijate 12, 23, 34 și 41. Iată cerințele pentru sortarea topologică:

• pentru 12, 1 trebuie să fie înaintea lui 2 în ordine
• pentru 23, 2 trebuie să fie înaintea lui 3
• pentru 34, 3 trebuie să fie înaintea lui 4
• pentru 41, 4 trebuie să fie înaintea lui 1

Primile trei cerințe sunt ușor de îndeplinit și pot fi satisfăcute cu o sortare 1, 2, 3. Dar ultima cerință este imposibil de îndeplinit. 4 trebuie să fie înaintea lui 1, dar 4, 1, 1, 2, 3 nu este posibil deoarece 3 trebuie să fie înaintea lui 4.

Sortarea topologică a grafurilor ciclice este imposibilă.

Grafic care nu este nici direcționat, nici aciclic

Am folosit până acum clasa DiGraph pentru a realiza grafuri care sunt direcționate. Puteți folosi clasa Graph pentru a realiza grafuri nedirecționate. Toate marginile dintr-un graf nedirecționat sunt bidirecționale, astfel încât săgețile nu sunt necesare în reprezentările vizuale ale grafurilor nedirecționate.

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

Trebuie să folosiți algoritmi diferiți atunci când interacționați cu grafuri bidirecționale. Rămâneți la DAG-uri cât timp începeți 😉

Rădăcini multiple

Un DAG poate avea mai multe noduri rădăcină.

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

Un graf direcționat poate avea mai multe sortări topologice valide. m, n, o, p, q este o altă modalitate de a sorta topologic acest graf.

Graficul unui DAG

Este ușor de vizualizat grafurile de rețeax cu matplotlib.

Iată cum putem vizualiza primul DAG din această postare pe blog:

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

Iată cum putem vizualiza graful nostru dirijat, ciclic.

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

Pasii următori

Acum că sunteți familiarizați cu DAG-urile și puteți vedea cât de ușor sunt de creat și de gestionat cu networkx, puteți începe cu ușurință să încorporați această structură de date în proiectele dumneavoastră.

Am creat recent un proiect numit unicron care modelează transformările PySpark într-un DAG, pentru a oferi utilizatorilor o interfață elegantă pentru rularea funcțiilor dependente de ordine. Veți putea face abstracțiuni frumoase ca acestea atunci când vă veți simți confortabil cu structura de date DAG.

Consultați această postare pe blog despre configurarea unui proiect PySpark cu Poetry dacă sunteți interesat să învățați cum să procesați seturi masive de date cu PySpark și să folosiți algoritmi networkx la scară.

.