Três maneiras de armazenar um gráfico na memória, vantagens e desvantagens

Existem três maneiras de armazenar um gráfico na memória:

1. Nós como objetos e bordas como ponteiros
2. Uma matriz contendo todos os pesos das arestas entre o nó numerado xe o nó y
3. Uma lista de arestas entre nós numerados

Sei escrever todos os três, mas não tenho certeza se pensei em todas as vantagens e desvantagens de cada um.

Quais são as vantagens e desvantagens de cada uma dessas maneiras de armazenar um gráfico na memória?

Uma forma de analisá-los é em termos de complexidade de memória e tempo (que depende de como você deseja acessar o gráfico).

Armazenando nós como objetos com ponteiros um para o outro

• A complexidade da memória para essa abordagem é O (n) porque você tem tantos objetos quanto nós. O número de ponteiros (para nós) necessários é de até O (n ^ 2), pois cada objeto de nó pode conter ponteiros para até n nós.
• A complexidade de tempo para esta estrutura de dados é O (n) para acessar qualquer nó dado.

Armazenando uma matriz de pesos de borda

• Isso seria uma complexidade de memória de O (n ^ 2) para a matriz.
• A vantagem dessa estrutura de dados é que a complexidade do tempo para acessar qualquer nó é O (1).

Dependendo de qual algoritmo você executa no gráfico e de quantos nós existem, você terá que escolher uma representação adequada.

Mais algumas coisas a serem consideradas:

1. O modelo matricial se presta mais facilmente a gráficos com arestas ponderadas, armazenando os pesos na matriz. O modelo de objeto / ponteiro precisaria armazenar pesos de borda em uma matriz paralela, o que requer sincronização com a matriz de ponteiro.

2. O modelo de objeto / ponteiro funciona melhor com gráficos direcionados do que gráficos não direcionados, porque os ponteiros precisariam ser mantidos em pares, que podem se tornar não sincronizados.

O método de objetos e ponteiros sofre de dificuldade de pesquisa, como alguns notaram, mas são bastante naturais para fazer coisas como construir árvores de pesquisa binárias, onde há uma grande quantidade de estrutura extra.

Eu, pessoalmente, adoro matrizes de adjacência porque elas tornam todos os tipos de problemas muito mais fáceis, usando ferramentas da teoria algébrica de grafos. (A k-ésima potência da matriz de adjacência fornece o número de caminhos de comprimento k do vértice i ao vértice j, por exemplo. Adicione uma matriz de identidade antes de tirar a k-ésima potência para obter o número de caminhos de comprimento <= k. Faça uma classificação n-1 menor do Laplaciano para obter o número de árvores abrangentes ... E assim por diante.)

Mas todo mundo diz que as matrizes de adjacência são caras em termos de memória! Eles estão apenas parcialmente certos: você pode contornar isso usando matrizes esparsas quando seu gráfico tiver poucas arestas. Estruturas de dados de matriz esparsa fazem exatamente o trabalho de apenas manter uma lista de adjacências, mas ainda têm toda a gama de operações de matriz padrão disponíveis, oferecendo a você o melhor dos dois mundos.

Acho que seu primeiro exemplo é um pouco ambíguo - nós como objetos e bordas como ponteiros. Você pode acompanhar isso armazenando apenas um ponteiro para algum nó raiz, caso em que acessar um determinado nó pode ser ineficiente (digamos que você queira o nó 4 - se o objeto de nó não for fornecido, talvez seja necessário procurá-lo) . Nesse caso, você também perderia partes do gráfico que não podem ser alcançadas a partir do nó raiz. Acho que é esse o caso que f64 rainbow está assumindo quando diz que a complexidade de tempo para acessar um determinado nó é O (n).

Caso contrário, você também pode manter uma matriz (ou hashmap) cheia de ponteiros para cada nó. Isso permite o acesso O (1) a um determinado nó, mas aumenta um pouco o uso da memória. Se n é o número de nós e e é o número de arestas, a complexidade espacial dessa abordagem seria O (n + e).

A complexidade do espaço para a abordagem da matriz seria ao longo das linhas de O (n ^ 2) (assumindo que as arestas são unidirecionais). Se seu gráfico for esparso, você terá muitas células vazias em sua matriz. Mas se o seu gráfico estiver totalmente conectado (e = n ^ 2), isso se compara favoravelmente com a primeira abordagem. Como RG diz, você também pode ter menos perdas de cache com esta abordagem se alocar a matriz como um pedaço de memória, o que pode tornar mais rápido seguir várias bordas ao redor do gráfico.

A terceira abordagem é provavelmente a mais eficiente em termos de espaço para a maioria dos casos - O (e) - mas tornaria a localização de todas as arestas de um determinado nó uma tarefa O (e). Não consigo pensar em um caso em que isso seria muito útil.

Dê uma olhada na tabela de comparação na wikipedia. Dá uma boa compreensão de quando usar cada representação de gráficos.

Existe outra opção: nós como objetos, arestas como objetos também, cada aresta estando ao mesmo tempo em duas listas duplamente vinculadas: a lista de todas as arestas que saem do mesmo nó e a lista de todas as arestas que vão para o mesmo nó .

struct Node {
    ... node payload ...
    Edge *first_in;    // All incoming edges
    Edge *first_out;   // All outgoing edges
};

struct Edge {
    ... edge payload ...
    Node *from, *to;
    Edge *prev_in_from, *next_in_from; // dlist of same "from"
    Edge *prev_in_to, *next_in_to;     // dlist of same "to"
};

A sobrecarga de memória é grande (2 ponteiros por nó e 6 ponteiros por borda), mas você obtém

• O (1) inserção de nó
• O (1) inserção de borda (apontadores fornecidos para nós "de" e "para")
• O (1) deleção de borda (dado o ponteiro)
• Exclusão de nó O (deg (n)) (dado o ponteiro)
• O (deg (n)) encontrando vizinhos de um nó

A estrutura também pode representar um gráfico bastante geral: multigrafo orientado com loops (ou seja, você pode ter várias arestas distintas entre os mesmos dois nós, incluindo vários loops distintos - arestas indo de x a x).

Uma explicação mais detalhada dessa abordagem está disponível aqui .

Ok, então se as arestas não têm pesos, a matriz pode ser um array binário, e usar operadores binários pode fazer as coisas acontecerem muito, muito rápido nesse caso.

Se o gráfico for esparso, o método de objeto / ponteiro parece muito mais eficiente. Manter o objeto / ponteiros em uma estrutura de dados especificamente para induzi-los a um único pedaço de memória também pode ser um bom plano, ou qualquer outro método para mantê-los juntos.

A lista de adjacências - simplesmente uma lista de nós conectados - parece de longe a mais eficiente em termos de memória, mas provavelmente também a mais lenta.

Reverter um grafo direcionado é fácil com a representação de matriz e fácil com a lista de adjacências, mas não tão bom com a representação de objeto / ponteiro.