Estrutura de dados para armazenar arestas de um gráfico

8

Atualmente, estou trabalhando na minha tese de mestrado, e trata-se de agrupar em gráficos. Estou trabalhando com uma ideia usando formigas para resolver o problema. Atualmente, estou trabalhando na implementação e estou me perguntando exatamente quão bem pode representar as bordas do gráfico.

Cada borda é aumentada com certas informações, como seu valor de feromônio e o número de vezes que uma formiga a visitou. Vou trabalhar com gráficos não direcionados, que podem acabar sendo muito grandes (mais de um milhão de vértices) e fiquei pensando qual é a maneira mais eficiente de armazenar as bordas e procurá-las? Eu estava pensando em aderir a uma convenção e armazenar pontos de extremidade de acordo com o que possui um ID de vértice mais baixo para e o mais alto para ( e são os pontos de extremidade da borda na estrutura de dados). Mas eu estou querendo saber como eu realizaria uma pesquisa neste caso?v1v2v1v2

Existe um mapeamento que criei da matriz de adjacência para a matriz de arestas, mas isso funciona apenas se o gráfico subjacente for um gráfico completo. Por isso, vim aqui para obter algumas sugestões de como proceder, pois preciso que minha pesquisa seja eficiente e, ao mesmo tempo, não quero aumentar o espaço de armazenamento das bordas, pois os gráficos serão enormes.

graph-theory data-structures evolutionary-computing turvar
fonte
1
Seu gráfico é esparso ou denso? Porque a resposta depende disso.
Bartosz Przybylski
Ah, eu deveria ter mencionado isso, sim, eles são principalmente gráficos esparsos. Basicamente, os gráficos com os quais vou trabalhar representam redes do mundo real que geralmente são escassas. :)
lamacento
Listas de adjacências classificadas?
Raphael

Respostas:

5

Se seu gráfico for escasso, você deve armazená-lo usando "listas" adjacentes, embora provavelmente deseje algo mais eficiente que uma lista (ou talvez não, dependendo do uso). É mais simples se você armazenar cada extremidade nos dois pontos de extremidade. Isso pode ser implementado de várias maneiras, por exemplo, você pode armazenar todos os dados em uma grande matriz e armazenar apenas ponteiros nas "listas" adjacentes.

Yuval Filmus
fonte
Até agora, tenho usado uma abordagem de lista de adjacências, onde para cada vértice tenho uma matriz de seus vizinhos (cada vértice é um objeto). Dessa forma, ajuda porque cada formiga conhece os vizinhos de todos os vértices. Mas preciso escolher a borda a seguir, com base nas informações dos feromônios e em alguns outros dados que vou calcular. Como não quero introduzir duplicação, fiquei imaginando se havia uma maneira de representar cada aresta individualmente, mas poder indexá-las de maneira eficiente ao mesmo tempo, pois precisarei de muita pesquisa para cada aresta em todas as iterações .
barrenta
Como exemplo, aqui está o possível mapeamento para os índices da matriz de arestas, se o gráfico estiver completo. Nesse caso, já sabemos que o tamanho da matriz de arestas será n (n-1), onde n é o número de vértices. Portanto, para traduzir [x] [y] a matriz de adjacência no índice da matriz (idx) pode ser a seguinte: se x <= y então idx = n * x - x * (x + 1) / 2 + (y - x - 1) else idx = n * y - y * (y + 1) / 2 + (x - y - 1) Então, digamos que edge (5,11) ou (11,5) traduza ambos para o mesmo índice de array. Mas como não estou trabalhando com gráficos completos, não consigo pensar em um mapeamento.
barrenta
2
Você continua insistindo em usar estruturas de dados que só fazem sentido para gráficos densos. Para gráficos esparsos, a abordagem é sempre armazenar, de alguma forma, para cada vértice todas as arestas incidentes nela. Não há duplicação - os dados são armazenados apenas em um local; mas há dois ponteiros para os dados. A indexação rápida pode ser implementada usando árvores de pesquisa, tabelas de hash e assim por diante. Isso permitirá que você implemente rápido e, esperançosamente, sem sobrecarga de espaço. G[x][y]
Yuval Filmus