Planarité possible des organigrammes

Question

J'ai une question: y a-t-il une référence (par exemple du papier) avec une preuve de la planéité des schémas de l'organigramme? Quelqu'un peut-il suggérer un algorithme pour générer des schémas (plans) d'organigramme?

Je sais qu'il existe des outils de code-à-diagramme, mais je ne suis pas au courant de leurs internes.

Answer 1

Cela dépend de ce que vous appelez un "organigramme". Si l'organigramme est le type simple, à savoir. un graphe orienté où aucun noeud ne pointe vers le haut (vers un noeud qui aurait pu être visité précédemment), alors ce que vous avez décrit est un tree dont l'intégration dans le plan est triviale.

Si toutefois votre diagramme a des boucles (cycles), il est simple de construire un contre-exemple, un graphique qui n'est pas et qui n'est pas noyable dans le plan. Pour un exemple artificiel (comme aucune restriction n'a été mentionnée), considérons le graphe complet K5, dans lequel chaque noeud est connecté à un autre. Ce graphique n'est pas planaire.

Comme pour dessiner des graphiques, je voudrais recommander l'excellent outil GraphViz qui dessine (entre autres) de beaux organigrammes avec mise en page automatique. Vous pouvez choisir un moteur de rendu qui essaie de conserver un certain ordre dans votre graphique et il existe une option explicite pour les graphiques hiérarchiques.

Answer 2

Je ne suis pas d'accord avec Hooked. Organigrammes, avec certaines restrictions (l'utilisation de boucles est PAS l'un d'entre eux), sont planaires. Quelques exemples:

• Une commande primitive unique se traduit par une courbe plane (un seul nœud)
• une séquence d'instructions: si les états peuvent être convertis en les graphes planaires, la séquence peut elle-même être converti en un plan graphique (simplement en connectant les sous-graphes)
• une fonction: le même que ci-dessus
• une boucle (repeat-until, while-do, etc) est une séquence d'instructions qui forme un cycle. Les cycles sont bien aussi, tant qu'ils nichent correctement (et ces constructions sont conçues pour imbriquer correctement).
• GOTO (goto ou break/continue/return déclarations qui peuvent sauter) sont pas ok. Si vous avez une boucle imbriquée, et de l'intérieur que vous sautez hors de la boucle externe, un tel arc croiserait clairement le cycle (boucle, fonction) qui le contient. Si le code est traduit pour quitter une boucle à la fois, ceux-ci sont bien aussi. (Cette traduction n'est pas trop différente de la simple introduction de nœuds pour modéliser les intersections).

Il doit y avoir un moyen de prouver formellement plus systématique qu'un organigramme provenant de compositions d'un ensemble particulier de constructions est plane, je voudrais pouvoir penser en 5 minutes, mais pas de chance :)

mise à jour: Soit dit en passant, goto s peut trivialement créer un K3,3 ou K5, par exemple ceci est un K5 (en bon vieux QBasic!):

00 GOTO (INT(RND * 5) * 10) 
10 GOTO (INT(RND * 5) * 10) 
20 GOTO (INT(RND * 5) * 10) 
30 GOTO (INT(RND * 5) * 10) 
40 GOTO (INT(RND * 5) * 10)