Arborescence de la structure du programme - Program structure tree

Une arborescence de structure de programme (PST) est un diagramme hiérarchique qui affiche la relation d'imbrication de fragments/régions à entrée unique et à sortie unique (SESE), montrant l'organisation d'un programme informatique . Les nœuds de cet arbre représentent les régions SESE du programme, tandis que les arêtes représentent les régions d' imbrication . Le PST est défini pour tous les graphiques de flux de contrôle.

Notes bibliographiques

Ces notes répertorient les travaux importants qui ont alimenté la recherche sur l'analyse syntaxique des programmes et/ou des graphes de flux (de travail) (adapté de la section 3.5 de Polyvyanyy, Artem (2012). Structuring Process Models (Ph.D.). Université de Potsdam.).

  • Les propriétés de connectivité sont les propriétés de base des graphes et sont utiles pour tester si un graphe est planaire ou pour déterminer si deux graphes sont isomorphes. John Hopcroft et Robert Endre Tarjan (1973) ont développé un algorithme optimal (à un facteur constant près) pour diviser un graphe en composantes triconnectées. L'algorithme est basé sur la recherche en profondeur des graphes et nécessite du temps et de l'espace pour examiner un graphe avec des sommets et des arêtes.
  • Robert Endre Tarjan et Jacobo Valdes (1980) ont utilisé des composants triconnectés pour l'analyse structurelle de graphes d'écoulement biconnectés. Les composants triconnectés de la version non dirigée d'un graphe de flux se révèlent utiles pour découvrir les informations structurelles des graphes de flux dirigés. Les composants triconnectés peuvent être découverts efficacement et forment une hiérarchie de fragments SESE d'un graphe de flux.
  • Giuseppe Di Battista et Roberto Tamassia (1990) ont introduit les arbres SPQR - une structure de données qui représente la décomposition d'un graphe biconnecté par rapport à ses composants triconnectés. Essentiellement, les arbres SPQR sont les arbres d'analyse de Tarjan et Valdes. Les auteurs ont montré l'utilité des arbres SPQR pour divers algorithmes de graphes en ligne, par exemple, la fermeture transitive, les tests de planéité et l'arbre couvrant minimum. En particulier, les auteurs ont proposé une solution efficace au problème de maintenance en ligne des composantes triconnectées d'un graphe.
  • Richard C. Johnson et al. (1994) ont proposé un arbre de structure de programme (PST), une représentation hiérarchique de la structure de programme basée sur des régions d'entrée et de sortie à bord unique. Le PST peut être calculé dans le temps pour un graphe de flux arbitraire, où est l'ensemble des arêtes du graphe. L'inconvénient du PST est qu'il exploite la notion de fragment SESE basé uniquement sur les entrées et les sorties de périphérie. Ainsi, le PST ne capture pas les fragments SESE qui sont basés sur des entrées et des sorties de sommet.
  • Carsten Gutwenger et Petra Mutzel (2001) ont partagé leur expérience pratique sur le calcul en temps linéaire des composantes triconnectées de graphes biconnectés. Ils ont identifié et corrigé les parties défectueuses de l'algorithme et appliqué l'algorithme résultant au calcul des arbres SPQR. La mise en œuvre est accessible au public.
  • Chun Ouyang et al. (2006-2009) ont utilisé l'analyse pour traduire les diagrammes BPMN en processus BPEL. La notion employée de fragment est similaire à la notion de région dans. Cependant, l'algorithme d'analyse développé est non déterministe, c'est-à-dire que l'arbre d'analyse n'est pas unique pour un diagramme donné.
  • Jussi Vanhatalo et al. (2008-2009) ont introduit l'Arbre de Structure de Processus Raffiné (RPST). Étant donné un graphe de workflow, le RPST est unique, modulaire et a une granularité plus fine que tout autre arbre d'analyse connu, c'est-à-dire qu'il découvre plus de fragments SESE que toute autre technique. En fait, le RPST capture tous les fragments canoniques d'un graphe de workflow qui, à leur tour, représentent tous les fragments SESE du graphe. Le RPST peut être calculé pour un graphique de programme/workflow arbitraire.
  • Artem Polyvyanyy, Jussi Vanhatalo et Hagen Voelzer (2010) ont proposé un algorithme simplifié pour le calcul du RPST. Cet algorithme simplifié peut être utilisé de manière directe en tant que sous-routine pour le calcul du RPST d'un graphe de programme/workflow arbitraire. Les deux algorithmes, l'original et le simplifié, permettent un calcul ecace du RPST. Cependant, ils fournissent différentes caractérisations structurelles des fragments SESE canoniques.

Liens externes

Les références