Graphs

O que é um Graph

Um graph é um conjunto de nodes mais um conjunto de edges conectando eles. Essa é a definição inteira. Todo o resto — direção, weight, cycles — é uma variação sobre esses dois conjuntos.

Toda estrutura até aqui foi sobre armazenar valores. Um graph é sobre relações entre valores. Os nodes são as coisas; os edges são como elas se relacionam.

Essa distinção importa: um graph é um abstract data type (ADT), não uma estrutura de dados concreta. Ele define o que você pode perguntar — adicionar um node, conectar dois nodes, listar os neighbors de um node — mas não diz nada sobre como nada disso é armazenado. As duas estruturas concretas que honram esse contrato são a adjacency list e a adjacency matrix, e escolher entre elas é a decisão mais consequente que você toma sobre um graph. É sobre essa escolha que este artigo trata na maior parte.

Note também o que um graph não tem: nenhum primeiro elemento, nenhum último elemento, nenhuma ordem. Uma linked list é um graph onde cada node tem exatamente um neighbor; uma tree é um graph sem cycles e com uma root. Graphs são o caso geral, e toda estrutura desta série até aqui é um graph com regras adicionais.

O problema que as estruturas anteriores não resolviam

Toda estrutura até aqui impõe uma forma aos seus dados, e cada forma tem uma pergunta correspondente que ela responde bem.

Arrays indexam por posição. Posição é uma relação útil quando seus dados são genuinamente sequenciais, mas "o usuário 4 está ao lado do usuário 5" não diz nada sobre eles se conhecerem.

Linked lists encadeiam um node ao próximo. Isso é uma relação — mas exatamente uma por node, sempre em uma direção. Você não consegue expressar "esta estação se conecta a três outras estações".

Hash tables mapeiam uma key para um value em O(1). Esse é o encaixe mais próximo entre as estruturas planas, e é por isso que graphs normalmente são construídos sobre uma. Mas uma hash table por si só armazena key → value, não key → outras keys.

Trees chegam mais perto que todas, e os últimos cinco artigos foram variações delas. Uma tree finalmente deixa um node apontar para vários — mas paga por isso com duas restrições que ela nunca afrouxa: todo node tem exatamente um parent, e não existem cycles. Essas duas são o que torna as garantias de uma tree possíveis, e são precisamente o que relações reais violam.

O que nenhuma delas consegue expressar é many-to-many com cycles. Uma pessoa tem muitos amigos, cada um deles tem muitos amigos, e seguindo esses links longe o suficiente você volta para onde começou. É essa a estrutura para a qual graphs existem — e derrubar as duas restrições de uma tree é exatamente o que um graph é.

Nodes, edges e o vocabulário

Graphs vêm com mais vocabulário do que qualquer estrutura até aqui. Tudo descreve os mesmos dois conjuntos, então o caminho mais rápido é manter os mesmos seis nodes e mudar uma coisa por vez.

Directed vs undirected

Em um graph undirected, um edge é mútuo: se A se conecta a B, então B se conecta a A. Amizade no Facebook funciona assim — não existe amigo de mão única.

Em um graph directed (ou digraph), cada edge tem uma direção. A aponta para B não diz nada sobre B apontar para A. Follows no Twitter funcionam assim, e também links da web, dependências de tarefas e chamadas de função.

Direção muda o que a estrutura armazena, não apenas o que ela significa. Um edge undirected é registrado duas vezes — uma na neighbor list de cada ponta — enquanto um edge directed é registrado uma só. É essa duplicação que faz uma adjacency list undirected custar 2E slots em vez de E.

Em um graph directed cada node tem duas contagens: in-degree (edges chegando) e out-degree (edges saindo). D acima tem in-degree 2 e out-degree 0.

Weighted vs unweighted

Um edge pode carregar um número: distância, custo, capacidade, latência, similaridade. Um graph cujos edges carregam números é weighted.

Estruturalmente, um weight é só um segundo valor armazenado junto de cada edge. Em uma adjacency list a entrada de neighbor passa a ser uma pequena struct em vez de um id solto; em uma matrix a célula guarda um número em vez de um bool, com algum sentinel — math.MaxInt, ou 0 quando zero não pode ser um weight legítimo — representando "sem edge".

Essa legenda é o que faz o weight valer o campo extra: A–C–D são dois edges, o mesmo que A–B–D, mas custa mais. Quando edges têm custos diferentes, "menos edges" e "rota mais barata" passam a ser perguntas diferentes.

Degree, path e cycle

O degree de um node é quantos edges o tocam. Um path é uma sequência de nodes onde cada par consecutivo está conectado. Um simple path nunca repete um node. Um cycle é um path que termina onde começou.

