Graphique planaires Layouts

Question

Quelles sont les techniques de minimisation de chevauchement de bord lors de la pose sur un graphique? (De préférence en rapport avec GraphViz) y sont également un logiciel existant qui peut la mise en page un graphique de façon plane?

Mise en page actuelle - http://www.evecakes.com/doodles/master.gif

La section rose dans le coin supérieur gauche semble bien tandis que la section bleu clair a un certain bord évitable chevauche.

Answer 1

Pour les graphiques générales, le problème de la détermination d'une disposition plane d'un diagramme avec des bords moins croisement (la mise en page D'OEUVRE).

La page ci-dessous décrit brièvement les algorithmes de graphviz et suggère des façons de les utiliser pour le bénéfice. Il a également des liens vers les pdfs qui devraient contenir plus d'informations sur les algorithmes:

  

http://rss.acs.unt.edu/ rdoc / bibliothèque / Rgraphviz / html / GraphvizLayouts.html

L'espoir qui aide.

Answer 2

La bibliothèque Java open source suivante a quelques algorithmes qui peuvent être utiles pour définir des plans graphiques. http://open.trickl.com/trickl-graph/index.html

En particulier, les classes suivantes fournissent des solutions analytiques au problème:

ChrobakPayneLayout (en fonction du Boost C ++ mise en œuvre par Aaron Windsor) http://www.boost.org/doc/libs /1_37_0/libs/graph/doc/straight_line_drawing.html

FoldFreeLayout (basé sur Distributed Anchor sans localisation dans les réseaux de capteurs  * Nissanka B. Priyantha, Hari Balakrishnan, Erik Demaine et Seth Teller)

Ce que vous pouvez faire est d'utiliser quelque chose comme cela comme la première « tentative » qui assure ne se chevauchent pas, mais peut ne pas sembler grand. Ensuite, vous pouvez appliquer un algorithme force dirigée à espacer les nœuds de façon plus équitable.

Malheureusement, la bibliothèque vient d'être publié alors est court sur la documentation. Il pourrait toutefois être utile en fournissant un code réel plutôt que la théorie.