Rastreando o tipo de dado desaparecido

Em busca do tipo de dado ausente

• Um grafo é um conjunto de nós conectados por setas (arestas).
• Nós e arestas podem conter dados.
• Em engenharia de software, grafos aparecem de várias formas, como dependências de pacotes, links da internet, espaço de estados de software, bancos de dados relacionais, listas ligadas, árvores binárias e tabelas hash.
• Na lógica de negócios, grafos também são usados em referências de citações, redes de transporte, redes sociais etc.
• Se você trabalha com desenvolvimento de software por muito tempo, é bem provável que encontre grafos em toda parte.

Reflexões sobre o uso de grafos

• Grafos são úteis, mas usá-los em código real é algo que pesa.
• A maioria das linguagens principais não oferece suporte a grafos como tipo embutido, isso também é raro em bibliotecas padrão, e não há tantas bibliotecas de terceiros realmente robustas.
• Muitas vezes é preciso implementar o grafo por conta própria.
• Existe uma lacuna entre a frequência com que engenheiros de software podem precisar usar grafos e o suporte oferecido pelo ecossistema de programação.

Por que não existe um tipo grafo

Há escolhas demais de design

• Existem vários tipos de grafos: direcionados e não direcionados, grafos simples e multigrafos, hipergrafos, ubergrafos etc.
• Para cada tipo, é preciso decidir se nós e arestas terão IDs e que tipo de dados vão armazenar.
• Uma biblioteca de grafos perfeita, capaz de cobrir todas as possibilidades, exigiria muito tempo.
• O desempenho dos algoritmos de grafos importa, e casos especiais são importantes.
• Algoritmos de grafos são difíceis de implementar corretamente.

Há escolhas demais de implementação

• Mesmo assumindo suporte apenas a grafos direcionados simples, ainda há várias formas de representá-los internamente.
• Existem diferentes formas de armazenamento, como lista de arestas, lista de adjacência, matriz de adjacência e conjuntos de structs.
• Operações diferentes em grafos têm características de desempenho diferentes dependendo da representação.
• A representação interna ideal do grafo muda conforme ele seja esparso ou denso.
• Implementar dados de nós, dados de arestas e diferentes tipos de nós e arestas torna tudo ainda mais complexo.

Desempenho importa demais

• Muitos algoritmos de grafos resolvem problemas NP-completos ou até mais difíceis.
• Grafos podem se tornar problemas muito grandes, e o desempenho varia bastante conforme a representação e os detalhes de implementação dos algoritmos.
• É necessário ter muito controle sobre a representação dos dados e sobre os algoritmos.

Um consenso

• A variedade de tipos de grafos, representações, algoritmos, a sensibilidade a desempenho e a execução de algoritmos caros em grafos grandes ajudam a explicar por que o suporte a grafos não se espalhou tanto.
• Isso explica por que linguagens não oferecem suporte a grafos em suas bibliotecas padrão.
• Também explica por que programadores evitam bibliotecas de grafos de terceiros.
• Como usar grafos é difícil, isso explica por que, fora de situações extremas, muita gente prefere nem pensar em problemas como grafos.

Opinião do GN⁺

• Este artigo oferece uma visão sobre por que grafos não se consolidaram como um tipo de dado básico em linguagens de programação e bibliotecas.
• A teoria dos grafos é uma área importante da ciência da computação e tem aplicações em algoritmos, análise de redes, bancos de dados e várias outras áreas.
• Para usar grafos de forma eficaz, são importantes a otimização de desempenho e a escolha adequada da estrutura de dados.
• Entre as bibliotecas de terceiros estão NetworkX, Boost Graph Library e Graph-tool, que podem ser usadas para resolver vários tipos de problemas com grafos.
• Ao usar grafos, é importante escolher o tipo de grafo e o algoritmo adequados às características do problema, já que isso afeta diretamente o desempenho do sistema.

[GN⁺]

Comentários do Hacker News

