Exemplos de implementação de algoritmos em grafos em softwares diversos

Pequena lista com exemplos de algoritmos de busca utilizados internamente em projetos de software de código aberto

AlgoritmoSoftwareDescrição do uso do algoritmoCódigo-fonte
Busca em largura (BFS)LinuxO kernel do Linux utiliza uma busca em largura no subsistema lockdep, responsável por verificar a correção do uso de bloqueios (locks) no kernel. O algoritmo percorre o grafo direcionado de dependências entre classes de bloqueios para determinar se uma nova dependência pode introduzir um ciclo, indicando um possível deadlock. A BFS também permite encontrar caminhos curtos de dependência, facilitando o diagnóstico desses problemas.lockdep.c
Busca em largura (BFS)PostgreSQLO PostgreSQL, um dos principais sistemas gerenciadores de bancos de dados relacionais de código aberto, utiliza uma busca em largura na extensão pg_trgm, que acelera consultas textuais por meio de índices de trigramas. O algoritmo percorre estados de um autômato associado a uma expressão regular, auxiliando a construção de uma representação que permite identificar quais trigramas são relevantes para a consulta.trgm_regexp.c
Busca em profundidade (DFS) — detecção de ciclosLinuxO kernel do Linux utiliza uma busca em profundidade no verificador de programas eBPF, tecnologia que permite executar programas controlados dentro do kernel, por exemplo, para monitoramento e processamento de pacotes de rede. A DFS percorre o grafo de fluxo de controle do programa e identifica ciclos que precisam ser considerados na verificação de segurança antes que o programa possa ser executado.cfg.c
Busca em profundidade (DFS) — detecção de ciclosGNU MakeO GNU Make é uma ferramenta amplamente utilizada para automatizar a compilação de programas. Ele organiza os alvos e suas dependências em um grafo direcionado, percorrido recursivamente para determinar quais alvos precisam ser atualizados. Durante esse percurso, identifica quando uma dependência aponta para um alvo que já está ativo na cadeia de chamadas, detectando uma dependência circular. Nesse caso, emite um aviso e descarta a dependência. Esse mecanismo corresponde à detecção de ciclos por uma exploração recursiva do tipo DFS.remake.c
Ordenação topológica — Busca em profundidade (DFS)APT (apt-get)O APT é o sistema de gerenciamento de pacotes utilizado em distribuições Linux como Debian e Ubuntu. Ele representa as dependências entre pacotes por um grafo direcionado e utiliza uma exploração recursiva baseada em DFS para determinar a ordem das operações de instalação, configuração e remoção de pacotes. O algoritmo considera diferentes tipos de dependência e identifica ciclos, que exigem tratamento especial para permitir a execução dessas operações.orderlist.cc
Ordenação topológica — Busca em profundidade (DFS)ChromiumO Chromium, projeto de código aberto que serve de base para navegadores como Google Chrome e Microsoft Edge, utiliza ordenação topológica no processamento de grafos WebNN. Esses grafos representam operações de redes neurais e suas dependências. Uma DFS determina uma ordem na qual cada operação aparece depois das operações das quais depende, permitindo processar corretamente o grafo de computação.ml_graph_utils.cc
Ordenação topológica — variante do Algoritmo de KahnGitO Git, sistema de controle de versões amplamente utilizado no desenvolvimento de software, representa o histórico de commits por um grafo direcionado acíclico, no qual as arestas registram relações de ancestralidade. O algoritmo utiliza graus de entrada e uma fila de prioridade para produzir uma ordenação topológica dos commits, garantindo que as relações de dependência entre eles sejam respeitadas durante a apresentação e o processamento do histórico.commit.c
Caminho máximo em DAGLLVMO LLVM, infraestrutura de compiladores utilizada por projetos como Clang (C/C++), Rust e Swift, representa dependências entre instruções por um grafo direcionado acíclico. O algoritmo calcula comprimentos de caminhos críticos, considerando as latências das instruções. Essas informações ajudam o escalonador a priorizar instruções cuja execução pode influenciar mais fortemente o tempo total de processamento.ScheduleDAG.cpp
Caminho máximo em DAGNinjaO Ninja é um sistema de automação de compilação utilizado em grandes projetos, incluindo o Chromium. Ele representa as tarefas de compilação e suas dependências por um DAG. O algoritmo calcula o caminho crítico desse grafo, utilizando durações registradas de execuções anteriores ou pesos estimados. O resultado auxilia na priorização das tarefas, favorecendo aquelas que podem determinar o tempo total da compilação.build.cc
Componentes fortemente conexas — variante iterativa do algoritmo de TarjanLinuxO kernel do Linux utiliza uma variante iterativa do algoritmo de Tarjan na análise de programas eBPF. O algoritmo identifica componentes fortemente conexas no grafo de fluxo de controle, agrupando instruções que podem alcançar umas às outras. Essas componentes permitem reconhecer regiões cíclicas do programa e fornecem informações utilizadas pelo verificador na análise de sua execução.cfg.c
Componentes fortemente conexas — KosarajuGCCO GCC, uma das principais coleções de compiladores de código aberto, utiliza o algoritmo de Kosaraju para identificar componentes fortemente conexas no grafo de fluxo de controle de funções. O algoritmo realiza duas buscas em profundidade e fornece informações empregadas na análise de laços irredutíveis, regiões cíclicas do fluxo de controle que não possuem a estrutura usual de um laço com uma única entrada.graphds.cc
Componentes fortemente conexas — TarjanCMakeO CMake é um sistema de configuração e geração de projetos de compilação, amplamente utilizado em software C e C++. Ele representa as dependências entre alvos de compilação por um grafo direcionado. O algoritmo de Tarjan identifica componentes fortemente conexas nesse grafo, permitindo reconhecer ciclos de dependência, especialmente entre bibliotecas estáticas, e construir um grafo acíclico de componentes para organizar a compilação.cmComputeComponentGraph.cxx
DijkstraFRRoutingO FRRouting é uma plataforma de roteamento de código aberto utilizada em redes de computadores, com suporte a protocolos como OSPF e BGP. Na implementação do OSPF, o algoritmo de Dijkstra calcula uma árvore de caminhos mínimos a partir do roteador local, utilizando os custos associados às conexões da rede. Essa árvore é utilizada para determinar os melhores caminhos até os destinos e atualizar as informações de roteamento.ospf_spf.c
DijkstraGraphHopperO GraphHopper é um mecanismo de cálculo de rotas geográficas utilizado em aplicações de navegação e logística. Ele representa a malha viária por um grafo cujos vértices correspondem a posições da rede e cujas arestas representam trechos de vias. O algoritmo de Dijkstra encontra caminhos de custo mínimo entre origem e destino, considerando pesos associados às vias, como distância ou tempo de viagem, conforme o modelo de roteamento.Dijkstra.java
Variante dos Algoritmos de Prim e DijkstraOpenROADO OpenROAD é uma plataforma de automação de projeto de circuitos integrados, utilizada para transformar descrições digitais em layouts físicos de chips. Na construção de interconexões elétricas, utiliza uma variante dos algoritmos de Prim e Dijkstra para produzir árvores de Steiner retilíneas. A construção procura equilibrar o comprimento total dos fios e as distâncias entre a origem do sinal e seus destinos, fatores importantes para a área e o desempenho do circuito.SteinerTreeBuilder.cpp
Vértices de corte — Busca em profundidade (DFS) com lowpointGRASS GISO GRASS GIS é um sistema de informação geográfica de código aberto utilizado em análise espacial e geoprocessamento. Sua biblioteca de análise de redes implementa uma busca em profundidade com valores de descoberta e lowpoint para identificar vértices de articulação. Em uma rede geográfica, esses vértices representam pontos cuja remoção pode desconectar partes da rede, informação útil para analisar sua vulnerabilidade e conectividade.articulation_point.c
Aresta de corte — Busca em profundidade (DFS) com lowpointGRASS GISO GRASS GIS também implementa a identificação de arestas de corte em grafos que representam redes geográficas, como redes de transporte. O algoritmo utiliza uma DFS e valores de lowpoint para encontrar arestas cuja remoção aumenta o número de componentes conexas. Essa funcionalidade é disponibilizada pelo módulo v.net.bridge, permitindo identificar conexões críticas para a manutenção da conectividade de uma rede.bridge.c

