Como reduzir o número de arestas de cruzamento em um diagrama?
Estou trabalhando em um editor de diagrama. Os diagramas exibem formas 2D ( nós ) conectadas com conectores ( arestas ).
Gostaria de adicionar uma operação que, dada uma seleção de nós, os "desembaraça" : os reposiciona para reduzir o número de arestas de cruzamento, se possível (e tudo bem se as arestas tiverem que ser desenhadas com pontos de curvatura) .
Então, eu quero um algoritmo de gráfico que, dada uma incorporação ( topológica ) de um gráfico e um subconjunto de seus nós, modifique a incorporação (sua topologia ) apenas nesses nós, a fim de minimizar o número de arestas de cruzamento.
Ao ler sobre os gráficos do ápice e navegar em Cabello e Mohar (2013) , suponho que esse problema seja difícil para o NP. Então, ficarei feliz com um algoritmo parametrizado (por exemplo, no número de arestas de cruzamento) que possui uma complexidade de tempo conhecida, polinomial, para qualquer valor de parâmetro especificado. Parece viável, mas não acho fácil criar esse algoritmo sozinho.
Onde procuro esse algoritmo?
Em software existente?
Existe alguma experiência prática significativa com essa operação? (O que parece bom na teoria pode não ser tão bom na prática, ou vice-versa.)
(Não sei onde melhor fazer esta pergunta: aqui, no StackOverflow ou MathOverflow?)
Eu suponho que a pergunta pode ser mais adequada para o StackOverflow, mas notei que perguntas semelhantes têm respostas insatisfatórias. Seguirei com uma resposta que deve ajudá-lo no final teórico, mas pode ser melhor que sua pergunta seja migrada para lá.
Há um trabalho muito profundo sendo feito aqui: complang.tuwien.ac.at/cd/ebner/ebner05da.pdf
Obrigado! Não apenas isso, mas é claramente uma apresentação muito legível do problema e uma pesquisa de algumas abordagens conhecidas.
A computação do número mínimo absoluto de cruzamento é, como você observou, . O processo de desenhar os gráficos deve ser pelo menos tão difícil quanto isso.NP-hardNP-hard
O problema colocado na pergunta é realmente mais difícil e mais envolvido do que o descrito acima. Você está considerando nós de gráfico de um determinado tamanho e forma, além de limitar o tamanho (área) do resultado. Além disso, uma noção ainda não determinada de estética é desejada. Obviamente, queremos uma heurística para isso, que não use o mínimo absoluto no caso geral. O número de nós encontrados em um aplicativo como esse provavelmente não é grande no caso médio. Desenhar a versão mínima da borda do gráfico pode ser viável para tamanhos pequenos.
Você pode estar interessado nos seguintes recursos, principalmente no primeiro:
A documentação para um recurso do pacote Graphviz apresenta um algoritmo que gera gráficos direcionados com boa aparência: http://www.graphviz.org/Documentation/TSE93.pdf
Ele possui vários outros recursos que podem ser úteis. O código fonte está localizado no site deles em EPL. Ele também inclui uma página dedicada à teoria por trás da visualização de gráficos.
Para um algoritmo de parâmetro fixo, verifique um artigo de Martin Grohe:
Computando números de cruzamento em tempo quadrático
Uma palestra de tecnologia proferida por Amina Shabbeer no RPI: Preservando Relações de Proximidade e Minimizando Passagem de Borda em Embebidos de
Um exemplo de um algoritmo probabilístico eficiente pode ser encontrado neste artigo por Julia Chuzhoy:
Um algoritmo para o problema do número de cruzamento de gráfico
Existem muitos outros recursos também. Isso deve ajudar você a começar.
Pensamentos e observações adicionais:
Aqui está uma idéia para contornar os problemas relacionados à forma e tamanho dos nós. Dado o gráfico (nós infinitamente pequenos), expanda cada nó enquanto "empurra" ou dobra as bordas para fora do caminho (por exemplo, usando splines enquanto aplica um limite de proximidade). Você precisa fazer isso com outras arestas e nós que atrapalhem, o que pode iniciar uma reação em cadeia. Veja como um equilíbrio pode ser computado eficientemente (por exemplo, estruturas moleculares). Se você não conseguir obter a forma de um nó no tamanho desejado, dimensione o diagrama inteiro.
Um usuário pode apreciar os resultados de um algoritmo aleatório. Eles poderiam usar seu recurso várias vezes até conseguirem algo de que gostassem. Evite computação redundante neste caso (não é necessário calcular um número de cruzamento novamente).
Eu adicionei topológico à minha pergunta especificamente para evitar a discussão de estética. É importante, mas não acho que eles afetem muito o problema básico - acho que eles podem ser tratados em uma etapa separada, depois de ajustar a topologia dos nós (ou seja, quais nós são cercados por outros nós).
Eu usei o Graphviz pela primeira vez há mais de 15 anos; Eu o uso aproximadamente uma vez por semana para todos os tipos de gráficos. Não estou muito impressionado com os resultados e entendo que é difícil fazer muito melhor.
Costumo visitar graphviz.org e li alguns dos documentos a que se referem. Mas ainda não encontrei uma resposta para essa pergunta específica e não está na descrição do meu trabalho familiarizar-me com a literatura. É por isso que estou perguntando aqui.
Obrigado pelas referências, no entanto - percebo que ainda é uma pesquisa atual .
A primeira coisa que tentarei é um algoritmo trivial (e, portanto, não necessariamente útil), baseado na idéia de Shabbeer. Obrigado novamente.