Planar Graph Layout
-
23-09-2019 - |
Domanda
Quali sono alcune tecniche di minimizzazione del bordo di sovrapposizione quando si posa su un grafico? (Preferibilmente correlate a GraphViz) Inoltre ci sono software esistente che può layout di un grafico in modo planare?
Layout attuale - http://www.evecakes.com/doodles/master.gif
La sezione rosa nell'angolo in alto a sinistra guarda bene mentre la sezione azzurro ha qualche vantaggio evitabile si sovrappone.
Soluzione
Per i grafici generali, il problema di una determinazione di una configurazione planare di un grafico con bordi meno attraversano ( Crossing Number ) è NP-hard. Quindi, vengono utilizzati alcuni metodi euristici (come gli algoritmi del layout di base Forza ).
La pagina di seguito descrive brevemente gli algoritmi graphviz e suggerisce alcuni modi di usarli per il bene. Essa ha anche i link ai file PDF che dovrebbe contenere ulteriori informazioni sugli algoritmi:
http://rss.acs.unt.edu/ rdoc / library / Rgraphviz / html / GraphvizLayouts.html
La speranza che aiuta.
Altri suggerimenti
Il seguente libreria Java open source ha un paio di algoritmi che possono aiutare a distendersi grafi planari. http://open.trickl.com/trickl-graph/index.html
In particolare, le seguenti classi forniscono soluzioni analitiche al problema:
ChrobakPayneLayout (in base alla Boost C ++ attuazione da Aaron Windsor) http://www.boost.org/doc/libs /1_37_0/libs/graph/doc/straight_line_drawing.html
FoldFreeLayout (sulla base di ancoraggio-Free Localizzazione Distribuito in reti di sensori * Nissanka B. Priyantha, Hari Balakrishnan, Erik Demaine, e Seth Teller)
Che cosa si potrebbe desiderare di fare è usare qualcosa come questo come il primo "tentativo", che garantisce l'assenza di sovrapposizioni, anche se non può sembrare grande. Poi si può applicare un algoritmo di forza-diretto per distanziare i nodi più equamente.
Purtroppo, la libreria è appena stato rilasciato lo è anche a corto di documentazione. Potrebbe però essere utile, fornendo un po 'di codice vero e proprio, piuttosto che solo teoria.