Mais exemplos de algoritmos para problemas em grafos

Mais exemplos de algoritmos para problemas em grafos utilizados internamente em projetos de software de código aberto.

AlgoritmoSoftwareDescrição do uso do algoritmoCódigo-fonte
Coloração de grafos — variante de Chaitin–BriggsGCCO GCC, uma das principais coleções de compiladores de código aberto, utiliza coloração de grafos na alocação de registradores do processador. O compilador constrói um grafo de interferência, no qual vértices representam valores que precisam ser armazenados e arestas indicam que dois valores não podem ocupar o mesmo registrador. Uma heurística baseada em Chaitin–Briggs procura atribuir registradores aos vértices, recorrendo ao armazenamento em memória quando necessário ou vantajoso segundo os custos considerados pelo alocador.ira-color.cc
Coloração de grafos — alocação de registradoresMesa 3DO Mesa 3D é uma importante implementação de código aberto de APIs gráficas, como OpenGL e Vulkan, e inclui compiladores de shaders para diferentes GPUs. Na alocação de registradores, utiliza uma heurística de coloração do grafo de interferência para atribuir registradores aos valores intermediários dos programas executados pela GPU. O algoritmo considera classes de registradores e restrições de sobreposição específicas do hardware. Uma tentativa de alocação pode falhar sem que isso demonstre a inexistência de uma coloração válida.register_allocate.c