• O Graphviz tem sua própria biblioteca de grafos, que não é usada por outros projetos. Essa biblioteca tem vantagens e desvantagens.

  • Com base nessa experiência, eles acabaram sofrendo da própria versão da "síndrome do segundo sistema".
  • Decidiram que uma biblioteca de grafos deveria ser modular, type-safe e eficiente. Isso pode ser uma variação de "bom, rápido e barato — escolha dois".
  • Modular significa que queriam escrever um conjunto de bibliotecas de algoritmos de grafos que pudessem ser desenvolvidas e compiladas de forma independente.
  • Type-safe significa que queriam detectar erros de programação em tempo de compilação ou, no mais tardar, em tempo de linkedição. Não queriam erros em tempo de execução.
  • Eficiência significa que acessar propriedades do grafo deveria ser tão barato quanto acessar um campo de uma struct em C.
  • É discutível se esses objetivos valiam a pena, mas era isso que eles queriam. Como criadores famosos do C++ estavam no laboratório deles, esperavam conseguir ajuda e decidiram dar mais uma chance ao C++.
  • Gordon Woodhull, um ex-estagiário, era um programador excepcional e implementou esse tipo de biblioteca de grafos em C++ com templates. Isso foi publicado via sourceforge em https://www.dynagraph.org/.
  • Como não tinham certeza se outras pessoas conseguiriam entender como o código funcionava, fizeram revisão de código com inventores famosos do C++. Perceberam que talvez tivessem passado do ponto em termos de complexidade.
  • Isso não foi culpa do Gordon, e ele continuou avançando e também realizou com sucesso trabalho de layout dinâmico de grafos no Microsoft OLE. Em retrospecto, isso pode ter sido o projeto Xanadu deles.
  • Enquanto estavam imersos nisso, surgiram muitas outras coisas, como Gephi (Java) e NetworkX e NetworKit (Python).
  • John Ellson é um engenheiro de software muito talentoso que escreveu partes do Graphviz e reviveu o esforço principal.

• Se você programa em .NET, talvez valha a pena experimentar a pequena e não muito rica em recursos biblioteca de grafos Arborescence.

  • Acredito que essa biblioteca oferece uma boa separação entre abstrações, algoritmos e estruturas de dados.
  • O usuário pode usar arestas com IDs próprios ou grafos implícitos que se expandem sob demanda.
  • Você pode usar tanto interfaces de adjacência (vizinhos de saída) quanto de incidência (arestas de saída + destino).
  • A biblioteca não impõe um tipo de aresta, mas fornece como utilitário uma estrutura básica de par cauda-cabeça.

• Grafos não são uma estrutura de dados nem um tipo de dado, mas uma abstração.

  • No essencial, tudo o que é necessário para definir um grafo é um conjunto de vértices e uma função de vizinhança.
  • Todo o resto são restrições específicas de cada caso.
  • Se considerarmos hipergrafos, um grafo é apenas um caso especial.
  • Pensando da perspectiva de banco de dados, um grafo é um problema de otimização de consultas e indexação.

• Recebi muitas perguntas sobre por que não existe um tipo de dado grafo embutido em linguagens de programação.

  • Agora fico feliz por poder apontar para análises mais profundas como este texto.

• O obstáculo central é o seguinte:

  • Para problemas de grafos simples e pequenos, é fácil o suficiente codificar uma lista de adjacência como vetor de vetores.
  • Para problemas de grafos complexos e enormes, não há como obter desempenho sem customizar a implementação do grafo para o problema.
  • Não está claro que tipo de suporte da linguagem ajudaria.

• Este texto responde em grande parte à pergunta de por que algoritmos de grafos não têm melhor suporte nas linguagens de programação.

  • Ao olhar para suporte a grafos de forma mais geral, surgem questões mais amplas, como por que OGM não é tão popular quanto ORM, por que JSON é mais amplamente usado que RDF etc.
  • No fim, por razões históricas e pela complexidade dos grafos, isso não escala bem entre desenvolvedores.

• Ferramentas de desenho de grafos também são muito decepcionantes.

  • Em grafos com mais de 500 nós, a saída fica difícil de entender ou complexa demais.
  • Falta funcionalidade para organizar automaticamente o grafo em uma estrutura hierárquica e oferecer uma boa interface para navegação.

• Este texto é realmente muito bom.

  • Quanto à observação central de que "há opções demais de implementação", na prática não é bem assim.
  • Na verdade, uma biblioteca pode implementar todas as representações de grafo adequadas.
  • É possível adaptar algoritmos à representação e converter de uma representação para outra.

• Electric Clojure usa o próprio Clojure (s-expressões) como sintaxe de autoria de grafos.

  • Uma DSL de autoria de grafos precisa expressar escopo, fluxo de controle e abstração, e isso é essencialmente o mesmo que uma linguagem de programação.

• Existe outro tipo de dado útil, como tabelas (como as tabelas dentro de um banco de dados).

  • Haveria avanço nas linguagens de programação se o compilador escolhesse a implementação da estrutura de dados.
  • Você usa estruturas abstratas (sequências, mapas, conjuntos, tabelas, grafos etc.), e o compilador escolhe a implementação concreta com base no perfil do programa.