Program structure tree

A program structure tree (PST) is a hierarchical diagram that displays the nesting relationship of single-entry single-exit (SESE) fragments/regions, showing the organization of a computer program. Nodes in this tree represent SESE regions of the program, while edges represent nesting regions. The PST is defined for all control flow graphs.

Bibliographical Notes

These notes list important works which fueled research on parsing of programs and/or (work)flow graphs (adapted from Section 3.5 in Polyvyanyy, Artem (2012). Structuring Process Models (Ph.D.). University of Potsdam.).

• The connectivity properties are the basic properties of graphs and are useful when testing whether a graph is planar or when determining if two graphs are isomorphic. John Hopcroft and Robert Endre Tarjan (1973) developed an optimal (to within a constant factor) algorithm for dividing a graph into triconnected components.^[1] The algorithm is based on the depth-first search of graphs and requires $O(|V|+|E|)$ time and space to examine a graph with $|V|$ vertices and $|E|$ edges.
• Robert Endre Tarjan and Jacobo Valdes (1980) used triconnected components for structural analysis of biconnected flow graphs.^[2] The triconnected components of the undirected version of a flow graph are shown to be useful for discovering structural information of directed flow graphs. The triconnected components can be discovered efficiently and form a hierarchy of SESE fragments of a flow graph.
• Giuseppe Di Battista and Roberto Tamassia (1990) introduced SPQR-trees^[3] - a data structure which represents decomposition of a biconnected graph with respect to its triconnected components. Essentially, SPQR-trees are the parse trees of Tarjan and Valdes.^[2] The authors showed the usefulness of SPQR-trees for various on-line graph algorithms, e.g., transitive closure, planarity testing, and minimum spanning tree.^[3] In particular, the authors proposed an efficient solution to the problem of on-line maintenance of the triconnected components of a graph.^[4]
• Richard C. Johnson et al. (1994) proposed a program structure tree (PST), a hierarchical representation of program structure based on single edge entry and single edge exit regions.^[5][6] The PST can be computed in $O(|E|)$ time for an arbitrary flow graph, where $E$ is the set of edges in the graph. The disadvantage of the PST is that it exploits the notion of a SESE fragment based on edge entries and exits only. Thus, the PST does not capture those SESE fragments which are based on vertex entries and exits.
• Carsten Gutwenger and Petra Mutzel (2001) shared their practical experience on linear time computation of the triconnected components of biconnected graphs.^[7] They have identified and corrected the faulty parts of the algorithm in^[1] and applied the resulting algorithm to the computation of SPQR-trees. The implementation is publicly available.

• Chun Ouyang et al. (2006-2009) used parsing to translate BPMN diagrams into BPEL processes.^[8][9] The employed notion of a fragment is similar to the notion of a region in.^[5] However, the developed parsing algorithm is non-deterministic, i.e., the parse tree is not unique for a given diagram.
• Jussi Vanhatalo et al. (2008-2009) introduced the Refined Process Structure Tree (RPST).^[10][11][12] Given a workflow graph, the RPST is unique, modular, and is finer grained than any other known parse tree, i.e., it discovers more SESE fragments than any other technique. In fact, the RPST captures all canonical fragments of a workflow graph which, in turn, represent all SESE fragments of the graph. The RPST can be computed for an arbitrary program/workflow graph.
• Artem Polyvyanyy, Jussi Vanhatalo, and Hagen Voelzer (2010) proposed a simplified algorithm for computation of the RPST.^[13] This simplified algorithm can be employed in a straightforward way as a subroutine for computation of the RPST of an arbitrary program/workflow graph. Both algorithms, the original and the simplified one, allow for an efficient computation of the RPST. However, they provide different structural characterizations of canonical SESE fragments.

External links

• Java implementation of the Refined Process Structure Tree in the jBPT library (see RPST class in jbpt-deco module). The implementation follows the algorithm described in^[13]

References

1. Hopcroft, John; Tarjan, Robert (1973), "Dividing a graph into triconnected components", SIAM Journal on Computing 2 (3): 135–158, doi:10.1137/0202012.
2. Tarjan, Robert; Valdes, Jacobo (1980), Prime subprogram parsing of a program, pp. 95–105, doi:10.1145/567446.567456.
3. Di Battista, Giuseppe; Tamassia, Roberto (1990), "On-line graph algorithms with SPQR-trees", Proc. 17th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 443, Springer-Verlag, pp. 598–611, doi:10.1007/BFb0032061
4. Di Battista, Giuseppe; Tamassia, Roberto (1996), "On-line maintenance of triconnected components with SPQR-trees", Algorithmica 15 (4): 302–318, doi:10.1007/BF01961541
5. Johnson, Richard Craig; Pearson, David; Pingali, Keshav (1994), The Program Structure Tree: Computing Control Regions in Linear Time, pp. 171–185, doi:10.1145/178243.178258
6. Johnson, Richard Craig (1995). Efficient Program Analysis using Dependence Flow Graphs (Ph.D.). Cornell University.
7. Gutwenger, Carsten; Mutzel, Petra (2001), "A linear time implementation of SPQR-trees", Proc. 8th International Symposium on Graph Drawing (GD 2000), Lecture Notes in Computer Science 1984, Springer-Verlag, pp. 77–90, doi:10.1007/3-540-44541-2_8
8. Ouyang, Chun; Dumas, Marlon; ter Hofstede, Arthur H. M.; van der Aalst, Wil M. P. (2006), From BPMN process models to BPEL web services, pp. 285–292
9. Ouyang, Chun; Dumas, Marlon; van der Aalst, Wil M. P.; ter Hofstede, Arthur H. M.; Mendling, Jan (2009), "From business process models to process-oriented software systems", ACM Transactions on Software Engineering and Methodology 19 (1): 2:1–2:37, doi:10.1007/BF01961541
10. Vanhatalo, Jussi; Voelzer, Hagen; Koehler, Jana (2008), The refined process structure tree, pp. 100–115, doi:10.1007/978-3-540-85758-7_10
11. Vanhatalo, Jussi; Voelzer, Hagen; Koehler, Jana (2009), "The refined process structure tree", Data and Knowledge Engineering 68 (9): 793–818, doi:10.1016/j.datak.2009.02.015
12. Vanhatalo, Jussi (2009). Process Structure Trees: Decomposing a Business Process Model into a Hierarchy of Single-Entry-Single-Exit Fragments (Ph.D.). University of Stuttgart.
13. Polyvyanyy, A.; Vanhatalo, J.; Völzer, H. (2010), "Simplified Computation and Generalization of the Refined Process Structure Tree", Web Services and Formal Methods, Lecture Notes in Computer Science 6551, Springer Berlin Heidelberg, pp. 25–41, doi:10.1007/978-3-642-19589-1_2, ISBN 978-3-642-19588-4