Degree é o número que decide o quão caro um node é para trabalhar: uma adjacency list responde "quem são os neighbors deste node" em tempo proporcional ao degree dele, então um node de degree alto é um node lento. Em um graph social esse é o problema da celebridade — algumas poucas contas com milhões de edges dominam o custo de tudo.

Cycles são o que separa um graph de uma tree. Como D é alcançável a partir de A por dois caminhos diferentes, não existe uma única relação de parent em que se apoiar, e nenhuma garantia de que seguir edges termine. Um graph com direção e sem cycles é um DAG — directed acyclic graph — que é a forma que dados de dependência assumem.

Connected, disconnected e components

Um graph é connected se existe um path entre todo par de nodes. Se não, ele se divide em connected components — ilhas sem edges entre si.

G importa para a representação mesmo que nada aponte para ele. Uma adjacency list ainda precisa de uma entrada para ele — esse é o V do O(V + E) — e uma matrix ainda aloca a linha e a coluna inteiras dele. Um node sem edges custa algo nos dois layouts, e é por isso que a contagem de nodes nunca é irrelevante.

Representando um Graph em memória

Duas estruturas dominam, e a escolha entre elas troca espaço por velocidade de lookup.

Adjacency list

Armazene, para cada node, uma lista dos seus neighbors. Em Go isso é um map de node para slice de nodes.

Para o graph acima, a adjacency list é:

Cada edge undirected aparece duas vezes — uma de cada ponta. A–B aparece na lista de A e na de B. Isso não é redundância para eliminar; é o que faz "listar os neighbors de B" ser tão rápido quanto "listar os de A".

Aqui está o type e o seu uso. O uso é o ponto; a implementação está a uma aba de distância.

O custo de espaço é O(V + E) — uma entrada de map por node, um elemento de slice por ponta de edge. Para a maioria dos graphs reais isso é pouco, porque a maioria dos graphs reais é sparse: um usuário do Facebook tem centenas de amigos, não dois bilhões.

Adjacency matrix

Armazene uma grade V × V onde a célula [i][j] diz se existe um edge de i para j.

Duas coisas para ler nela. A matrix é simétrica em relação à diagonal, porque o graph é undirected — para um digraph não seria. E ela é quase toda zeros: 12 de 36 células carregam um edge, e essa proporção só piora conforme o graph cresce.

Qual dos dois usar

Um graph é dense quando E se aproxima de V², e sparse caso contrário. E o cruzamento é exato, não uma questão de gosto: uma adjacency list undirected guarda V + 2E slots, então em um graph completo, onde E = V(V−1)/2, isso dá V + V(V−1) — precisamente V², a contagem de células da matrix.

Então a list é menor para todo graph que não é completo, empata quando é, e só perde na prática porque os seus slots são mais gordos: um header de slice e um bucket de map custam muito mais por entrada do que um byte em uma grade. Essa é a regra real — a matrix ganha quando o graph é quase completo, pequeno, ou quando hasEdge é o seu caminho crítico, e a list ganha em todo o resto.

Na prática isso significa que adjacency lists ganham quase sempre, porque os graphs que as pessoas de fato têm — malhas viárias, graphs sociais, árvores de dependência, a web — são todos sparse.

Teste você mesmo

Duas formas de editar o graph: clique em uma linha do diagrama para cortar aquele edge, ou clique em qualquer célula da matrix para alternar um. De qualquer forma, veja as três visões se moverem juntas — o diagrama, a adjacency list e os dois contadores de espaço.

O fato de a matrix funcionar como controle já é o ponto que vale notar: uma célula é a pergunta "existe um edge entre estes dois", então respondê-la de outra forma e editar o graph são a mesma ação. A adjacency list não tem célula para clicar em um edge que não existe, que é exatamente por que ela custa menos.

Experimente Conectar tudo para chegar no empate exato descrito acima, depois corte uma única linha e veja a list cair abaixo da matrix outra vez.

Operações comuns e seus custos

Assumindo uma adjacency list, onde V são nodes e E são edges:

Note quantas dessas são O(deg) em vez de O(1) ou O(n). Degree é o custo característico da adjacency list, e é por isso que a forma do graph — não só o tamanho dele — determina a velocidade do seu código.

Graphs no mundo real

Redes sociais

Pessoas são nodes, relações são edges. O Facebook construiu um armazenamento de graph distribuído dedicado, o TAO, porque o padrão de leitura de um graph social — buscar os neighbors de um node, milhões de vezes por segundo — é exatamente aquilo em que um banco de dados de propósito geral é ruim. A representação, não o algoritmo, foi o gargalo que valeu engenharia.

