Layouts de gráficos planares
-
23-09-2019 - |
Pergunta
Quais são algumas técnicas de minimização de sobreposição de arestas ao traçar um gráfico?(De preferência relacionado ao GraphViz) Também existe algum software que possa fazer o layout de um gráfico de forma planar?
Layout Atual - http://www.evecakes.com/doodles/master.gif
A seção rosa no canto superior esquerdo parece boa, enquanto a seção azul claro tem algumas sobreposições de borda evitáveis.
Solução
Para gráficos gerais, o problema de determinar um layout plano de um gráfico com menos arestas cruzadas (o Número de cruzamento) é NP-difícil.Portanto, alguns métodos heurísticos são usados (como o Layout baseado em força algoritmos).
A página abaixo descreve brevemente os algoritmos graphviz e sugere algumas maneiras de usá-los para obter benefícios.Também contém links para os pdfs que devem conter mais informações sobre os algoritmos:
http://rss.acs.unt.edu/Rdoc/library/Rgraphviz/html/GraphvizLayouts.html
Espero que ajude.
Outras dicas
A seguinte biblioteca Java de código aberto possui alguns algoritmos que podem ajudar no layout de gráficos planares.http://open.trickl.com/trickl-graph/index.html
Em particular, as seguintes classes fornecem soluções analíticas para o problema:
ChrobakPayneLayout (baseado na implementação Boost C++ de Aaron Windsor)http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/straight_line_drawing.html
FoldFreeLayout (Com base na localização distribuída sem âncora em redes de sensores * Nissanka B.Priyantha, Hari Balakrishnan, Erik Demaine e Seth Teller)
O que você pode querer fazer é usar algo assim como a primeira "tentativa", o que garante que não haja sobreposições, embora possa não parecer ótimo.Então você pode aplicar um algoritmo direcionado à força para espaçar os nós de maneira mais justa.
Infelizmente, a biblioteca acabou de ser lançada, por isso falta documentação.No entanto, pode ser útil fornecendo algum código real em vez de apenas teoria.