Fundamentos do Armazenamento de Grafos

A modelagem e o armazenamento de estruturas em grafo formam a base de sistemas modernos, incluindo redes sociais, motores de recomendação e bases de conhecimento. Um grafo é composto por vértices (nós) e arestas (relações). A escolha da estrutura de dados subjacente impacta diretamente a latência das operações de leitura e escrita, a pegada de memória e a capacidade de escalar horizontalmente.

Matriz de Adjacência

A abordagem clássica utiliza um arranjo bidimensional onde as coordenadas representma os vértices e os valores armazenados indicam a presença de uma aresta ou o seu respectivo peso.

Vantagens

• A validação de conexão entre dois nós ocorre em tempo constante O(1).
• Altamente recomendada para modelagem de grafos densos.

Desvantagens

• O consumo de memória escala quadraticamente O(V²), gerando desperdício significativo em grafos esparsos.
• A reestruturação do arranjo para adição ou remoção de vértices é uma operação custosa.

class MatrizDeAdjacencia:
    def __init__(self, total_vertices):
        self.matriz = [[0] * total_vertices for _ in range(total_vertices)]

    def criar_conexao(self, origem, destino, peso=1):
        self.matriz[origem][destino] = peso
        self.matriz[destino][origem] = peso  # Configuração para grafo não direcionado

Lista de Adjacência

Esta técnica associa cada vértice a uma coleção dinâmica contendo apenas as referências de seus vizinhos diretos.

Vantagens

• A complexidade espacial é reduzida para O(V + E), sendo o padrão de fato para a maioria dos algoritmos em grafos esparsos.
• Inserções e remoções de conexões são operações rápidas e isoladas.

Desvantagens

• Verificar se uma aresta específica existe requer iteração sobre a lista de vizinhos, resultando em complexidade O(V) no pior caso.

from collections import defaultdict

class ListaDeAdjacencia:
    def __init__(self):
        self.vizinhos = defaultdict(list)

    def conectar(self, no_a, no_b):
        self.vizinhos[no_a].append(no_b)
        self.vizinhos[no_b].append(no_a)

Lista de Arestas

Um modelo minimalista que consiste em um repositório plano de todas as conexões existentes no sistema.

Vantagens

• Arquitetura de armazenamento extremamente simples e excelente para ingestão de dados em lote.
• Ocupa espaço estritamente proporcional ao número de conexões O(E).

Desvantagens

• Consultas de vizinhança exigem varredura linear completa O(E), tornando-o impraticável para buscas topológicas em tempo real.

from dataclasses import dataclass

@dataclass
class Aresta:
    origem: int
    destino: int
    custo: float

repositorio_conexoes = [
    Aresta(origem=10, destino=20, custo=1.5),
    Aresta(origem=20, destino=30, custo=2.0)
]

Lista Ortogonal

Projetada para grafos direcionados, esta estrutura mescla a lista de adjacência tradicional com a lista inversa. Cada nó mantém referências separadas tanto para as arestas de saída quanto para as de entrada.

Vantagens

• Permite calcular os graus de entrada e saída de um vértice de forma isolada e eficiente.
• Mantém a complexidade espacial em O(V + E).

Desvantagens

• A lógica de implementação é intrincada, exigindo a atualização simultânea de múltiplos ponteiros durante mutações no grafo.

struct NoAresta {
    int id_origem;
    int id_destino;
    double metrica;
    NoAresta* proxima_saida;
    NoAresta* proxima_entrada;
};

Multilista de Adjacência

Uma otimização específica para grafos não direcionados que evita a redundância de salvar cada aresta duas vezes na memória.

Vantagens

• Economia de memória e travessias de arestas mais velozes, pois cada conexão possui um único registro físico.
• Facilita a marcação de arestas visitadas durante algoritmos de busca.

Desvantagens

• O gerenciamento de ponteiros duplos durante a remoção de arestas eleva a complexidade do código.

struct RegistroAresta {
    int vertice_a;
    int vertice_b;
    float peso;
    RegistroAresta* link_a;
    RegistroAresta* link_b;
    bool foi_visitado;
};

Bancos de Dados de Grafos

Soluções especializadas de mercado oferecem suporte nativo a propriedades, índices secundários e transações ACID para manipulação de dados interconectados.

Vantagens

• Projetados para consultas topológicas profundas e garantem a integridade dos dados em ambientes de produção.
• Motores de execução otimizados com cache de travessia.

Desvantagens

• A infraestrutura requer recursos operacionais significativos para implantação, particionamento e manutenção contínua.

MATCH (usuario:Usuario {status: 'ativo'})-[:SEGUIU]->(alvo:Usuario)
WHERE alvo.idade > 25
RETURN usuario.nome, alvo.nome

Linha Esparsa Comprimida (CSR)

O formato CSR é um padrão de compressão que traduz a estrutura do grafo em três vetores unidimensionais: ponteiros de linha, índices de coluna e pesos.

Vantagens

• Maximiza a localidade de cache da CPU e é o formato preferencial para computação científica e algoritmos matriciais em grafos massivos.
• Altíssima densidade de informação por byte alocado.

Desvantagens

• Estrutura imutável por design; adições ou remoções de arestas exigem a reconstrução parcial ou total dos vetores.

class GrafoCSR:
    def __init__(self):
        # Ponteiros de início de cada vértice no vetor de índices
        self.indptr = [0, 2, 3, 5]
        # Identificadores dos vértices de destino
        self.indices = [1, 2, 0, 0, 2]
        # Valores das conexões
        self.dados = [0.5, 1.2, 0.5, 0.8, 1.1]

Armazenamento Distribuído

Frameworks de processamento distribuído fragmentam o grafo em um cluster de máquinas para permitir computação paralela.

Vantagens

• Escalabilidade horizontal teoricamente ilimitada, lidando com grafos compostos por bilhões de nós e arestas.
• Suporte nativo a execução paralela de algoritmos de caminho mais curto e centralidade.

Desvantagens

• A sobrecarga de rede durante a sincronização de estados entre nós do cluster é alta.
• O desempenho geral depende estritamente da estratégia de particionamento (Hash ou Faixa de IDs) para minimizar a quantidade de arestas que cruzam diferentes partições.