Mapas e roteamento

Cruzamentos são nodes, ruas são edges weighted. Malhas viárias são extremamente sparse — um cruzamento tem talvez quatro ruas, nunca quatro milhões — então são armazenadas como adjacency lists, normalmente em um layout comprimido que troca facilidade de edição por leituras sequenciais.

Gerenciadores de pacote e build systems

go mod graph imprime um graph de dependências, e todo gerenciador de pacote mantém um. A forma de DAG é o ponto: dependências sem cycles admitem uma ordem de instalação válida, e um cycle é um erro fatal que você vê reportado como tal.

Compiladores

Compiladores transformam cada função em um control-flow graph: basic blocks como nodes, saltos possíveis como edges. Esses graphs são pequenos e frequentemente dense o bastante para uma matrix baseada em bitset ser a escolha certa — o oposto de uma malha viária, pelas mesmas razões ao contrário.

Graphs de conhecimento e recomendação

Produtos, tags, usuários e suas interações formam um graph onde um edge significa "relacionado". Bancos como o Neo4j existem porque expressar isso em SQL significa um join por salto, e o número de saltos é exatamente o que você não sabe de antemão.

Bancos de dados

O PostgreSQL mantém um wait-for graph de qual transação está bloqueada por qual lock. É um graph directed pequeno mantido continuamente, e a forma dele — especificamente se contém um cycle — é o que diz ao banco que ocorreu um deadlock.

Quando Graphs deixam a desejar

Graphs modelam quase qualquer coisa, que é exatamente por que são fáceis de escolher quando algo mais simples resolveria.

Pointer chasing é hostil ao cache. Percorrer uma adjacency list significa seguir lookups de map e referências de slice espalhados pela memória, então quase todo passo é um cache miss. Arrays ganham em localidade por uma margem larga. É por isso que processamento sério de graph abandona a representação amigável em favor de formatos comprimidos como CSR, que empacotam todas as neighbor lists em dois arrays planos e abrem mão de mutação barata para recuperar leituras sequenciais.

Matrices não escalam. O(V²) é tranquilo com mil nodes e impossível com um milhão, e a contagem de edges nunca entra na conta. Use uma matrix só quando você estabeleceu que o graph é dense e limitado.

Nodes de degree alto distorcem tudo. O(deg) é um limite confortável até um node ter um milhão de edges. Graphs reais seguem power laws, então um punhado de nodes domina o custo de toda operação, e o degree médio te diz quase nada sobre o pior caso.

Mutação e concorrência não combinam. Um map de Go não é seguro para escrita concorrente, então um graph compartilhado precisa de um mutex ou de um redesenho. Pior, uma leitura que segura um lock enquanto percorre serializa tudo — e uma que não segura pode observar uma lista de edges mudando debaixo dela. Snapshots imutáveis normalmente são a resposta.

Algo mais simples costuma servir. Se seus dados têm uma root e nenhum cycle, é uma tree, e código de tree é mais curto e mais rápido. Se você só pergunta "qual o parent deste node", uma hash table de parents ganha de um graph. Use um graph quando você realmente precisa de relações many-to-many arbitrárias — não meramente porque seus dados têm algumas relações.

Resumo

Graphs são o caso geral do qual toda outra estrutura desta série é um caso particular:

• Nodes e edges — um graph modela relações, não sequência, e expressa conexões many-to-many que nada mais aqui consegue
• Direção e weight são decisões de armazenamento — um edge undirected é guardado duas vezes, e um weight é um campo extra por edge ou por célula
• Adjacency list para sparse, matrix para dense — O(V + E) contra O(V²), e o cruzamento é exatamente um graph completo
• Degree é o custo que importa — a maioria das operações de adjacency list é O(deg), então a forma do graph, não só o tamanho, define a sua performance
• Cycles separam um graph de uma tree — sem root, sem ordem, e sem garantia de que seguir edges termine

A percepção principal é que graphs invertem para que serve uma estrutura de dados. Arrays, linked lists, stacks, queues e hash tables todas organizam valores. Um graph organiza conexões, e os valores se tornam quase incidentais — que é por que escolher uma representação importa mais aqui do que em qualquer estrutura até agora. O mesmo graph armazenado de duas formas pode diferir em ordens de magnitude em memória e no custo da única pergunta que você mais faz.

É também por isso que este artigo para onde para. Escolher uma representação é uma decisão de estrutura de dados, e é a primeira que você toma. O que você depois faz com o graph — percorrer, encontrar shortest paths, detectar cycles, ordenar um DAG — é um corpo de trabalho separado, e ganha a própria série.