Albero della struttura del programma - Program structure tree

Un albero della struttura del programma (PST) è un diagramma gerarchico che mostra la relazione di nidificazione di frammenti/regioni a ingresso singolo e uscita singola (SESE), mostrando l'organizzazione di un programma per computer . I nodi in questo albero rappresentano le regioni SESE del programma, mentre i bordi rappresentano le regioni di nidificazione . Il PST è definito per tutti i grafici di flusso di controllo.

Note bibliografiche

Queste note elencano importanti lavori che hanno alimentato la ricerca sull'analisi di programmi e/o grafici di flusso (di lavoro) (adattato dalla Sezione 3.5 in Polyvyanyy, Artem (2012). Modelli di processo di strutturazione (Ph.D.). Università di Potsdam.).

• Le proprietà di connettività sono le proprietà di base dei grafici e sono utili quando si verifica se un grafo è planare o quando si determina se due grafi sono isomorfi. John Hopcroft e Robert Endre Tarjan (1973) hanno sviluppato un algoritmo ottimale (entro un fattore costante) per dividere un grafo in componenti triconnessi. L'algoritmo si basa sulla ricerca in profondità dei grafici e richiede tempo e spazio per esaminare un grafico con vertici e bordi.${\displaystyle O(|V|+|E|)}$${\displaystyle |V|}$${\displaystyle |E|}$
• Robert Endre Tarjan e Jacobo Valdes (1980) hanno utilizzato componenti triconnessi per l'analisi strutturale di grafi di flusso biconnessi. I componenti triconnessi della versione non orientata di un grafo di flusso si sono dimostrati utili per scoprire informazioni strutturali di grafi di flusso diretti. I componenti triconnessi possono essere scoperti in modo efficiente e formare una gerarchia di frammenti SESE di un grafo di flusso.
• Giuseppe Di Battista e Roberto Tamassia (1990) hanno introdotto SPQR-trees - una struttura dati che rappresenta la scomposizione di un grafo biconnesso rispetto ai suoi componenti triconnessi. Essenzialmente, gli alberi SPQR sono gli alberi di analisi di Tarjan e Valdes. Gli autori hanno mostrato l'utilità degli alberi SPQR per vari algoritmi di grafi in linea, ad esempio chiusura transitiva, test di planarità e albero di copertura minimo. In particolare, gli autori hanno proposto una soluzione efficiente al problema della manutenzione in linea delle componenti triconnesse di un grafo.
• Richard C. Johnson et al. (1994) hanno proposto un albero della struttura del programma (PST), una rappresentazione gerarchica della struttura del programma basata su regioni di entrata e di uscita a bordo singolo. Il PST può essere calcolato in tempo per un grafo di flusso arbitrario, dove è l'insieme degli archi nel grafico. Lo svantaggio del PST è che sfrutta la nozione di un frammento SESE basato solo su entrate e uscite edge. Pertanto, il PST non cattura quei frammenti SESE che si basano su entrate e uscite di vertici.${\displaystyle O(|E|)}$${\displaystyle E}$
• Carsten Gutwenger e Petra Mutzel (2001) hanno condiviso la loro esperienza pratica sul calcolo del tempo lineare delle componenti triconnesse di grafi biconnessi. Hanno identificato e corretto le parti difettose dell'algoritmo e applicato l'algoritmo risultante al calcolo degli alberi SPQR. L'implementazione è pubblicamente disponibile.

• Chun Ouyang et al. (2006-2009) hanno utilizzato l'analisi per tradurre i diagrammi BPMN in processi BPEL. La nozione utilizzata di frammento è simile alla nozione di regione in. Tuttavia, l'algoritmo di analisi sviluppato non è deterministico, ovvero l'albero di analisi non è unico per un dato diagramma.
• Jussi Vanhatalo et al. (2008-2009) ha introdotto il Refined Process Structure Tree (RPST). Dato un grafico del flusso di lavoro, l'RPST è unico, modulare ed è a grana più fine rispetto a qualsiasi altro albero di analisi noto, ovvero scopre più frammenti SESE di qualsiasi altra tecnica. Infatti, l'RPST cattura tutti i frammenti canonici di un grafico del flusso di lavoro che, a loro volta, rappresentano tutti i frammenti SESE del grafico. L'RPST può essere calcolato per un programma/grafico flusso di lavoro arbitrario.
• Artem Polyvyanyy, Jussi Vanhatalo e Hagen Voelzer (2010) hanno proposto un algoritmo semplificato per il calcolo dell'RPST. Questo algoritmo semplificato può essere impiegato in modo diretto come subroutine per il calcolo dell'RPST di un grafo di programma/flusso di lavoro arbitrario. Entrambi gli algoritmi, quello originale e quello semplificato, consentono un calcolo eciente dell'RPST. Tuttavia, forniscono diverse caratterizzazioni strutturali dei frammenti SESE canonici.

link esterno

• Implementazione Java del Refined Process Structure Tree nella libreria jBPT (vedi classe RPST nel modulo jbpt-deco). L'implementazione segue l'algoritmo descritto in

Riferimenti