Existe-t-il un algorithme approprié pour tracer un graphe mixte de circonscription / dépendance dans un système de coordonnées?

9

Je recherche un algorithme pour dessiner un graphe mixte de circonscription / dépendance (pour une application linguistique). Un tel graphique aurait deux types de sommets différents (jetons, nœuds) et deux types d'arêtes différents (hiérarchique, non hiérarchique).

Je suis nouveau dans la théorie des graphes et les algorithmes en général, et j'espère que cette question ne se heurtera pas par exemple aux exigences de recherche de ce site. Elle devrait cependant généralement être du domaine de la théorie .

Le graphique devrait être tracé de bas en haut (je pense), car tous les jetons devraient être affichés avec la même coordonnée y, et les coordonnées y des nœuds regroupant des jetons et / ou des nœuds en constituants devront être calculées dynamiquement, par exemple, via leur plus long chemin vers un jeton.

Les arêtes hiérarchiques (utilisées pour regrouper les jetons / nœuds en constituants) devraient avoir un nombre minimum de points de pliage (idéalement 0), mais il devrait également y avoir un nombre minimum de croisements, écrasant l'ancienne exigence si nécessaire.

Les arêtes non hiérarchiques (utilisées pour les dépendances) doivent avoir un nombre minimum de croisements et être tracées sous forme de courbes de Bézier.

La deuxième meilleure chose que j'ai rencontrée est l'algorithme décrit par Buchheim et al. , améliorant l'algorithme de Walker pour fonctionner en temps linéaire.

S'il vous plaît, faites-moi savoir s'il devrait être nécessaire d'améliorer ma question, et merci beaucoup à l'avance pour tous les conseils.

ÉDITER:

Comme indiqué dans un commentaire, je dois mentionner que je veux essentiellement une disposition de graphique par défaut par un algorithme, que je - à long terme - souhaite éditer et réviser dans les possibilités Eclipse GEF . J'ai déjà examiné des options pour que Graphviz fonctionne avec GEF, mais il ne semble pas y avoir de solution de travail qui préserve toutes les fonctionnalités d'édition héritées de GEF.

Dakota du Sud
la source
Avez-vous besoin d'un algorithme ou d'un outil existant? Graphviz ( graphviz.org ) peut le faire. Vous spécifiez le graphique, éventuellement certaines options de mise en forme (pour différents types de nœuds et d'arêtes) et l'outil produira un graphique raisonnablement rendu.
Dave Clarke
@DaveClarke: Merci. Je sais que Graphviz est en mesure de le faire. Malheureusement, il ne semble pas qu'il existe actuellement aucune possibilité d'utiliser Graphviz avec un éditeur basé sur [Eclipse Graphical Editing Framework] (www.eclipse.org/gef). Par conséquent, je recherche un algorithme réel. À moins que quelqu'un sache comment brancher / porter Graphviz sur GEF bien sûr :).
sd
Il semble que l'OP recherche un algorithme (ou une formulation de problème qui capture la spécification)
Suresh Venkat
@SureshVenkat: Oui, merci pour la clarification.
sd
1
Q n'a aucune mention de l'édition et mais dans les commentaires, vous refusez graphviz et semble indiquer que vous souhaitez le modifier avec GEF. GEF est un framework / API d'édition visuelle général sur lequel d'autres "plugins" peuvent s'appuyer. vous semblez vouloir une disposition de graphique par défaut par un algorithme que vous pouvez ensuite réviser. vous suggérons de modifier votre question pour refléter cela. soit dit en passant, graphviz peut être utilisé pour générer des coordonnées qui peuvent ensuite alimenter un éditeur de graphiques. concernant l'
vzn

Réponses:

1

vous semblez vouloir ce qui suit

  • un algorithme de mise en page graphique. de nombreux algorithmes std utilisent généralement des méthodes basées sur la force où les nœuds sont connectés par des "ressorts" réplicatifs / attractifs et l'état d'équilibre / basse énergie est obtenu par une certaine quantité d'itération (de l'équation différentielle liée à la force construite globalement correspondante). la sortie de l'algorithme est un ensemble de coordonnées 2D ou 3D pour les nœuds et (généralement) les bords.
  • possibilité de modifier manuellement les résultats de cet algorithme. généralement appelé "éditeur de graphes". cela commence par les coordonnées de l'algorithme de mise en page et permet l'ajustement.

re (1) le logiciel de pointe semble être graphviz . re (2) voir par exemple cette question "quel est le meilleur éditeur de graphes" sur mathoverflow .

parcourant la galerie graphviz, voici deux types de graphiques similaires à ce que vous voulez.

Diagramme ER et feu de circulation .

vous dites que vous avez deux types d'arêtes. un moyen simple serait d'avoir des bords dirigés "vers ou loin" comme dans l'exemple des feux de circulation. ou les bords peuvent être étiquetés de deux manières comme dans le diagramme ER. les deux exemples montrent deux types de nœuds différents utilisant des formes ou des étiquettes différentes, ou un ombrage, etc., d'autres approches consisteraient à utiliser la coloration.

comme l'indiquent les mathoverflow Q / As, il existe de nombreux éditeurs de graphiques. le std avec graphviz est "dotty". voir par exemple le pdf "édition de graphiques avec dotty" par Koutsofious.

une autre technique de représentation graphique, éventuellement de grands graphiques, consiste à examiner les compositions structurelles, par exemple les décompositions de clique.

vzn
la source