MungingData

Gráficos Acíclicos Dirigidos (DAGs) são uma estrutura de dados crítica para a ciência dos dados / fluxos de trabalho de engenharia de dados. DAGs são usados extensivamente por projetos populares como Apache Airflow e Apache Spark.

Este post no blog irá ensiná-lo como construir um DAG em Python com a biblioteca networkx e executar algoritmos de gráficos importantes.

Após você estar confortável com DAGs e ver como eles são fáceis de trabalhar, você encontrará todo tipo de análises que são bons candidatos para DAGs. DAGs são tão importantes quanto estruturas de dados como dicionários e listas para muitas análises.

Simples exemplo

Considerar o seguinte DAG:

root, a, b, c, d, e e são referidos como nós. As setas que ligam os nós são chamadas de bordas. Um gráfico é um conjunto de nós que são conectados por arestas. Um gráfico acíclico dirigido é um tipo especial de gráfico com propriedades que serão explicadas neste post.

Aqui está como podemos construir nosso gráfico de exemplo com a biblioteca networkx.

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

DiGraph é a abreviação de “gráfico dirigido”.

O gráfico dirigido é modelado como uma lista de tuplos que conectam os nós. Lembre-se que estas conexões são referidas como “bordas” na nomenclatura do gráfico. Dê outra olhada na imagem do gráfico e observe como todos os argumentos para add_edges_from coincidem com as setas no gráfico.

networkx é inteligente o suficiente para inferir os nós de uma coleção de arestas.

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

Algoritmos permitem que você realize análises poderosas nos gráficos. Este post do blog foca em como usar os algoritmos embutidos do networkx.

Shortest path

O caminho mais curto entre dois nós em um gráfico é a maneira mais rápida de viajar do nó inicial ao nó final.

Vamos usar o algoritmo de caminho mais curto para calcular o caminho mais rápido para ir da raiz para e.

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

Você também poderia ir da raiz => a => b => d => e para ir da raiz para e, mas isso seria mais longo.

Caminho mais longo

O método dag_longest_path devolve o caminho mais longo em um DAG.

nx.dag_longest_path(graph) # => 

Seleção Topológica

Nós em um DAG podem ser ordenados topologicamente de tal forma que para cada borda dirigida uv de nó u para nó v, u vem antes de v na ordenação.

Nosso gráfico tem nós (a, b, c, etc.) e arestas direcionadas (ab, bc, bd, de, etc.). Aqui estão alguns requisitos que nosso tipo topológico precisa satisfazer:

• para ab, a precisa vir antes de b na ordenação
• para bc, b precisa vir antes de c
• para bd, b precisa vir antes de d
• para de, d precisa vir antes de e

Passemos a executar o algoritmo e ver se todos os nossos requisitos são satisfeitos:

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

Observe que a vem antes de b, b vem antes de c, b vem antes de d, e d vem antes de e. O tipo topológico satisfaz todos os requisitos de ordenação.

Verificando a validade

Podemos verificar se o gráfico é dirigido.

nx.is_directed(graph) # => True

Podemos também verificar se é um gráfico acíclico dirigido.

nx.is_directed_acyclic_graph(graph) # => True

Gráfico dirigido que não é acíclico

Vamos fazer um gráfico que é dirigido, mas não acíclico. Um “gráfico não acíclico” é mais comumente referido como um “gráfico cíclico”.

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

Um gráfico acíclico é quando um nó não consegue alcançar a si mesmo. Este gráfico não é acíclico porque os nós podem alcançar a si mesmos (por exemplo 3 podem fazer esta viagem 3 => 4 => 1 => 2 => 3 e chegar de volta a si mesmos.

Gráficos orientados que não são acíclicos não podem ser classificados topologicamente.

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

Vamos revisitar os requisitos de classificação topológica e examinar porque os gráficos orientados ciclicamente não podem ser classificados topologicamente. Nosso gráfico tem nós 1, 2, 3, 4 e bordas direcionadas 12, 23, 34, e 41. Aqui estão os requisitos para classificação topológica:

• para 12, 1 precisa vir antes de 2 na ordenação
• para 23, 2 precisa vir antes de 3
• para 34, 3 precisa vir antes de 4
• para 41, 4 precisa vir antes de 1

Os três primeiros requisitos são fáceis de cumprir e podem ser satisfeitos com uma ordenação 1, 2, 3. Mas o requisito final é impossível de cumprir. 4 precisa ser antes de 1, mas 4, 1, 2, 3 não é possível porque 3 precisa vir antes de 4.

Topologicamente ordenar gráficos cíclicos é impossível.

Gráfico que não é dirigido nem acíclico

Estamos usando a classe DiGraph para fazer gráficos que são dirigidos até agora. Você pode usar a classe Graph para fazer gráficos não direcionados. Todas as bordas em um gráfico não direcionado são bidirecionais, então setas não são necessárias em representações visuais de gráficos não direcionados.

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

Você precisa usar algoritmos diferentes ao interagir com gráficos bidirecionais. Fique com DAGs enquanto você está começando 😉

Raízes múltiplas

Um DAG pode ter múltiplos nós raiz.

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

Um gráfico direcionado pode ter múltiplos tipos topológicos válidos. m, n, o, p, q é outra maneira de ordenar topologicamente este gráfico.

Grafar um DAG

É fácil visualizar gráficos networkx com matplotlib.

Aqui está como podemos visualizar o primeiro DAG deste blog post:

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

Aqui está como podemos visualizar o nosso gráfico cíclico dirigido.

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

Passos seguintes

Agora que você está familiarizado com DAGs e pode ver como eles são fáceis de criar e gerenciar com networkx, você pode facilmente começar a incorporar esta estrutura de dados em seus projetos.

Criei recentemente um projeto chamado unicron que modela transformações PySpark em um DAG, para dar aos usuários uma interface elegante para executar funções dependentes de ordem. Você será capaz de fazer abstrações legais como estas quando você estiver confortável com a estrutura de dados do DAG.

Check out this blog post on setting up a PySpark project with Poetry if you’re interested in learn how to process massive dataets with PySpark and use networkx algorithms at scale.