Dúvida - Grafo

Programação Java
#1

Supondo um grafo, onde temos nodos e arestas valoradas entre estes nodos. Estava pensando na possibilidade de se elaborar uma representação em um espaço 2d deste grafo. Como?

Minha ideia básica era tomar um certo nodo como origem (0,0). A partir deste nodo eu queria distribuir todos os demais neste espaço, considerando que o valor da aresta entre dois nodos representa a distância entre eles neste plano.

Estava encarando ingenuamente esta tarefa como trivial. Foi então que me dei conta que ajustar todos os demais nodos em função dessa origem é mais complicado do que parece. Simplesmente porque, tomando um nodo A e um nodo B, adjacente, e considerando uma aresta entre eles cujo valor é N. Se eu tomar A como a origem, posso posicionar B em infinitos lugares diferentes em torno de A, em um raio N.

Vocês vêem alguma solução simples para esse problema que eu não estou vendo?

Será que a planaridade do grafo influencia a viabilidade desta empreitada?

#2

Realmente essa tarefa não tem absolutamente nada de trivial.
Mas algumas APIs podem te ajudar:

Só não entendi pq vc abriu esse tópico no off-tópico, se isso é claramente uma dúvida de interface gráfica.

#3

Hum…Talvez eu tenha me expressado mal.

Na verdade, não estou pensando em exibir este grafo.
Só queria criar um modelo espacial, porque estou pensando em usar uma metáfora espacial para resolver um problema. Experiências, experiências :slight_smile:

Mas aí me dei conta de que esta tarefa não é trivial, como eu disse.
Hoje pela manhã lembrei de apis gráficas que parecem fazer isso. Mas não teho certeza de que elas fazem a distribuição dos nodos seguindo as restrições das arestas.

De qualquer forma, obrigado pela ajuda.

#4

Bem…Pelo que vi, meu tópico foi alterado para a categoria “Interface gráfica”.

Volto a dizer que meu intuito não é exibir os grafos. Minha dúvida não passa por interfaces gráficas.

Estou querendo pensar em um algoritmo que faça o mapeamento abstrato (não necessariamente para visualização) de um grafo com arestas valoradas para uma representação espacial, onde cada nodo tem uma coordenada em um espaço 2d e está posicionado no espaço a uma distância N dos nodos adjacentes, onde N representa o valor da aresta.

Esqueci de mencionar que as arestas do grafo, nesta concepção, só podem receber valores positivos.

Estava investigando a possibilidade deste mapeamento para testar uma abordagem em que eu preciso da representação espacial do grafo para inferir características mais abstratas.

É um problema de algoritmos (talvez de computação teórica), na verdade, não de interface gráfica.

Gostaria que o tópico voltasse para a categoria original.

Retomando a questão. Vocês acham que a planaridade do grafo influencia? Será que para grafos não-planares, apenas representações em um espaço superior ao bidimensional é possível? Uma representação 3d é suficiente para qualquer grafo?

#5

Estou achando que este é um problema NP. A menos que eu esteja realmente ignorando algo improtante.

Para cada nodo mapeado para a representação, eu preciso revisar todos os outros nodos e verificar se as suas coordenadas refletem as restrições da valoração da aresta. Parece um tipo de problema de satisfação de restrições.

#6

Voltei a pensar sobre o problema. Ele me parece um CSP (problema de satisfação de restrições). Parece se tratar de um problema de classe NP;

Além disso, acho que existem grafos cujas arestas são valoradas, que não podem ter representação espacial, considerando os valores das arestas como restrições entre as distâncias entre os nodos.

Vamos pensar em um exemplo aqui:
Temos 4 vértices (V1,V2,V3,V4), onde cada vértices está conectado aos 3 restantes, através de 6 arestas (A1,A2,A3,A4,A5,A6).

A seguir, caracterizo as arestas, da seguinte forma:

{Nome da aresta} : {vértices conectados} : { valor}

A1 : V1-V2 : 4
A2 : V2-V3 : 3
A3 : V3-V4 : 4
A4 : V4-V1 : 3
A5 : V1-V3 : 6
A6 : V2-V4 : 6

Se A5 e A6 tivessem como valor 5, esta representação seria possível. Os vértices e arestas formariam um retângulo, com as arestas A5 e A6 cruzando o retângulo internamente. Mas, com 6, não consigo estabilizar uma representação. Simplesmente porque não se pode satisfazer todas as restrições geométricas consideradas, ao mesmo tempo, levando em conta que estamos falando de um espaço bidimensional euclidiano, e que a distância entre os vértices é a distância euclidiana. Ou seja, para manter 6 como valor dessas arestas, o valor das demais teria que ser outro e vice-versa.

Talvez seja preciso considerar outros tipos de espaço, ou com outras dimensões, ou aceitar que nem todo grafo pode ter essa representação. Teria que ver.

De qualquer forma, alguns grafos podem ser mapeados para representação espacial. Sobretudo aqueles que são construídos justamente para representar distâncias espaciais (grafo de estradas ligando cidades, por exemplo). Talvez tu tenhas que se concentrar neste tipo de grafo. Ou melhor estudar essas propriedades abstratas, assumindo grafos que podem ter este mapeamento, ignorando, por ora, o problema de fazer o mapeamento de qualquer grafo para uma representação espacial bidimensional.

#7