Rastreando o tipo de dado desaparecido
(hillelwayne.com)- Grafos estão por toda parte no software, como em dependências, links da web, espaços de estado de model checkers e chaves estrangeiras de bancos de dados relacionais, mas linguagens de programação mainstream quase não oferecem tipos embutidos nem suporte em biblioteca padrão
- O primeiro motivo para ser difícil criar um tipo de grafo embutido é a grande variedade de tipos de grafo, como direcionado ou não direcionado, simples ou multigrafo, e hipergrafo, além de propriedades específicas mudarem bastante a escolha do algoritmo e o desempenho
- Em formas de representação como lista de arestas, lista de adjacência, matriz de adjacência e structs com referências, uso de memória e desempenho de consulta variam, o que dificulta satisfazer todos os casos de uso com uma representação genérica única
- Algoritmos de grafos são difíceis de implementar e costumam rodar sobre entradas grandes, então, como nos casos de Nosey Parker e Gecode, representações e travessias ajustadas ao problema podem ser mais importantes do que bibliotecas genéricas
- Grafos são raros em bibliotecas padrão porque os trade-offs de tipo, representação, algoritmo e desempenho, além da carga de manutenção, são altos; mesmo bibliotecas de terceiros podem ser limitadas ou lentas
Grafos são comuns, mas o suporte nas linguagens é fraco
- Grafos são compostos por nós e arestas, e tanto nós quanto arestas podem conter dados
- Em engenharia de software, grafos aparecem de várias formas
- Dependências de pacotes e imports de módulos formam grafos direcionados
- A internet é um grafo de links entre páginas web
- Model checkers exploram o espaço de estados de todas as configurações possíveis, em que nós são estados e arestas são transições válidas
- Bancos de dados relacionais podem ser vistos com registros como nós e chaves estrangeiras como arestas
- Grafos podem ser vistos como uma generalização de listas ligadas, árvores binárias e tabelas hash
- Na lógica de negócio também aparecem com frequência grafos como relações de citação entre artigos, rotas em redes de transporte e conexões em redes sociais
- Embora grafos sejam frequentemente necessários, a maioria das linguagens mainstream não os oferece como tipo embutido, e também é raro incluí-los na biblioteca padrão
- Em muitos ecossistemas, faltam até bibliotecas de grafos de terceiros realmente robustas, então muitas vezes é preciso implementar por conta própria
Há opções demais no projeto de tipos de grafo
- Além de grafos direcionados e não direcionados, há muitas outras variações
- Grafos simples, com no máximo uma aresta entre dois nós, e multigrafos, que permitem várias arestas
- Hipergrafos, em que uma aresta conecta três ou mais nós
- Ubergrafos, em que arestas podem apontar para outras arestas
- Cada variação traz decisões extras de projeto
- É preciso decidir se arestas também terão ID, ou apenas os nós
- Também é preciso decidir que dados serão armazenados em nós e arestas
- Poderia haver um tipo genérico como um “hiperubermultigrafo direcionado”, deixando o usuário impor restrições, mas dois problemas aparecem imediatamente
- A interface muda, por exemplo, dependendo de a operação retornar um único valor ou uma lista
- Sem aproveitar propriedades especiais do grafo, o desempenho dos algoritmos piora
- Por exemplo, em maximum weight matching, se soubermos que o grafo é bipartido, podemos usar um algoritmo mais rápido; em grafos gerais, é preciso usar um algoritmo mais lento e mais genérico
- Quando há um problema P, um grafo G e algoritmos A, B e C, surge também o problema de despacho de algoritmo: qual deles executar
- Uma biblioteca de grafos perfeita precisaria suportar muitos tipos de grafo, mas isso reduziria o tempo disponível para implementar os algoritmos que os usuários realmente querem
- Algoritmos de grafos são difíceis de implementar
- O algoritmo
find_shortest_path, escrito pelo criador do Python, foi corrigido cinco vezes depois - Nicole diz que todas as implementações de PageRank que comparou estavam erradas
- O NetworkX oferece cerca de 500 algoritmos de grafos, e só o código desses algoritmos soma quase 60.000 linhas
- A biblioteca padrão inteira do Python tem cerca de 300 pacotes e menos de 600.000 linhas
- O algoritmo
- Quem mantém a biblioteca padrão teria de decidir que tipos de grafo, que tratamentos topológicos especiais e que algoritmos incluir, o que traz uma grande carga de manutenção
- Até o Python, conhecido pelo lema “batteries included”, vem passando por uma tendência de remoção, com o PEP 594 retirando 20 módulos da biblioteca padrão
Também é difícil escolher uma única forma de representar grafos
- Mesmo pensando apenas no grafo direcionado mais simples, há várias representações internas possíveis
- Lista de arestas:
[[a, b], [b, c], [c, a], [c, b]] - Lista de adjacência:
[[b], [c], [a, b]] - Matriz de adjacência:
[0 1 0; 0 0 1; 1 1 0] - Um conjunto de structs que se referenciam mutuamente
- Lista de arestas:
- O desempenho das operações muda conforme a representação
- Se um grafo com 100 nós e 200 arestas for representado por uma matriz de adjacência, a matriz 100×100 conterá 200 valores 1 e 9.800 valores 0
- O mesmo grafo, como lista de arestas, precisa apenas de 200 pares de nós
- Dependendo da linguagem e do nível de otimização, a diferença de memória pode passar de 20 vezes
- Por outro lado, em um grafo com 100 nós e 8.000 arestas, procurar a aresta entre o nó 0 e o 93 muda o resultado prático
- Na matriz de adjacência, é possível consultar com O(1) via
graph[0][93] - Em uma lista de arestas, é preciso percorrer as 8.000 arestas, então o tempo é O(|edge|)
- Na matriz de adjacência, é possível consultar com O(1) via
- Grafos com poucas arestas são esparsos, e grafos com quase todas as arestas possíveis são densos
- Um programa que monta o grafo a partir de dados externos pode começar com um grafo esparso e depois se tornar denso, então não existe uma “escolha sempre boa” de representação interna
- Se ainda adicionarmos dados de nós, dados de arestas e suporte a vários tipos de nós e arestas, a complexidade de implementação cresce ainda mais
- Bibliotecas de terceiros geralmente seguem um de dois caminhos
- Oferecem um tipo único rico que cobre todos os casos de uso, sacrificando eficiência
- Ou fornecem tipos de grafo separados por representação, deixando para o usuário o gerenciamento dos dados de nós e arestas
Os trade-offs mostrados por NetworkX e Petgraph
- O NetworkX armazena grafos como uma estrutura de dict de dict de dict para permitir anexar dados arbitrários a nós e arestas
- Ele oferece funções para converter para outras representações, mas não um modo de trabalhar diretamente nessas representações
- A principal biblioteca de grafos de Rust, Petgraph, oferece tipos por caso de uso, como
graph,graphmapematrix_graph - Bradford usa Petgraph no Nosey Parker, ferramenta de segurança que procura secrets em todo o histórico de um repositório git
- O grafo de benchmark é o CPython, com 250.000 commits e 1.300.000 objetos
- Como cada nó de commit tem poucas arestas, ele escolheu uma lista de adjacência
- Suportar várias representações aumenta o custo de adicionar algoritmos
- Se cada representação exigir um algoritmo separado, a carga de manutenção cresce de 3 a 4 vezes
- Se tudo for escrito sobre uma abstração genérica para tipos polimórficos, o desempenho cai
- Um entrevistado estimou que um algoritmo de grafo escrito sob medida pode ser mais de 20 vezes mais rápido do que um algoritmo genérico
Restrições de desempenho são o problema central das bibliotecas de grafos
- Em algoritmos de grafos há muitos problemas NP-complete ou até mais difíceis
- Das 21 canonical NP-complete problems de Karp, 14 são problemas de grafos
- Problemas de grafos podem rodar sobre entradas muito grandes, então o modo de representação e os detalhes de implementação podem determinar se a execução é viável ou não
- Em Nosey Parker, Bradford precisava percorrer o grafo de objetos para reconstruir um snapshot do sistema de arquivos para cada commit
- Os quatro graph walkers do Petgraph não eram extensíveis da forma necessária para esse caso de uso
- Então ele projetou na hora um graph traversal algorithm “semi-novel”, reduzindo o uso de memória em 1.000 vezes
- Zayenz citou o 15 puzzle como exemplo de caso em que o grafo é tão grande que não dá para tratá-lo por inteiro
- A busca da solução roda A* search no espaço de estados
- O espaço de estados tem mais de 20 trilhões de estados
- Gerar todos os nós já significa fracassar de saída
- Em um projeto de pesquisa ligado à extensão de grafos do resolvedor de restrições Gecode, com o qual Zayenz esteve envolvido, um tipo de grafo genérico também não conseguiu competir com a escolha de representações ajustadas ao problema
- Bancos de dados de grafos também foram projetados para executar algoritmos complexos de grafos, mas os problemas de desempenho continuam
- Segundo Nicole, se a travessia não limitar a profundidade, ela acabará visitando o grafo inteiro
- Mesmo uma busca como “ir até 3 passos para fora e encontrar se houver caminho” visita muitos dados
- Nicole diz que, em consultorias de desempenho de consultas em grafos, costuma principalmente conduzir migrações para fora de bancos de dados de grafos
- Em um projeto, deixou apenas um cálculo como estava e reescreveu todo o resto como um procedimento MapReduce
- Ficou mais difícil de entender, mas ao menos podia de fato terminar durante a noite
Por que grafos são raros na biblioteca padrão
- O suporte amplo a grafos é raro por uma combinação de fatores
- Há muitos tipos de grafo
- Cada tipo de grafo admite muitas formas de representação
- Há muitos tipos de algoritmo de grafo
- O desempenho dos algoritmos é sensível à representação e aos detalhes da implementação
- As pessoas executam algoritmos muito caros sobre grafos muito grandes
- A biblioteca padrão de uma linguagem teria de assumir decisões demais de projeto, trade-offs demais e uma carga alta de manutenção
- Também há motivos para programadores evitarem bibliotecas de grafos de terceiros
- A biblioteca pode ser limitada demais
- Uma biblioteca genérica pode não atender às exigências de desempenho
- Grafos são úteis para analisar sistemas, mas, na etapa de implementação, muitas vezes é preciso controlar diretamente a representação dos dados e a escolha dos algoritmos
Apêndice: linguagens com tipos de grafo e ferramentas relacionadas
- Linguagens de consulta de grafos (GQL) cumprem em bancos de dados de grafos um papel equivalente ao do SQL
- GraphQL não é uma linguagem de consulta de grafos; o nome vem de sua ligação com o Facebook Graph Search
- A principal diferença entre GQL e SQL é que relações, isto é,
join, são entidades de primeira classe- Em um conjunto de dados de filmes e pessoas, SQL implementa as relações “atuou em”, “dirigiu” e “produziu” como tabelas many-to-many separadas
- Em SPARQL, como relações são arestas, fica fácil consultar “as pessoas que tiveram qualquer papel no filme Y e qual foi esse papel”
- GQL também pode suportar manipulações de arestas como inversão, composição e fecho transitivo
- O SPARQL não oferece comprimento de caminho nem computação ao longo do caminho, por exemplo coletar cadeias de filmes ligando dois atores
- Uma GQL que suporte isso se torna muito mais complexa
- A linguagem de especificação formal Alloy tem primitivas úteis de travessia de grafos no tipo relation, o que torna mais fácil lidar com representações de grafos do que em linguagens de programação gerais
- Mas essas primitivas se baseiam em arestas rotuladas e podem não se encaixar em outras representações de grafo
- O Python adicionou graphlib em 2020
- Não há métodos além de
TopologicalSorter - O grafo só é aceito como dict de nós
- O grafo
a -> bé representado no sentido inverso, como{b: [a]}
- Não há métodos além de
- Em 2023, o
graphlibainda não era usado internamente no CPython- Há menos de 900 arquivos no GitHub que fazem referência a
graphlib - Já o
zoneinfo, adicionado no mesmo ano, aparece em mais de 6.000 arquivos - A expressão
def topological_sort(aparece em 4.000 arquivos - Muitos topological sorts implementados manualmente usam representações de grafo diferentes da do graphlib, o que dificulta a conversão
- Há menos de 900 arquivos no GitHub que fazem referência a
- Outros exemplos de biblioteca padrão com tipo de grafo incluem Erlang e SWI-Prolog
- Também existem linguagens de programação em que “tudo é grafo”
- Linguagens de software matemático como Mathematica, MATLAB e Maple também têm bibliotecas de grafos de alguma forma
- Em uma atualização de 18 de março de 2024, alguns comentários sobre o texto foram reunidos em uma página separada
1 comentários
Comentários do Hacker News
O Graphviz tem sua própria biblioteca básica de grafos, que outros projetos não usam, e isso trouxe vantagens e desvantagens
Com base nessa experiência, nós também acabamos sofrendo do típico síndrome do segundo sistema. Queríamos criar uma biblioteca de grafos modular, segura em tipos e eficiente, mas no fim isso provavelmente era uma variação de “bom, rápido e barato — escolha dois”
Ser modular significava querer desenvolver e compilar de forma independente um conjunto de bibliotecas de algoritmos de grafos, e ser segura em tipos significava querer detectar erros de programação em tempo de compilação ou, no mais tardar, na etapa de linkedição, em vez de erros em tempo de execução como “o nó não tem atributo
color”Ser eficiente significava que o custo de acessar propriedades do grafo precisava ser tão baixo quanto acessar campos de uma struct em C, e não queríamos depender de tabelas hash externas nem de muitas conversões para string
Dá para discutir se esses objetivos faziam sentido ou se valiam o preço, mas era isso que queríamos na época. Havia criadores famosos de C++ no laboratório, e estávamos dispostos a dar outra chance ao C++
Gordon Woodhull, que começou como estagiário e continuou trabalhando conosco, era um programador brilhante e escreveu uma implementação desse tipo de biblioteca de grafos em C++ com templates. O código-fonte ainda está em https://www.dynagraph.org/
O resto de nós não tinha certeza de que algum dia conseguiria entender como aquele código funcionava, então fizemos revisão de código com inventores famosos do C++, e depois de inúmeras telas cheias de código e longos silêncios a conclusão foi: “provavelmente funciona”. Foi aí que percebemos que talvez já tivéssemos passado do precipício da complexidade
Erros de template em tempo de compilação enchiam a tela inteira com uma única falha e despejavam detalhes que só inventores de C++ seriam capazes de amar. A culpa foi nossa, e Gordon seguiu em frente mesmo assim, a ponto de fazer layout dinâmico de grafos funcionar até no Microsoft OLE
Olhando para trás, aquilo foi nosso próprio Project Xanadu, e enquanto nos perdíamos nele surgiram coisas como Gephi (Java), NetworkX e NetworKit (Python). John Ellson, um excelente engenheiro de software que escreveu partes do Graphviz, trouxe o trabalho principal de volta aos trilhos
Tendo trabalhado bastante com grafos, já me perguntaram incontáveis vezes: “por que linguagens de programação não têm um tipo de dado de grafo embutido?”
Agora fico feliz por não precisar apenas pedir que acreditem quando digo “é realmente muito difícil fazer isso bem”, e poder apontar para uma análise mais profunda como esta
O que a maioria das linguagens oferece como tipos estruturais são basicamente arrays estáticos, arrays dinâmicos e listas ligadas. Coisas como árvores binárias de busca ou tabelas hash são abstrações semânticas que ocultam parte das capacidades da estrutura subjacente, não representações estruturais puras
A parte do texto que diz “há escolhas demais de implementação” fala da mesma coisa. Aí conheci o Petgraph [0] e foi a primeira vez que olhei de verdade para uma biblioteca de grafos de uso geral; achei bem interessante, mas ainda assim continuei implementando grafos no nível do domínio
[0] https://github.com/petgraph/petgraph
https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...
Quase toda linguagem oferece um mapa hash, e embora em casos específicos você possa fazer uma implementação mais rápida por conta própria, a implementação padrão em geral funciona bem. Com grafos isso é mais difícil, e talvez, se fosse para fazer, fosse preciso oferecer vários tipos de grafo
Só como observação, o HashMap do Java é um pouco incomum por permitir ajustar o fator de carga, ao contrário da maioria das outras linguagens
O que as pessoas querem, na verdade, está mais próximo de ferramentas para percorrer grafos do que de um tipo de grafo em si
Acho que grafos são mais uma abstração do que uma estrutura de dados ou tipo de dado
No fundo, tudo de que você precisa para definir um grafo é um conjunto de vértices v \in V e uma função Neighbors(v), e para a maioria dos algoritmos básicos de grafos isso realmente basta
O resto são restrições específicas de cada caso. Se A->B implica B->A, se o conjunto de nós pode ser particionado sob certas restrições, se há cores ou rótulos, e assim por diante
Generalizando mais, dá até para chegar a hipergrafos, em que basta ter um conjunto de vértices e um conjunto de conjuntos de vértices. Dependendo do interesse, isso pode ser representado de inúmeras maneiras, e o grafo comum é só um caso particular
Do ponto de vista de banco de dados, isso também pode ser visto como um problema de otimização de consultas e indexação. Dependendo das perguntas que você quer fazer ao grafo, a forma de representação que responde melhor muda. Assim como não existe uma única forma de representar a abstração “tabela”, “grafo” também não se resume a uma única forma
Eles estão no mesmo nível de abstração de números puros. Assim como dá para dizer que existem bibliotecas “numéricas” úteis, também dá para dizer que existem bibliotecas “gráficas” úteis, mas não existem muito bibliotecas de “números” ou de “grafos”. Esses conceitos são abstratos demais para construir uma API
Os arquivos seriam os vértices, e os diretórios seriam conjuntos de vértices que podem ser aninhados
Há dois obstáculos principais
Para problemas de grafo simples e pequenos, é fácil o bastante implementar diretamente uma lista de adjacência com um vetor de vetores; para problemas de grafo complexos e enormes, o desempenho só aparece quando a implementação do grafo é feita sob medida para os detalhes do problema que se quer resolver
Por isso, não fica claro que tipo de suporte da linguagem ajudaria. Seria difícil, a menos que existisse algo como um compilador superinteligente capaz de analisar o código e decidir se lista de adjacência, matriz, arranjo tridimensional etc. é o ideal. Esse tipo de otimização provavelmente não vai aparecer em compiladores tão cedo
Este é outro exemplo do fenômeno observado por Stroustrup. Somos bons em compartilhar código de coisas pequenas, como vetores, e de coisas grandes, como sistemas operacionais, mas não conseguimos compartilhar bem os problemas de tamanho intermediário
Dentro de um ecossistema de linguagem, a API de vetor é pequena, então parece fácil compartilhar. Sistemas operacionais também têm APIs relativamente pequenas em comparação com sua complexidade interna, e o mesmo vale para bibliotecas de computação numérica, por isso são bem compartilhados
Por outro lado, quanto mais se tenta customizar algo como uma estrutura de dados complexa, mais a API fica complexa e mais difícil se torna compartilhar. No fim, a possibilidade de compartilhamento parece depender da área de superfície do que é compartilhado, isto é, do tamanho relativo da API
Electric Clojure usa as próprias s-expressions do Clojure como sintaxe de escrita de grafos e, com macros, concretiza o fluxo de dados de um sistema reativo cliente/servidor
O caso de uso aqui é interface de usuário full stack, mas a ideia pode ser generalizada. https://github.com/hyperfiddle/electric fundador
Vejo a resposta para “Para onde foram todos os tipos de grafo?” como sendo que uma DSL de escrita de grafos precisa expressar escopo, fluxo de controle e abstração, e então acaba sendo isomórfica a uma linguagem de programação liberada do modelo de avaliação. Em Python e TypeScript, é bem difícil encaixar uma linguagem de programação completa no meio
Também vale consultar o post “Four problems preventing visual flowchart programming from expressing web applications”
https://www.dustingetz.com/#/page/four%20problems%20preventi...
Este texto responde principalmente à pergunta “por que linguagens de programação não dão suporte melhor a algoritmos de grafos” e parece focar mais em processamento de grafos de “big data” do que em suporte geral a grafos
Se olharmos para suporte a grafos de forma ampla, isso inclui perguntas maiores como “por que OGM (Object Graph Mapper) não é tão popular quanto ORM?” e “por que JSON é amplamente usado, enquanto RDF ou outras serializações de grafo de baixo nível não são?”
No fim, acho que os motivos históricos pesam bastante. O RDF surgiu um pouco cedo demais, não conseguiu evoluir direito e acabou acumulando padrões acadêmicos horríveis e um ecossistema de implementações igualmente ruim. Além disso, grafos são intrinsecamente um pouco mais complexos em implementação e curva de aprendizado, então não escalam tão bem para muitos desenvolvedores
Eu não daria peso demais à seção “Graph Querying Language” do texto. Há trechos que soam como material de marketing escrito por usuários entusiasmados de Neo4J ou SPARQL sem realmente terem construído produtos
Diz-se que “a principal diferença entre todo GQL e SQL é que joins, isto é, relacionamentos, são entidades de primeira classe”, mas em SQL joins também são entidades de primeira classe. Existe até a palavra-chave JOIN
Se descermos para a camada mais baixa das linguagens de consulta a grafos e olharmos os planos de consulta, não há muita diferença significativa em relação a consultas baseadas em SQL. O fato de a padronização do GQL[0] estar avançando como uma extensão de SQL é uma evidência disso
O SPARQL é fácil quando se precisa de travessia exata de caminhos, mas, ao tentar fazer algo um pouco mais complexo do tipo que se faria no backend de uma aplicação web, logo se cai em armadilhas como joins com valores não vinculados, que podem acabar apagando acidentalmente todo o conjunto de resultados
[0]: https://en.wikipedia.org/wiki/Graph_Query_Language
Por exemplo, type classes em Haskell não são de primeira classe, e fluxo de controle também não é de primeira classe na maioria das linguagens de programação
Só não há atalhos sintáticos; em essência, linguagens de consulta a grafos se concentram em adicionar justamente esses atalhos
As ferramentas para desenhar grafos também são bem decepcionantes. Funcionam bem em grafos pequenos, mas quando passam de uns 500 nós a saída fica completamente incompreensível ou muito difícil de ver
Falta capacidade de organizar automaticamente o grafo em uma estrutura hierárquica e oferecer uma interface boa para exploração. Considerando que estamos acostumados a enxergar quase tudo ao nosso redor até certo ponto como uma hierarquia, parece que o mesmo tipo de problema também precisaria ser resolvido ao criar um tipo de dado de grafo genérico
Isso talvez precise ser implementado no nível do compilador, para que algoritmos genéricos de grafos se adaptem à hierarquia estrutural gerada. Se somarmos a isso um provador de teoremas para verificar que certos subgrafos sempre têm uma estrutura específica, esse procedimento pode ser gerado estaticamente, enquanto para o restante do grafo superior ele pode ser gerado dinamicamente em tempo de execução
Portanto, quem resolver o problema de desenho de grafos genérico provavelmente também terá a capacidade ou a percepção necessária para implementar isso
Uma biblioteca de desenho de grafos genérica do tipo Graphviz, oferecendo mais opções e controle
https://eclipse.dev/elk/
Experimento conduzido pela equipe de desenvolvimento do ELK na Kiel University
https://github.com/kieler/KLighD
Wiki do projeto Kieler
https://rtsys.informatik.uni-kiel.de/confluence/display/KIEL...
Biblioteca de desenho de grafos baseada em restrições
https://www.adaptagrams.org/
Implementação em JavaScript
https://ialab.it.monash.edu/webcola/
Material interessante: HOLA: Human-like Orthogonal Network Layout
https://ialab.it.monash.edu/~dwyer/papers/hola2015.pdf
A demo de Confluent Graphs torna as arestas mais fáceis de ler
https://www.aviz.fr/~bbach/confluentgraphs/
Stress-Minimizing Orthogonal Layout of Data Flow Diagrams with Ports
https://arxiv.org/pdf/1408.4626.pdf
Improved Optimal and Approximate Power Graph Compression for Clearer Visualisation of Dense Graphs
https://arxiv.org/pdf/1311.6996v1.pdf
Mesmo em grafos estruturalmente idênticos, duas pessoas podem renderizá-los de formas totalmente diferentes para enfatizar aspectos distintos dos dados. Isso também é semelhante ao problema de “algoritmo de grafo genérico” e “estrutura de dados de grafo genérica”
Grafos ficam na fronteira entre código e dados. Por exemplo, qualquer programa tem um grafo de chamadas, então, em certo sentido, um “algoritmo de grafo genérico” é a própria computação
Quando passam de algumas dezenas de nós, geralmente fica difícil torná-los planares, ou fazer com que pareçam quase planares com poucos cruzamentos e bom agrupamento de nós relacionados
Na prática, o desenho de grafos precisa conciliar coisas que quase não são hierárquicas, e é difícil traçar uma linha matematicamente rigorosa sobre até onde algo pode ser considerado hierárquico. Quanto menos suposições se fizer sobre a estrutura subjacente do grafo — como conectividade, presença de ciclos ou esparsidade — pior esse problema fica
Ao criar uma UI para interagir com grafos em trabalho prático, normalmente dá para definir ou impor um ou dois níveis de meta-hierarquia para permitir clustering; isso reduz o impacto de nós tipo hairball que estragam o layout e também diminui o número de nós, melhorando o desempenho de renderização. Para o layout, dá para usar fCOSE, e também existe uma implementação em Cytoscape.js
Acho que a observação central, de que “há opções demais de implementação”, não está totalmente correta
Na prática, uma biblioteca poderia implementar todas as representações adequadas de grafos, fornecer em cada representação os algoritmos com melhor desempenho e oferecer conversões entre as representações. Essas conversões são proporcionais ao número de representações, e tanto a implementação quanto o uso são simples, então o custo para mantenedores e usuários parece bem razoável
Como bônus, também poderia oferecer conversões de importação/exportação a partir de tipos de dados e idiomatismos da biblioteca padrão. Memória e custo de conversão são baratos, e em 99% dos casos de uso o overhead de transformação de dados provavelmente pode ser ignorado tanto em RAM quanto em CPU
Isso também me faz lembrar a frase: “A dura verdade de trabalhar no Google é que, no fim das contas, você está só movendo protobuf de um lugar para outro”
https://news.ycombinator.com/item?id=20132880
No fim, a gente sempre acaba reimplementando grafos. Desempenho importa, e as bibliotecas de grafos prontas que vi não conseguiam explorar a regularidade dos nossos conjuntos de dados. Por exemplo, usamos um DAG append-only no qual quase todos os nós têm só uma aresta apontando para o item adicionado por último, então dá para usar codificação por comprimento de execução internamente
Também nunca vi uma biblioteca de grafos genérica que suportasse as consultas de que precisamos. Em especial, uma grande é uma função de diff de subgrafo
Além disso, uma implementação sob medida não dá tanto trabalho assim. Grafos são muito mais fáceis de reimplementar do que B-trees, e uma implementação simples cabe em poucas dezenas de linhas. Até a nossa biblioteca altamente otimizada, com os algoritmos de suporte incluídos, tem só algumas centenas de linhas
Seria bom ter uma forma de exportar os dados em um formato padrão, mas no nosso caso de uso trazer uma biblioteca parece que criaria mais problemas do que resolveria
Uma aplicação ausente que me vem à cabeça com frequência é um Excel para grafos
Seria uma ferramenta como o Excel para dados tabulares: para dados que cabem na RAM, numa escala em que você precisa de um computador mas não de um datacenter, que implemente muitos algoritmos e visualizações “boas o suficiente” e que possa ser usada sem conhecimento de programação
Como o texto diz, muitos problemas do mundo real são problemas de grafo, então por que só programadores deveriam ter ferramentas para resolvê-los?
Ainda assim, existem estruturas de dados e bibliotecas padrão que atendem bem à maioria dos casos de uso, e se houver exigências especialmente pesadas, aí você cria uma solução sob medida
O texto diz que muitas vezes os grafos são grandes demais, mas se você perguntar a pessoas que realmente lidam com algoritmos de grafos, é fácil ter essa impressão. A maioria dos programadores e usuários provavelmente lidará apenas com grafos realmente pequenos
Não acho que um usuário comum veja grafos em problemas aleatórios do mundo real. O que aprendi trabalhando em uma grande empresa é que, com esforço suficiente, tudo pode virar uma planilha do Excel
https://strlen.com/treesheets/ é mais próximo de um Excel para dados em árvore
Por exemplo, diz-se que a internet pode ser modelada como um grafo, mas, mesmo que isso seja verdade, não está claro o que isso traz de útil. A internet pode ser representada de várias maneiras, e não é evidente que representá-la como grafo tenha implicações de engenharia geralmente úteis
Daria para argumentar de forma parecida, com igual poder de convencimento, que a representação ideal para extrair informação útil é uma função de codificação matricial de caixa-preta que mapeia entradas arbitrárias para saídas consistentes, ou seja, uma rede neural
Em lugares como o Google isso pode até ser uma ideia de bilhões de dólares, mas a internet inteira não é um problema de grafo para muita gente, e representá-la como grafo não resolve muita coisa
Pouca gente está resolvendo problemas do mundo real no papel com grafos. Tabelas são usadas o tempo todo. Grafos são comuns, mas problemas de grafo não são comuns
Em outros comentários também foi dito que visualização de grafos é difícil, mas interfaces 3D dão muito mais espaço. Quando o hype de VR começou, pensei: “qual seria o Excel do VR?”. A resposta da Microsoft foi “planilhas 2D flutuando no espaço 3D”. Acho isso absurdo. Eu acho que seriam grafos
Se alguém quiser explorar isso junto, pode mandar e-mail para meu nome de usuário at gmail.com
Tipos de grafo existem há bastante tempo
Em Erlang há https://www.erlang.org/doc/man/digraph.html e https://www.erlang.org/doc/man/digraph_utils, e, se você quiser fazer trabalho mais de teoria dos conjuntos, também há https://www.erlang.org/doc/man/sofs.html
O conteúdo é: “Encontrei Erlang e SWI-Prolog como duas outras linguagens com tipo de grafo. Como não conheço bem nenhuma das duas, não sei dizer quando isso foi adicionado, mas Erlang existe pelo menos desde antes de 2008. Entrei em contato com alguém do comitê central da linguagem Erlang, mas não recebi resposta”
Já a usei para resolução de dependências ao definir ordem de tarefas