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.

È stato utile?

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.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top