UNIVERSITÀ DEGLI
STUDI DI PADOVA
Facoltà di Scienze MM.FF.NN.
Corso di Laurea Specialistica in Informatica
Tesi di Laurea:
GENERAZIONE DI GRAFI
IN BUSINESS PROCESS MANAGEMENT NOTATION
Laureanda: Contiero Erika
Relatore: prof. Massimo Marchiori
A.A. 2009/2010
Università degli Studi di Padova - LS Informatica
1. Introduzione
Pagina 2
Generazione di grafi in BPMN - Contiero Erika
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
1. Introduzione
Indice
1.
2.
3.
4.
Introduzione ...................................................................................................................................... 5
1.1.
Scopo del progetto .................................................................................................................... 5
1.2.
Struttura del documento ........................................................................................................... 6
Definizione del dominio..................................................................................................................... 7
2.1.
Il graph drawing ......................................................................................................................... 7
2.2.
Business Process Modelling Notation ....................................................................................... 8
2.2.1.
Cos’è la BPMN ....................................................................................................................... 8
2.2.2.
Le basi della BPMN ................................................................................................................ 8
2.2.3.
Usi generali della BPMN ...................................................................................................... 12
2.2.4.
Il valore aggiunto nel modellare attraverso la BPMN ......................................................... 13
Applicazione in un prodotto open source ....................................................................................... 14
3.1.
L’azienda promotrice ............................................................................................................... 14
3.2.
SpagoWorld e l’approccio open source ................................................................................... 14
3.3.
Spagic e il monitor dei processi ............................................................................................... 15
3.4.
La collocazione di questo progetto.......................................................................................... 17
Fase di analisi ................................................................................................................................... 18
4.1.
Requisiti di progetto ................................................................................................................ 19
4.2.
Confronto tra librerie............................................................................................................... 20
4.2.1.
Le librerie ............................................................................................................................. 20
4.2.2.
Librerie selezionate ............................................................................................................. 27
4.2.3.
La scelta ............................................................................................................................... 28
4.3.
5.
6.
Uso della libreria Zest .............................................................................................................. 29
4.3.1.
Struttura delle classi ............................................................................................................ 29
4.3.2.
Aspetto dei nodi .................................................................................................................. 32
Fase di progettazione ...................................................................................................................... 33
5.1.
L’algoritmo gerarchico per grafi orientati ............................................................................... 34
5.2.
Validità del grafo...................................................................................................................... 36
5.3.
Rimozione dei cicli ................................................................................................................... 36
5.4.
Assegnazione del rank ............................................................................................................. 38
5.5.
Creazione strutture virtuali ..................................................................................................... 46
5.6.
Ordinamento dei nodi nei rank ............................................................................................... 47
5.7.
Posizionamento dei nodi ......................................................................................................... 52
5.8.
Assegnazione delle coordinate ................................................................................................ 54
La libreria realizzata ......................................................................................................................... 56
6.1.
Dettagli implementativi ........................................................................................................... 56
6.2.
I risultati ottenuti ..................................................................................................................... 58
Pagina 3
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
1. Introduzione
7.
Fase di test ....................................................................................................................................... 67
8.
Tracciamento dei requisiti ............................................................................................................... 70
9.
Conclusioni ...................................................................................................................................... 72
10.
Bibliografia ....................................................................................................................................... 73
Pagina 4
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
1. Introduzione
1. Introduzione
1.1. Scopo del progetto
La Business Process Modeling Notation (BPMN) è una rappresentazione grafica per la descrizione di
processi di business come workflow. Il suo obiettivo primario è quello di fornire una notazione
standard, comprensibile per tutti gli stakeholders. La modellazione in BPMN si effettua attraverso
diagrammi o grafi, che fanno uso di elementi grafici. Lo studio affrontato riguarda la produzione di
tali diagrammi come immagini a partire dalle informazioni sugli elementi che li compongono.
In particolare, è stato oggetto di studio la generazione di un’immagine partendo dalle informazioni
su un grafo quali il numero, il tipo, la dimensione e le etichette dei nodi che lo compongono, le
immagini elementari con cui rappresentare i nodi, le transizioni tra i nodi e lo stile grafico con cui le
si vogliono rappresentate.
Tra tali informazioni non è previsto venga fornito anche il posizionamento dei nodi: quest’ultimo
deve essere calcolato in modo opportuno dalle informazioni fornite, attraverso l’utilizzo di un
algoritmo di autolayout, ovvero di un algoritmo che determini il corretto posizionamento degli
elementi grafici e dei testi che compongono il grafo, con l’obiettivo di generare un’immagine che
rappresenti un diagramma leggibile, comprensibile, ben strutturato e ordinato. È stato oggetto del
progetto quindi, anche lo studio degli algoritmi di autolayout esistenti e delle librerie che li
implementano.
Una volta esaminati gli algoritmi e la loro implementazione, è stato oggetto del progetto
l’applicazione delle soluzioni individuate allo scopo di creare una libreria Java con questa
funzionalità.
Il risultato dello studio e della creazione di una libreria con queste funzionalità troverà applicazione
come componente di Spagic, una piattaforma Free Open Source per la progettazione, lo sviluppo e
la gestione di soluzioni SOA/BPM.
Pagina 5
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
1. Introduzione
1.2. Struttura del documento
Questo documento di tesi presenta il cammino di studio che ha portato al prodotto in oggetto,
cammino sviluppato nelle seguenti sezioni.
Una sezione di definizione del dominio che illustra:
o
una panoramica sulle basi della Business Process Management Notation, notazione
sulla quale si basa la creazione di diagrammi di processo; tale panoramica è
indispensabile per iniziare a comprendere il dominio d’interesse del prodotto;
o
una breve panoramica sulla letteratura del graph drawing e sugli studi condotti fino ad
oggi su questo tema.
Una sezione che illustra il prodotto FOSS Spagic, dove trova applicazione il lavoro fatto:
o
una sezione che descrive l’azienda promotrice del progetto SpagoWorld, che ha
supportato la realizzazione di questo lavoro;
o
una descrizione della vision alla base di SpagoWorld ed il licensing dei progetti;
o
una breve descrizione del prodotto Spagic, e della Spagic Console che farà uso della
libreria realizzata in questo lavoro.
Una sezione che illustra la fase di analisi del progetto, in cui vengono illustrati i requisiti richiesti
al prodotto, seguiti dalla ricerca della libreria Java esistente che rispetti il maggior numero di
requisiti, da assumere come libreria di partenza per raggiungere gli obiettivi. Vengono illustrate
le considerazioni e le conclusioni relative a questa ricerca, e soprattutto viene illustrata la scelta
effettuata e lo studio della libreria selezionata.
Dal momento che la migliore libreria individuata è comunque mancante per quanto riguarda
l’algoritmo di autolayout opportuno per diagrammi in BPMN, è seguita (e perciò viene qui
descritta) la fase di progettazione dell’algoritmo di layout. Tale progettazione prevede vari
passi: la rimozione dei cicli del grafo, l’assegnazione del rank (o layer verticale), l’utilizzo di
catene di nodi dummy, l’ordinamento dei nodi all’interno dei rank, il posizionamento dei nodi
orizzontalmente, e infine l’assegnazione delle coordinate finali ai nodi. Per ognuno di questi
passi illustriamo lo pseudocodice che è stato poi implementato.
Infine, una sezione che descrive alcuni aspetti rilevanti dei dettagli implementativi della libreria
realizzata.
Pagina 6
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
2. Definizione del dominio
2. Definizione del dominio
2.1. Il graph drawing
Il graph drawing affronta il problema di costruire rappresentazioni geometriche di grafi, reti e
strutture correlate. Le rappresentazioni geometriche dei grafi sono state oggetto di studio per i
matematici per secoli, per la visualizzazione o per lo studio geometrico degli stessi.
Negli anni '60 gli informatici cominciarono ad utilizzare grafi come diagrammi per una migliore
comprensione del software. L'articolo di Knuth del 1963 sui flowchart è stato probabilmente il
primo articolo che presentò un algoritmo per disegnare un grafo a scopo di visualizzazione. Oggi, la
generazione automatica di disegni di grafi trova molte applicazioni: nell'ingegneria del software,
nelle basi di dati, nei sistemi informativi, nei sistemi real-time, nei sistemi di supporto alle decisioni,
ecc.
Molti sono gli standard esistenti per disegnare i grafi, a seconda della loro applicazione, ma tutti
hanno l'obiettivo della leggibilità, ovvero di comunicare il significato informativo del grafo in modo
chiaro e rapido. Il principio della leggibilità può essere a sua volta espresso attraverso molti criteri
estetici, ne sono esempi la minimizzazione degli incroci tra archi, la planarità, la simmetria, il
corretto utilizzo dello spazio a disposizione per il layout.
Vari sono gli approcci per il layout di un grafo, ne sono alcuni esempi noti nella letteratura gli
approcci Topology-shape-metrics, Hierachical, Visibility, Argumentation, Force-Directed, Divide and
Conquer.
In particolare in questo documento andremo ad utilizzare l’approccio Hierarchical (gerarchico) che
consente di tracciare layered drawings di grafi orientati, ovvero di rappresentarli attraverso livelli.
Questo metodo è stato presentato nel 1981 da Sugiyama, Tagawa e Toda, e successivamente è
stato oggetto di numerosi miglioramenti ed ulteriori studi, nonché di moltissime implementazioni,
anche all’interno di noti prodotti proprietari per il graph drawing.
Pagina 7
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
2. Definizione del dominio
2.2. Business Process Modelling Notation
Questa sezione ha lo scopo di fornire una panoramica di alto livello e un’introduzione alla Business
Process Modeling Notation. Si tratterà in breve il contesto e l'uso della BPMN, oltre alla notazione
di base, cioè gli oggetti grafici che compongono la notazione e come questi lavorano insieme come
parte di un Business Process Diagram. Verranno trattati gli svariati usi della BPMN, includendo
considerazioni su quanto il livello di precisione richiesto influisca sul contenuto di un diagramma e
verrà definito il valore dell’uso della BPMN come una notazione standard.
2.2.1. Cos’è la BPMN
La Business Process Management Initiative (BPMI) ha sviluppato una notazione standard detta
Business Process Modeling Notation (BPMN). Le specifiche della BPMN 1.0 sono state rilasciate nel
maggio 2004. Tali specifiche rappresentano più di due anni di lavoro da parte della Notation
Working Group. Lo scopo primario del lavoro sulla BPMN è stato di fornire una notazione
prontamente comprensibile da parte di tutti gli utenti del business, dall’analista che crea la bozza
iniziale dei processi, allo sviluppatore tecnico responsabile dell’implementazione della tecnologia
che esegue quei processi, fino agli utenti che monitorano e gestiscono tali processi. La BPMN
determina anche una soluzione standardizzata per il problema del gap tra il design dei processi e la
loro implementazione.
La BPMN definisce il concetto di Business Process Diagram (BPD), ovvero un diagramma basato su
tecniche di flowcharting, per creare modelli grafici per le operazioni dei processi di business. Un
modello di processo di business è una rete di oggetti grafici, che rappresentano attività, e controlli
di flusso che definiscono l’ordine della loro esecuzione.
2.2.2. Le basi della BPMN
Un BPD è composto da un insieme di elementi grafici. Tali elementi consentono uno sviluppo
facilitato di diagrammi semplici, il cui aspetto risulta familiare agli analisti perché basato sui
diagrammi di flusso.
Gli elementi sono stati scelti in modo da essere distinguibili tra loro e in modo che le figure
utilizzate fossero familiari alla maggior parte degli utenti. Ad esempio, le attività sono dei rettangoli
e i punti di decisione sono dei rombi.
L’enfasi è posta sulla precisa intenzione di creare un meccanismo semplice per creare modelli di
processi di business, gestendo allo stesso tempo le complessità ad essi relative. L’approccio
intrapreso per gestire entrambi questi requisiti contrastanti è stato di organizzare l’aspetto grafico
della notazione in specifiche categorie. Fornendo un insieme ristretto di categorie di notazione,
Pagina 8
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
2. Definizione del dominio
l’utente che legge il diagramma può facilmente riconoscere i tipi base di elemento e comprendere il
significato del diagramma.
All’interno delle categorie di base degli elementi possono essere aggiunte variazioni e informazioni
ulteriori per supportare i requisiti di complessità senza dover cambiare drasticamente l’aspetto di
base del diagramma.
Le quattro categorie di base di elementi sono:
Flow Objects
Connecting Objects
Swimlanes
Artifacts
Figura 1 - Elementi di base della BPMN
(Palette di Spagic Studio)
Pagina 9
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
2. Definizione del dominio
Flow Objects
Un BPD ha un insieme ristretto di core elements, caratteristica che consente agli utenti di non dover
imparare a riconoscere un numero eccessivo di forme diverse.
I tre oggetti di flusso sono:
Event
Un event è rappresentato da un cerchio, e rappresenta qualcosa che accade durante il corso di un
processo. Tali eventi influiscono sul flusso del processo e normalmente hanno una causa (trigger) o
un effetto (result). Ai cerchi che rappresentano gli eventi viene assegnato un nome (eventualmente
scritto all’interno) per distinguere tra loro eventi dello stesso tipo.
I tipi di eventi sono tre, e il tipo si basa su come l’evento influenza il flusso: Start, Intermediate, End.
Activity
Un’activity è rappresentata da un rettangolo con gli angoli arrotondati, e si tratta di un termine
generico con cui si definisce un lavoro da effettuare. Può essere singola o composta. I tipi di attività
sono: Task e Sub-process.
Gateway
Un gateway è rappresentato dalla ben nota forma a rombo ed è utilizzato per controllare la
divergenza o la convergenza del flusso. Perciò determinerà decisioni che biforcano il flusso in
cammini diversi, o lo riuniscono.
Connecting Objects
Le connessioni vengono utilizzate per connettere tra loro i flow objects che compongono il
diagramma, creando così la struttura scheletro del processo. Ci sono tre oggetti di connessione a
fornire questa funzione. I tre connettori sono:
Sequence Flow
Una connessione di tipo Sequence Flow è rappresentata da una linea continua, con un capo a forma
di freccia, ed è utilizzata per mostrare l’ordine con cui le attività devono essere eseguite in un
processo.
Message Flow
Una connessione di tipo Message Flow è rappresentata da una linea tratteggiata con un capo a
forma di freccia vuota all’interno, ed è utilizzato per mostrare il flusso dei messaggi tra due diversi
Process Participants, che inviano e ricevono. Nella BPMN due Pool nel diagramma rappresentano
due distinti Participants, e tra di essi possono essere scambiati messaggi.
Association
Una connessione di tipo Association è rappresentata da una linea a puntini con un capo a forma di
freccia, ed è utilizzato per associare dati, testo o altri Artifacts agli oggetti del flusso. Sono utilizzate
ad esempio per evidenziare input ed output delle attività.
Pagina 10
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
2. Definizione del dominio
Per i designer che richiedono o desiderano un basso livello di precisione per creare modelli di
processi a scopo di documentazione o di comunicazione, i core elements e i connettori forniranno
la possibilità di creare facilmente diagrammi intuitivi.
Per i designer che richiedono un alto livello di precisione per creare modelli di processi, che saranno
oggetto di analisi dettagliate o saranno gestite da Business Process Management System (BPMS),
possono essere aggiunti dettagli agli elementi core, mostrati attraverso marcatori interni.
Swimlanes
Molte metodologie di modellazione dei processi utilizzano il concetto delle swimlanes come
meccanismo per organizzare le attività in categorie visivamente separate, e per illustrare funzioni
diverse o diverse responsabilità. La BPMN supporta il concetto delle swimlanes con due costrutti
principali. I due tipi di oggetti swimlanes dei BPD sono:
Pool
Un Pool in un processo rappresenta un Participant, un partecipante, e agisce come contenitore per
partizionare l’insieme di attività, solitamente in contesti B2B.
Lane
Una Lane è una sotto-partizione in un Pool che si estende per la sua intera lunghezza. Le Lane sono
utilizzate per organizzare e categorizzare le attività.
I Pool sono utilizzati quando un diagramma coinvolge due entità di business separate. Le attività
all’interno di un Pool sono considerate un processo. Perciò il Sequence Flow può non attraversare il
confine tra un Pool e l’altro. Il Message Flow è definito come il meccanismo che mostra la
comunicazione tra due partecipanti, e perciò può connettere due Pool o gli oggetti al loro interno.
Le Lane sono più strettamente correlate con le swimlane delle metodologie tradizionali di
modellazione. Sono spesso utilizzate per separare attività associate a funzioni specifiche o specifici
ruoli. Il Sequence Flow può attraversare i confini tra una Lane e l’altra, ma il Message Flow non
dovrebbe essere utilizzato tra Flow Objects in Lane diverse dello stesso Pool.
Artifacts
La BPMN è stata progettata per consentire a chi modella una certa flessibilità nell’estendere la
notazione di base e nel fornire l’abilità di modellare specifiche situazioni in modo appropriato. Un
qualsiasi numero di Artifacts può essere aggiunto ad un diagramma, come opportuno per il
contesto del processo che si sta modellando. I tre tipi di Artifacts predefiniti sono:
Data Objects
I Data Objects sono un meccanismo per mostrare come i dati sono richiesti o prodotti dalle attività.
Sono connessi alle attività tramite connessioni di tipo associazione.
Pagina 11
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
2. Definizione del dominio
Groups
Un gruppo è rappresentato da un rettangolo con gli angoli arrotondati tratteggiato. Può essere
usato a scopo di documentazione o di analisi, ma non ha alcun effetto sul Sequence Flow.
Annotations
Le Annotations sono un meccanismo per fornire informazioni come testo aggiuntivo.
Chi modella può aggiungere un proprio tipo di Artifact, per aggiungere più dettagli su come il
processo è eseguito, su input e output delle attività nel processo. In ogni caso, la struttura di base
del processo rimane invariata nonostante l’aggiunta degli artifacts nel diagramma.
2.2.3. Usi generali della BPMN
La modellazione dei processi di business è usata per comunicare un’ampia quantità di informazioni
a molti tipi di utenti. La BPMN è studiata per coprire molti tipi di modellazione e permette la
creazione di segmenti di processi come anche processi end-to-end. Nella varietà di obiettivi del
process modelling ci sono due tipi base di modelli che possono essere creati con un BPD:
Collaborative (Public) B2B Processes
Internal (Private) Business Processes
Collaborative B2B Processes
Un Collaborative B2B process descrive l’interazione tra due o più entità di business. I diagrammi per
questo tipo di processi hanno generalmente un punto di vista globale, ovvero non approfondiscono
nessun partecipante in particolare, ma mostrano le interazioni tra i partecipanti. Le interazioni sono
rappresentate come una sequenza di attività e lo scambio di messaggi tra esse.
Le attività per i partecipanti possono essere considerate i loro punti di contatto, perciò, il processo
definisce l’interazione visibile al pubblico per ogni partecipante.
Quando si osserva un processo mostrato in un Pool, cioè un partecipante, il processo pubblico è
anche detto processo astratto. I processi reali, quelli interni, tipicamente conterranno più attività e
più dettagli di quanto non venga mostrato dal processo collaborativo B2B.
Internal business processes
Un processo di business interno generalmente pone il focus sul punto di vista del business di una
singola organizzazione. Sebbene i processi interni spesso mostrino le interazioni con i partecipanti
esterni, essi definiscono le attività che generalmente non sono visibili al pubblico. Se le swimlanes
sono utilizzate, allora il processo di business interno sarà contenuto in un singolo Pool. Il Sequence
Flow è perciò contenuto nel Pool e non attraversa i confini dello stesso. Il Message Flow può
Pagina 12
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
2. Definizione del dominio
attraversare i confini del Pool e mostrare le interazioni che esistono tra processi di business interni
diversi. Perciò un singolo Business Process Diagram può mostrare più processi di business private.
Diversi obiettivi – diversi livelli di precisione
La modellazione di un processo di business spesso comincia catturando le attività di alto livello e
facendo poi un’operazione di drill down verso i livelli di dettaglio in diagrammi separati. Ci possono
essere più livelli di diagramma, a seconda della metodologia usata per lo sviluppo del modello.
Comunque, la BPMN rimane indipendente da ogni metodologia di modellazione specifica.
2.2.4. Il valore aggiunto nel modellare attraverso la BPMN
Lo sviluppo della BPMN è un passo importante verso la riduzione della frammentazione che esiste a
causa della moltitudine di notazioni e di strumenti per la modellazione dei processi. Il BPMI
Notation Working Group ha sfruttato la competenza e l’esperienza con le molte notazioni esistenti
e ha cercato di consolidare le migliori idee provenineti da queste notazioni divergenti in un’unica
notazione standard. Esempi di altre notazioni o metodologie che sono state revisionate sono: UML
Activity Diagram, UML EDOC Business Processes, IDEF, ebXML BPSS, Activity-Decision Flow (ADF)
Diagram, RosettaNet, LOVeM, ed Event-Process Chains (EPCs). Questa frammentazione ha
ostacolato l’adozione diffusa dei sistemi interoperabili di business process management. Una
notazione di modellazione standard ben supportata aumenta la chiarezza tra il lato business e gli
utenti finali dell’IT.
Un altro fattore che ha guidato lo sviluppo della BPMN sta nel fatto che, storicamente, i modelli di
processi di business sviluppati dal lato business erano tecnicamente separati dalle rappresentazioni
dei processi richieste per implementarli e metterli in esecuzione. Perciò, era necessario tradurre
manualmente i modelli di processi di business originali in modelli d’esecuzione. Tali traduzioni sono
ovviamente fonte di errore e rendono difficoltosa la comprensione dell’evoluzione e delle
performance dei processi.
Pagina 13
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
3. Applicazione in un prodotto open source
3. Applicazione in un prodotto open source
3.1. L’azienda promotrice
Engineering Ingegneria Informatica S.p.A. è un’azienda di
analisi, progettazione e sviluppo software, nata nel 1980 a
Padova, e composta attualmente di 11 società operative
specializzate per segmento di mercato o per linee di business. Engineering è un player di
dimensione internazionale ed è il terzo operatore IT in Italia in software e servizi. L'offerta di
Engineering si colloca lungo l’intera catena di valore del software: consulenza, system & business
integration, servizi di outsourcing, prodotti e soluzioni verticali.
3.2. SpagoWorld e l’approccio open source
SpagoWorld è un'iniziativa di software libero e open source
promossa da Engineering Ingegneria Informatica S.p.A., i cui
progetti sono caratterizzati dalla distribuzione in licenza GNU
LGPL nella loro versione completa, facilmente adattabili alle
esigenze degli utenti perché sviluppati con approccio di
piattaforma d’integrazione, pensati per l’applicazione a livello industriale e mission-critical ma con
attenzione alla comunità di contributori del mondo accademico e della ricerca, e facenti parte di un
ecosistema del valore che ha inizio nella comunità del Consorzio OW2.
I progetti SpagoWorld appartengono alla nuova generazione di progetti open source caratterizzati
da: approccio olistico e sviluppo pianificato, progettazione complessa di soluzioni in domini verticali
per rispondere a requisiti di business, processo di sviluppo maturo, coinvolgimento di una ampia
comunità di utenti, aziende ed organizzazioni, specialisti open source, consulenti e sviluppatori, e,
infine, supporto garantito.
SpagoWorld promuove lo sviluppo sostenibile dei progetti per consentire alle aziende di conseguire
i propri obiettivi mission-critical in un quadro di affidabilità generale, garantita dalla qualità dello
sviluppo, dall'utilizzo di standard aperti e dall'innovazione. La strategia dei progetti SpagoWorld è
quella di condividere gli sviluppi con le comunità, di consolidare le soluzioni open source a livello
industriale, di stabilire partnership internazionali e di indirizzare la road-map evolutiva verso
iniziative industriali. Lo sviluppo sostenibile si basa su: visione centrata sugli obiettivi di progetto,
sviluppi evolutivi, chiaro modello di business, servizi di supporto e crescita della comunità, modello
di licenza e di sottoscrizione che sostenga un'evoluzione libera e duratura dei progetti, costi
ragionevoli per servizi di supporto efficaci.
Pagina 14
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
3. Applicazione in un prodotto open source
Quattro sono i progetti principali dell'iniziativa:
SpagoBI: la piattaforma libera per lo sviluppo di progetti di Business
Intelligence in un ambiente integrato e flessibile.
Spagic: la piattaforma libera per la governance dei servizi e lo sviluppo di
applicazioni SOA tramite la realizzazione di un Universal Middleware
altamente modulare e configurabile.
Spago4Q: la piattaforma libera per la misura, l'analisi ed il monitoraggio
della Qualità di prodotti, processi di sviluppo e servizi di gestione
software.
Spago: il Java Enterprise Wide Framework per lo sviluppo di applicazioni
web e multicanale in ambienti SOA.
3.3. Spagic e il monitor dei processi
Spagic è uno dei quattro progetti di SpagoWorld, ed
è una piattaforma libera per la governance dei
servizi
e
lo
sviluppo
di
applicazioni
SOA,
attualmente alla release 3.0.
Spagic 3 offre tutti gli strumenti a supporto della
governance di progetti SOA: tool di supporto alla
modellazione, definizione dei servizi, realizzazione
form per le attività utente, controllo del deploy,
connettori, motori di Business Process Management
BPM,
servizi
e
container
infrastrutturali
ed
ambiente di monitoraggio.
Figura 2 - Architettura di Spagic 3.0
Spagic si articola nei seguenti moduli:
Spagic Service Manager: soluzione di Universal Middleware dinamica ed adattabile, le cui
caratteristiche di modularità del modello OSGi permettono un’ampia adattabilità della soluzione in
diversi contesti, fra i quali: Enterprise Middleware, Lite Middleware, installazione dell’OSGi
container in applicativi esistenti o su sistemi specifici come il mobile o l’hardware custom.
Spagic Studio: basato su Eclipse IDE, predispone gli strumenti di progettazione, sviluppo e deploy.
Spagic Monitor: rende disponibili i servizi di management e di gestione del ciclo di vita dei singoli
moduli.
Pagina 15
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
3. Applicazione in un prodotto open source
Figura 3 a - Spagic Studio 3.0
Figura 3 b - Spagic Monitor 3.0
Pagina 16
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
3. Applicazione in un prodotto open source
Spagic Monitor rende disponibili i servizi di monitoraggio e gestione del ciclo di vita dei singoli
moduli. In particolare, tramite Spagic Monitor, è possibile fermare, mettere in pausa e fare ripartire
un servizio o processo del middleware.
Le principali funzionalità sono: monitoraggio di singoli servizi, monitoraggio per processi,
monitoraggio della piattaforma OSGi, ricerca per messaggi, ricerca per variabili o valori rilevanti,
gestione del ciclo di vita, logging.
3.4. La collocazione di questo progetto
L’attuale soluzione utilizzata dalla Spagic Console per la rappresentazione dei diagrammi di
processo e di istanze di processo è basata sull’utilizzo di immagini in formato SVG, generate da
GraphViz, un motore esterno alla suite e installato separatamente. Questo motore genera i grafi di
processo a partire dalle informazioni relative ai nodi, alla loro tipologia, e alle connessioni tra essi.
Questo motore contiene ed esegue algoritmi di autolayout dei nodi e posiziona correttamente tutti
i nodi del diagramma. Tuttavia questo motore permette una personalizzazione dell’aspetto del
diagramma molto limitata, e questo concede poco margine di miglioramento all’aspetto della
console di monitoraggio. Ad esempio ai nodi non possono essere aggiunte icone o simboli,
caratteristica particolarmente diffusa nelle console di monitoraggio di prodotti presenti nel
mercato. GraphViz, inoltre, pur essendo un prodotto Free Open Source, è rilasciato in licenza AT&T,
che impedisce l’integrazione del motore grafico nella suite di Spagic, rilasciata invece con le licenze
LGPL ed EPL. L’impossibilità di avere anche il motore di generazione dei grafi embedded in un unico
pacchetto di installazione di Spagic, costringe l’utilizzatore della Suite ad installarlo come prodotto
esterno, scaricandolo dal sito di prodotto, cosa che costituisce un disagio ulteriore, oltre a quello
della personalizzazione estetica di cui sopra.
La Console di Spagic è un’applicazione web, e perciò può essere utilizzata da un qualsiasi browser.
Un altro problema dell’attuale soluzione è relativo al supporto che i browser forniscono per il
formato SVG con cui GraphViz genera attualmente le rappresentazioni dei grafi di processo. Il
formato SVG, infatti, risulta non uniformemente supportato dai browser: mentre Mozilla Firefox lo
supporta nativamente, Internet Explorer costringe ad installare un plugin aggiuntivo.
In risposta a tali carenze e problematiche, il team di sviluppo di Spagic Monitor ha supportato la
realizzazione del progetto in oggetto a questa tesi. Chiaramente l’obiettivo è di avere un nuovo
motore di realizzazione delle immagini dei diagrammi efficace quanto quello di GraphViz, ma
realizzato come libreria Java Free Open Source in licenza compatibile LGPL od EPL, che consenta
una personalizzazione estetica più flessibile, e che generi immagini in formato nativamente
supportato dai browser più diffusi.
La libreria Java risultato del lavoro di tesi è perciò rilasciata in licenza LGPL e sarà nel prossimo
futuro integrata in Spagic, e resa quindi disponibile per la comunità scientifica.
Pagina 17
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
4. Fase di analisi
La fase di analisi è iniziata in collaborazione col team di Spagic. Innanzitutto si è considerato che il
lavoro del progetto potesse basarsi su una libreria esistente che rispettasse la maggior parte dei
requisiti richiesti, evitando di implementare tutto da zero, che sarebbe costato uno sforzo
considerevole in termini di tempo. Vista la diffusione nel mondo della comunità scientifica della
problematica del graph drawing, si è ipotizzata una certa probabilità di trovare una libreria adatta
da cui partire, da individuare attraverso un’indagine via web.
Evitare di partire da zero, oltre al vantaggio dell’efficienza nei tempi di progetto, avrebbe dato
anche un vantaggio sull’efficacia nello sfruttare l’esperienza di chi ha già affrontato problematiche
implementative del graph drawing nel realizzare una libreria.
Ovviamente il primo step per la fase di analisi è stato formalizzare le esigenze del progetto e del
team di Spagic in una lista di requisiti, da utilizzare per selezionare una libreria di partenza.
Pagina 18
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
4.1. Requisiti di progetto
Per lo sviluppo del progetto è necessario che la libreria grafica incontri il maggior numero di
requisiti tra quelli che andiamo ad elencare di seguito.
Linguaggio e sviluppo:
1. Deve essere sviluppata in Java, per consentire l’integrazione all’interno di Spagic.
2. Deve far parte di un progetto maturo, supportato e ben documentato; deve essere
rilasciata in una versione testata e stabile (non in versione alpha). Inoltre deve trattarsi di
un progetto sufficientemente valido da scongiurarne l’abbandono da parte dei developer, e
per il quale si esclude con ragionevole certezza una chiusura del codice per i rilasci futuri.
Licenza:
3. Deve essere free e open source, con una licenza compatibile con i fini dell’intero progetto
Spagic, quindi deve essere modificabile e utilizzabile a scopo commerciale. Deve avere
perciò licenza LGPL, EPL, o compatibile con queste.
Funzionalità:
4. Deve essere in grado di rappresentare grafi, più in particolare BPD, permettendo la
rappresentazione di tutte le parti che ne compongono la struttura: nodi e archi, con le
etichette testuali.
5. Nella rappresentazione dei nodi deve essere prevista anche l’informazione visuale: per i
nodi devono essere specificabili forma, dimensione, colorazione ed immagine contenuta,
mentre per gli archi è gradito che sia specificabile lo stile.
6. Deve essere possibile esportare il grafo rappresentato sottoforma di immagine
bidimensionale, in formato JPEG o PNG.
7. Deve essere implementato nella libreria un algoritmo di autolayout, che generi layout
verticali (ed eventualmente anche layout orizzontali), in grado di disporre in modo ordinato
i nodi, affinché il diagramma risulti leggibile e dall’aspetto gradevole.
8. Deve presentare le funzionalità ai punti 6 e 7, ma in passaggi distinti, in modo che
rimangano disponibili le coordinate dei vertici generate dall’algoritmo di layout
indipendentemente dall’esportazione del grafo come immagine, per poter utilizzare tali
coordinate per la creazione di mappe via CSS.
9. Non deve precludere la possibilità che l’immagine del diagramma dell’istanza di processo
venga creata dinamicamente piuttosto che essere creata una volta soltanto e poi
personalizzata attraverso l’uso di fogli di stile.
Pagina 19
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
4.2. Confronto tra librerie
Questa sezione illustra una descrizione dei risultati della ricerca di librerie grafiche, svolta allo
scopo di selezionare la libreria che incontra il maggior numero di requisiti per lo svolgimento del
progetto.
Di ogni libreria verranno perciò descritti alcuni aspetti rilevanti ai fini della valutazione della stessa.
Da questa indagine sono stati esclusi tutti i prodotti proprietari, a pagamento e/o a codice chiuso,
perché completamente avulsi dagli obiettivi del progetto. Sebbene non citati in questo documento,
tali prodotti proprietari sono stati comunque osservati nelle loro caratteristiche pubblicizzate, per
conoscenza e per trarre spunto per creare un prodotto migliore nell’ambito di questo progetto.
4.2.1. Le librerie
Di seguito andiamo ad elencare le librerie incontrate durante la ricerca e illustriamo l’eventuale
match con i requisiti di cui alla sezione precedente. Indichiamo in corsivo i requisiti per i quali non
viene trovato match e che potranno portare ad escludere la libreria in esame dall’essere candidata
all’uso nel proseguimento del progetto. In presenza di requisiti rilevanti non soddisfatti può essere
omessa l’analisi dei rimanenti requisiti. Il match con alcuni requisiti può essere omesso anche nel
caso in cui per accertarlo sia richiesta un’analisi molto approfondita della libreria, non adatta ad
una fase di panoramica sulle librerie.
GINY Graph INterface librarY – 1.1
csbi.sourceforge.net - 2005
Si propone come libreria per la rappresentazione e la visualizzazione di grafi, sviluppata ispirandosi
alle librerie e ai prodotti preesistenti col proposito di sopperire alle mancanze di questi.
Match con i requisiti:
1. Libreria Java.
2. Sufficientemente documentata, rilasciata in versione beta.
3. Licenza LGPL.
4. Consente la rappresentazione di nodi, archi, etichette.
5. Le possibilità di dettagliare la visualizzazione grafica sono da verificare.
6. Non ancora trovato un metodo che consenta esportazione del grafo come immagine.
7. Alcuni algoritmi di layout implementati, molti di essi fanno parte della libreria JUNG.
Pagina 20
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
TouchGraph GraphLayout – 1.22
touchgraph.sourceforge.net - 2002
Fornisce un insieme di interfacce per la visualizzazione di grafi, utilizzando algoritmi force-based per
il layout e tecniche di focus+context.
Match con i requisiti:
1. Libreria Java.
2. Progetto non documentato, abbandonato dagli sviluppatori.
3. Licenza Apache Software License, compatibile LGPL.
JgraphT – 0.8
www.jgrapht.org - 2008
JGraphT è una libreria di classi Java open-source, che fornisce oggetti della teoria matematica dei
grafi, e algoritmi sui grafi. È stata progettata per essere ottimizzata anche per grafi con molti nodi.
Consente di attribuire ai nodi del grafo un qualsiasi oggetto.
Match con i requisiti:
1. Libreria Java.
2. Progetto recente e ancora attivo, fornisce javadoc ma non manuali.
3. GNU Library or Lesser General Public License (LGPL).
4. 5. 6. 7. Si basa su Jgraph per la rappresentazione dei grafi e loro visualizzazione.
Jgraph – 5.12.2.1
www.jgraph.com - 2008
JGraph è una libreria Java per la rappresentazione di grafi, open-source, potente, di semplice
utilizzo, e ricca di funzionalità.
Match con i requisiti:
1. Libreria Java.
2. Progetto stabile, ben documentato. Tuttavia, si tratta di una versione “lite” di un prodotto
proprietario, il quale fornisce anche gli algoritmi di autolayout; questo affiancamento
suggerisce un ragionevole dubbio sul fatto che il codice della versione lite rimanga aperto
anche nei rilasci futuri e continui ad essere supportato dagli sviluppatori.
3. GNU Library or Lesser General Public License (LGPL).
4. In grado di rappresentare ogni parte della struttura di un grafo.
Pagina 21
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
5. È possibile inserire dentro ad ogni nodo un’immagine, è possibile scegliere lo stile degli
archi, e utilizzare etichette per nodi e archi.
6. Consente l'esportazione del grafo realizzato come immagine jpeg o png.
7. Algoritmi di autolayout del grafo sono inclusi solo nella versione a pagamento e a codice
chiuso.
GVF - The Graph Visualization Framework – 1.36
gvf.sourceforge.net - 2004
Graph Visualization Framework è un insieme di due package Java che possono essere utilizzati
come fondamento per applicazioni che manipolano o visualizzano strutture a grafo. “Royere” è
costruito su GVF è include supporto XML, output SVG, layout, e l’editing dei grafi.
Match con i requisiti:
1. Libreria Java.
2. Progetto stabile e ben documentato.
3. GNU General Public License (GPL), incompatibile LGPL
JUNG Java Universal Network/Graph – 2.0
jung.sourceforge.net - 2009
JUNG è una libreria per la modellazione, l’analisi, e la visualizzazione di dati che possono essere
rappresentati come grafi o reti.
È progettata per supportare un’ampia varietà di rappresentazioni di entità e loro relazioni, come
grafi orientati e semplici, con archi paralleli, o grafi iperbolici. Consente il collegamento dei nodi a
metadati, e fornisce algoritmi di teoria dei grafi, analisi statistiche, e altre misure importanti.
Fornisce alcuni algoritmi di layout e consente di crearne di aggiuntivi.
Match con i requisiti:
1. Libreria Java.
2. Progetto stabile e ancora attivo, ma documentato in modo incompleto.
3. BSD License, compatibile LGPL.
4. In grado di rappresentare nodi e archi di un grafo.
5. Consente l’uso di immagini come shape dei nodi, l’aspetto estetico della visualizzazione di
archi rimane da verificare.
6. Contiene un metodo rudimentale per l’esportazione del grafo come immagine.
Pagina 22
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
7. È fornito di alcuni algoritmi di layout, tra i quali però non vi è il layout gerarchico tipico dei
diagrammi workflow in BPMN.
HyperGraph – 0.6.3
hypergraph.sourceforge.net - 2005
HyperGraph è un progetto open source che fornisce codice java per lavorare con la geometria
iperbolica e specialmente con alberi iperbolici, per la visualizzazione e il layout di questi.
Match con i requisiti:
1. Libreria Java.
2. Abbastanza documentato e stabile.
3. GNU Library or Lesser General Public License (LGPL).
4. In grado di rappresentare nodi e archi di un grafo.
5. Incentrato sulla visualizzazione di grafi che rappresentano reti, non offre la possibilità di
rappresentare i nodi con immagini.
JDigraph – 0.9
jdigraph.dev.java.net - 2005
JDigraph è una libreria per rappresentare e lavorare con i grafi orientati e con i cammini.
Match con i requisiti:
1. Libreria Java.
2. Progetto poco documentato, in versione alpha.
3. Berkeley Software Distribution (BSD) License.
4. Consente la rappresentazione di nodi e archi.
5. Si appoggia a Graphviz per il rendering degli aspetti estetici, e perciò risulta insufficiente.
VRLM Graph – 1.0
vrmlgraph.i-scream.org.uk - 2001
Virtual Reality Modeling Language graph è un package Java completo di codice sorgente per creare
rappresentazioni di grafi in 3 dimensioni.
Match con i requisiti:
1. Libreria Java.
2. Dotato solo di Javadoc.
Pagina 23
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
3. GNU Library or Lesser General Public License (LGPL).
4. Consente di rappresentare nodi e archi.
5. Incentrato sul rendering 3d in formato VRML, non consente l’utilizzo degli aspetti estetici
tipici di un diagramma in BPMN.
graphopt graph layout optimizer – 0.4.1
www.schmuhl.org/graphopt - 2003
Nasce per sopperire alle lacune delle librerie disponibili per l’ottimizzazione del layout dei grafi,
attraverso l’uso di algoritmi basati sulla fisica.
Match con i requisiti:
1. Libreria C++.
2. Poco documentato
3. GNU General Public License (GPL), incompatibile LGPL.
JGraphEd – 1.21
www.jharris.ca/JGraphEd/ - 2004
Si tratta di una libreria Java per l’editing di grafi. È pensata per consentire all’utente di creare
facilmente grafi dalla GUI, e comprende un insieme di algoritmi per la gestione dei grafi.
Match con i requisiti:
1. Libreria Java.
2. Ben documentata.
3. Licenza personale dell’autore non compatibile con progetti a scopo commerciale.
VGJ Visualizing Graphs with Java – 1.03
www.eng.auburn.edu/csse/research/graph_drawing/manual/vgj_manual.html - 2002
Visualizing Graphs with Java (VGJ) è uno strumento per la rappresentazione e il layout dei grafi. Il
grafo può essere dato in input come una descrizione testuale in formato GML (graph modeling
language) oppure disegnato utilizzando l’editor. Fornisce tre algoritmi di layout per disporre il grafo
in modo organizzato.
Match con i requisiti:
1. Libreria Java.
2. Sufficientemente documentato.
Pagina 24
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
3. GNU General Public License, Version 2, incompatibile LGPL.
GUESS Graph Exploration System – 1.0.3
www.graphexploration.org - 2007
GUESS Graph Exploration System, è un sistema per la visualizzazione e la manipolazione di strutture
a grafo e per la creazione di nuove applicazioni di visualizzazione. Fa uso di JUNG al suo interno.
Match con i requisiti:
1. Libreria Java con utilizzo di una estensione di Python.
2. beta release, supportato e documentato.
3. GNU General Public License (GPL), incompatibile LGPL.
The prefuse visualization toolkit – 20071021
prefuse.org - 2007
Strumento software per la costruzione di applicazioni per la visualizzazione di informazioni. Prefuse
supporta un ricco set di caratteristiche per il data modelling, la visualizzazione, l’animazione e
l’interazione, sia per Java che per Flash (prefuse flare). Fornisce strutture dati ottimizzate per grafi
e alberi, molte tecniche di layout e visualizzazione. È scritto in Java, utilizzando la libreria grafica
Java 2D e si integra facilmente in applicazioni Java Swing o web applets.
Match con i requisiti:
1. Libreria Java.
2. beta release, progetto recente, documentazione molto incompleta.
3. BSD license, consente scopi commerciali.
4. Attraverso la galleria degli esempi si nota come sia in grado di rappresentare tutte le parti
dei diagrammi: nodi, archi, etichette.
5. 6. 7. A causa della scarsa documentazione, resta da verificare il match con le altre
funzionalità richieste.
Zest: The Eclipse Visualization Toolkit – 3.5.0
www.eclipse.org/gef/zest/ - 2009
Zest è un insieme di componenti di visualizzazione per Eclipse. L’intera libreria è stata sviluppata in
SWT / Draw2D. Il progetto Zest contiene un package di layout per i grafi.
Questa libreria è utilizzabile anche indipendentemente da Eclipse.
Pagina 25
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
È stata realizzata in un progetto la funzionalità che lega il linguaggio DOT di Graphviz con Zest, sia
DOT to Zest, che consente di rappresentare in Zest un grafo descritto in linguaggio DOT, sia Zest to
DOT, che consente di tradurre in linguaggio DOT per Graphviz un grafo rappresentato con oggetti
delle classi di Zest.
Per i nostri scopi risulta vantaggiosa la possibilità di passare a Zest un grafo descritto in linguaggio
DOT, perché questa libreria lo rappresenti attraverso oggetti e lo visualizzi con caratteristiche
estetiche di cui è fornita. Tuttavia i creatori di questo progetto prevedono il passaggio da Zest a
linguaggio DOT e poi l’uso di Graphviz per l’esportazione del grafo come immagine, mentre
l’esportazione diretta da Zest è una milestone ancora da completare.
Esiste inoltre un progetto basato su Zest che consente l’input di un grafo in formato GraphML.
GraphML è un formato XML-based che consente di descrivere le principali caratteristiche di un
grafo. Non è prevista da questo formato la dichiarazione delle coordinate di un nodo e del
posizionamento degli archi, perciò per includere questa informazione nel file graphml si dovrebbe
definire un nuovo tag; questo perché il layout del grafo è comunemente espresso nei fogli di stile
XSL, usati per la trasformazione XSLT del file graphml per esempio in un file SVG che presenti anche
le coordinate per i nodi (file XSL che realizzino una presentazione del grafo con assegnamento
automatico delle coordinate sono difficilmente reperibili).
Tuttavia, questo progetto non aggiunge a Zest nulla quanto ad algoritmi di autolayout e funzionalità
di visualizzazione: il suo uso prevede l’importazione di un grafo in formato graphml e quindi l’uso
degli algoritmi forniti da Zest.
Match con i requisiti:
1. Libreria Java, utilizzabile anche indipendentemente da Eclipse.
2. Progetto stabile ma scarsamente documentato. Essendo un plugin di Eclipse open, con
un’ampia community che lo utilizza, è ragionevole supporre che in futuro il codice rimanga
open; essendo un plugin apprezzato dalla comunità di utenti di Eclipse si può prevedere
che non verrà abbandonato dai developer, i quali sono attualmente alla ricerca di
miglioramenti per questo plugin.
3. Eclipse Public License (EPL).
4. In grado di rappresentare ogni parte della struttura di un grafo.
5. È possibile inserire dentro ad ogni nodo un’immagine, è possibile scegliere lo stile degli
archi, e utilizzare etichette per nodi e archi.
6. Consente la visualizzazione del grafo su finestra; la possibilità di esportare come immagine
potrebbe basarsi esclusivamente sulla realizzazione di uno screenshot di tale finestra;
l’analisi di questa possibilità si svolgerà nel seguito di questo documento.
Pagina 26
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
7. Algoritmi di autolayout del grafo sono inclusi, ma non consentono di realizzare il layout
gerarchico di un diagramma workflow.
8. Le coordinate calcolate da qualsiasi algoritmo di layout della libreria vanno a settare dei
campi dati dell’oggetto che rappresenta il nodo del grafo e sono accedibili da metodi di get.
9. La generazione dinamica del diagramma è una possibilità che non viene preclusa dall’uso di
questa libreria.
4.2.2. Librerie selezionate
Nella fase di ricerca delle librerie che più si avvicinano ai requisiti stabiliti, è stato rilevato che i
prodotti esistenti con caratteristiche perfettamente aderenti allo scopo del progetto sono prodotti
proprietari, con codice chiuso, e licenza a pagamento, che in questo documento non vengono citati
perché la loro licenza li rende completamente discordanti con lo scopo della ricerca e del progetto
stesso.
D’altra parte, anche molti dei prodotti sviluppati in ambito accademico e scientifico non incontrano
i requisiti a causa della licenza, perché rilasciati in licenza GPL, che forza il prodotto a restare aperto
e non prevedere scopi commerciali.
Le librerie selezionate sono comunque general purpose, e consentono la rappresentazione di grafi,
e non sono ad hoc per la rappresentazione di diagrammi workflow in BPMN.
Le librerie che maggiormente si avvicinano agli scopi del progetto sono:
GINY Graph INterface librarY – 1.1
di cui restano da accertare le funzionalità per i dettagli estetici dei grafi e a cui mancano gli
algoritmi di layout per diagrammi workflow;
JUNG Java Universal Network/Graph – 2.0
di cui è da valutare la possibilità d’uso vista la carenza di documentazione e a cui mancano gli
algoritmi di layout per diagrammi workflow;
Jgraph – 5.12.2.1
a cui mancano gli algoritmi di layout, e di cui non costituisce fattore di preferenza il fatto che si
tratti di un prodotto “lite” affiancato ad una versione “pro” a codice chiuso in un’ottica di rilasci
futuri a codice aperto;
Zest: The Eclipse Visualization Toolkit – 3.5.0
di cui va approfondita la funzionalità di esportazione dell’immagine e a cui mancano gli algoritmi di
layout per diagrammi workflow.
Pagina 27
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
4.2.3. La scelta
Trattandosi in ogni caso di librerie prive di algoritmi di autolayout per diagrammi workflow, la scelta
si è basata su altre caratteristiche. In particolare, si è considerato fondamentale il futuro dello
sviluppo della libreria da parte dei suoi developer: si è considerato necessario che il progetto
rimanga free e open source, manutenuto dai developer, e utilizzato dalla comunità, in modo che il
progetto per il quale la libreria viene usata possa evolvere anche attraverso gli aggiornamenti e i
miglioramenti di questa libreria.
La libreria che più avvicina questo principio è “Zest: The Eclipse Visualization Toolkit”, e visto che
presenta carenze equivalenti rispetto alle altre librerie osservate, ci apprestiamo ad effettuarne
uno studio più approfondito, al fine di controllare il funzionamento dell’esportazione
dell’immagine, appurare la possibilità di inserirvi un nuovo algoritmo di layout adatto ai diagrammi
workflow BPD, nonché a delineare la rappresentazione e l’uso delle strutture dati appartenenti al
grafo con cui sopperire alla totale mancanza di documentazione.
Figura 4 - Screenshot di Zest
Pagina 28
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
4.3. Uso della libreria Zest
In questa sezione verrà descritto l’approfondimento sulla libreria grafica scelta in seguito alla fase
di ricerca e valutazione, ovvero la libreria “Zest: The Eclipse Visualization Toolkit”, che costituisce
un plugin per Eclipse per la visualizzazione e manipolazione dei grafi all’interno dell’IDE di sviluppo.
In particolare verrà svolto uno studio più approfondito sulle funzionalità di Zest indispensabili alla
realizzazione del progetto: verrà studiata la possibilità di esportare l’immagine, la possibilità di
costruirvi sopra un nuovo algoritmo di layout gerarchico, adatto ai diagrammi workflow, e verranno
delineati la rappresentazione e l’uso delle strutture dati appartenenti al grafo per sopperire alla
mancanza di documentazione.
Da questo punto del percorso del nostro progetto comincia ad essere indispensabile l’utilizzo dello
strumento Eclipse come IDE di sviluppo, dove importare i jar della libreria di Zest e delle sottostanti
SWT e draw2d, includendo anche il codice sorgente, e tutti gli snippet disponibili, che costituiscono
un ottimo modo per essere iniziati all’uso di una libreria.
In particolare è stato utile uno strumento aggiuntivo, AmaterasUML, un plugin di Eclipse free e
open source che consente di disegnare diagrammi delle classi in notazione UML in Eclipse, ma
anche di ottenere automaticamente il class diagram di classi esistenti attraverso il solo
trascinamento dei file .java sulla finestra del plugin.
4.3.1. Struttura delle classi
Package org.eclipse.zest.core.widgets
La classe al centro di questa libreria è la classe Graph, che, ovviamente rappresenta l’intero grafo.
Un oggetto Graph contiene una lista di nodi e una lista di connessioni, rispettivamente di tipo
GraphNode e GraphConnection. Contiene inoltre un campo dati di tipo LayoutAlgorithm. La classe
Graph presenta tutti i metodi di get and set necessari, e in particolare presenta il metodo
getNodes() con cui è possibile avere accesso ai nodi per ottenere le coordinate a cui sono stati
posizionati dall’algoritmo. Al costruttore di un oggetto Graph va passato un oggetto di tipo
org.eclipse.swt.widgets.Shell, su cui il grafo viene tracciato.
La classe GraphNode rappresenta i nodi del grafo. Contiene le informazioni sull’aspetto del nodo,
quali: colore di primo piano, colore in secondo piano, colore e spessore del bordo, colore di
evidenziazione, dimensione, font per l’etichetta, visibilità, ecc. Testo dell’etichetta e immagine per
il nodo sono registrate presso l’oggetto Item, poiché GraphNode è l’ultima classe di una gerarchia
che eredita dalle classi della libreria grafica swt (Widget, Item, GraphItem, GraphNode).
Ogni nodo GraphNode contiene una lista di connessioni GraphConnection di cui è destinazione, e
una lista di connessioni di cui è sorgente.
Pagina 29
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
Alla creazione del nodo, il costruttore richiede come primo parametro il grafo per il quale lo si crea;
tale informazione verrà salvata in un campo dati dell’oggetto, e verrà richiamato un metodo del
grafo per l’aggiunta del nodo creato nella lista dei nodi.
L’informazione relativa al posizionamento del nodo nel grafo è mantenuta nel campo dati
currentPosition di tipo org.eclipse.draw2d.geometry.Point.
Il campo dati di tipo layoutEntity è la parte di questo oggetto che viene interessata dall’algoritmo di
layout. org.eclipse.zest.layouts.LayoutEntity è in realtà un interfaccia, e tale campo dati sarà
inizializzato con un oggetto LayoutGraphNode, classe che implementa LayoutEntity. Vedremo in
seguito più chiaramente i dettagli dell’uso degli algoritmi di layout.
La classe GraphConnection rappresenta gli archi del grafo. In modo abbastanza coerente con la
struttura della classe GraphNode, essa contiene le informazioni sull’aspetto della connessione,
quali: colore, stile, spessore, curvatura, evidenziazione, visibilità , ecc. Ha un campo dati di tipo
org.eclipse.draw2d.Label per l’etichetta. Ogni connessione GraphConnection ha un riferimento al
GraphNode sorgente e a quello destinazione, e, come per i nodi, mantiene un riferimento anche al
grafo per il quale è stata creata, richiesto dal costruttore, che invocherà un metodo per registrare la
connessione creata sia nella lista delle connessioni entranti del nodo destinazione, sia nella lista
delle connessioni uscenti del nodo sorgente, sia nella lista di connessioni del grafo.
Come GraphNode, ha un campo dati di tipo org.eclipse.zest.layouts.LayoutRelationship
(interfaccia), che verrà inizializzato con un oggetto GraphLayoutConnection, oggetto utilizzato dagli
algoritmi di layout.
Figura 5 - Principali campi dati e metodi delle classi di org.eclipse.zest.core.widgets
Pagina 30
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
Package org.eclipse.zest.layouts
Per applicare un layout è necessario invocare sull’oggetto Graph il metodo setLayoutAlgorithm(…)
che prende come parametro un oggetto di tipo LayoutAlgorithm, e un boolean che se true indica
che il layout va applicato, altrimenti che il layout è stato solo settato ma l’effettiva applicazione è
rimandata. Questo metodo setta il campo dati di Graph, e se il boolean è true invoca applyLayout().
Quest’ultimo effettua un controllo sulla visibilità della finestra del grafo, e solo nel caso in cui essa
sia visualizzata, invoca l’esecuzione asincrona del metodo applyLayoutInternal(). Quest’ultimo
effettua alcuni controlli e impostazioni, quindi va a recuperare dal grafo i nodi e le connessioni di
cui fare il layout: prende dai nodi il loro campo LayoutEntity, e dalle connessioni il loro campo
LayoutRelationship, ed è qui che si nota come questi campi dati siano l’ “interfaccia” delle strutture
GraphNode e GraphConnection verso il layouting. Dopo aver popolato un array di LayoutEntity e
uno di LayoutRelationship (controllando per ogni connessione che esistano i nodi sorgente e
destinazione), invoca sul campo dati layoutAlgorithm il metodo che avvierà l’algoritmo:
applyLayout(LayoutEntity*+ entitiesToLayout, LayoutRelationship*+ relationshipsToConsider, …).
In cima alla gerarchia di classi per il layout troviamo l'interfaccia LayoutAlgorithm, che impone di
implementare il metodo applyLayout(…). Ad implementare questa interfaccia troviamo la classe
astratta AbstractLayoutAlgorithm; questa implementa applyLayout(...), invocando al suo interno il
metodo setupLayout(...), che crea un InternalNode per ogni LayoutEntity, e un InternalRelationship
per ogni LayoutRelationship.
Gli algoritmi di layout, infatti, operano su una struttura nodo e una struttura connessione “interne”,
appositamente create per il layout: InternalNode e InternalRelationship. InternalNode contiene
molti campi dati per memorizzare le coordinate del nodo in più momenti, mentre
InternalRelationship contiene l’informazione sui punti di curvatura dell’arco.
Ogni InternalNode ha un campo dati entity di tipo LayoutEntity, così come ogni InternalRelationship
ha un campo dati externalRelationship di tipo LayoutRelationship, con cui viene mantenuto un
collegamento con i nodi “esterni” e con le connessioni “esterne” (ovvero con le strutture dati di cui
alla sezione precedente), e che permetteranno alla fine del calcolo di rendere visibili le coordinate
calcolate a livello esterno.
Creati da setupLayout(…) un array di InternalNodes e uno di InternalRelationship, si hanno pronte le
strutture dati su cui far lavorare il calcolo, con cui vengono settati i campi dati internalNodes e
internalRelationships
dell’oggetto
algoritmo,
quindi
viene
invocato
il
metodo
applyLayoutInternal(InternalNodes*+ nodes, InternalRelationship*+ relationships, …).
Ogni sottoclasse di AbstractLayoutAlgorithm deve implementare applyLayoutInternal(…), metodo
in cui è svolto il calcolo effettivo delle coordinate.
Pagina 31
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
4. Fase di analisi
Le coordinate calcolate, come già accennato, vengono memorizzate nei campi dati double degli
internalNodes, ma alla fine del calcolo è necessario che con tali coordinate venga settata la
currentLocation
del
GraphNode.
AbstractLayoutAlgorithm
deve
Per
fare
invocare
questo,
dentro
ogni
classe
che
applyLayoutInternal(…)
implementa
il
metodo
updateLayoutLocations(InternalNode[] nodes), che, attraverso alcune invocazioni di metodi, si
occupa
di
settare
la
currentLocation
del
GraphNode.
In
alternativa
all’uso
di
updateLayoutLocations(…) è possibile andare ad invocare direttamente sulle entity il metodo
setLocationInLayout( double x, double y ) con cui andrà settata la currentPosition del GraphNode
esterno corrispondente.
I layout disponibili
Osservando il package org.eclipse.zest.layouts.algorithm, si è posta una particolare attenzione agli
algoritmi di layout implementati.
Nel sito web di progetto si trovano dichiarati i seguenti algoritmi di layout: Spring Layout Algorithm,
Tree Layout Algorithm, Radial Layout Algorithm, Grid Layout Algorithm, mentre nel package, oltre a
questi appena citati, si trova anche implementato DirectedGraphLayoutAlgorithm. Leggendo i
commenti al codice sorgente e osservando il codice stesso, sembrava trattarsi di
un’implementazione di un algoritmo gerarchico. Questo ha introdotto nel progetto una fase non
prevista: il test di questo algoritmo per verificare se fosse adatto agli scopi di questo progetto.
Tuttavia, i test, eseguiti anche dal team di Spagic, hanno rilevato le pessime performance
dell’algoritmo in termini di efficacia, e questa fase di test si è conclusa molto velocemente e senza
alcuna variazione al proseguimento del progetto.
4.3.2. Aspetto dei nodi
Un’osservazione più approfondita della libreria ha rivelato che le possibilità di personalizzare
l’aspetto dei nodi utilizzando i classici GraphNode sono limitate. In particolare, la struttura delle
classi nodo non mette a disposizione immediatamente la possibilità di scegliere una forma
particolare per il nodo. La shape di ogni nodo è un rounded rectangle e non c’è modo di creare un
GraphNode specificando una shape diversa (ad esempio un cerchio o un poligono). GraphNode
consente solamente di specificare un’immagine da inserire all’interno del rounded rectangle,
accanto all’etichetta.
Molti bug sono stati aperti a causa di questa grave carenza, e per il loro fixing è stata creata la
classe CGraphNode. Questa è una sottoclasse di GraphNode, dotata di un costruttore a cui passare
una org.eclipse.draw2d.IFigure che verrà utilizzata per il nodo. Tuttavia l’utilizzo di un CGraphNode
non consente di specificare da costruttore una stringa da apporre sul nodo, e sarà competenza del
metodo che costruisce la figura apporvi una label.
Pagina 32
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
5. Fase di progettazione
Come già anticipato, la libreria Zest, su cui si appoggia l’intero progetto, manca di alcune
funzionalità che andavano quindi progettate, implementate e testate. Citiamo in questa sezione la
progettazione della funzionalità di autolayout, che è stata implementata utilizzando le classi di Zest
per la rappresentazione dei grafi, dei nodi e delle connessioni. Alla sezione successiva verranno
citati alcuni dettagli relativi alle altre funzionalità, di cui è più interessante vedere il lato
implementativo.
La progettazione dell’algoritmo di autolayout ha visto innanzitutto la scelta di una possibile
implementazione dell’algoritmo di Sugiyama, tra le tante realizzate. La scelta di una
implementazione doveva essere guidata da motivazioni sull’efficacia e sull’efficienza della stessa,
perciò, qualunque testo o articolo si fosse seguito per implementare, sarebbe stato essenziale
avere in anticipo una certa “garanzia” di affidabilità dell’implementazione, e di aderenza agli scopi
di questo progetto. Difficilmente si trovano articoli che descrivano una implementazione
dell’algoritmo di Sugiyama che siano anche accompagnati da codice sorgente che un utilizzatore
possa testare per verificarne i risultati sui grafi del proprio progetto.
Una soluzione a questo problema era costituita dallo stesso GraphViz.
Il sito di progetto di GraphViz mette a disposizione un articolo che descrive lo pseudocodice seguito
per implementare l’algoritmo gerarchico per grafi orientati, e contemporaneamente mette a
disposizione lo strumento di GraphViz stesso, con cui se ne può testare l’esecuzione sui propri grafi
di test. In particolare nel caso di questo progetto abbiamo già i grafi di test generati da GraphViz:
sono i grafi attualmente in uso nella Console. Inoltre è a disposizione lo strumento di Gvedit per
editare nuovi grafi in linguaggio dot e ottenerne la visualizzazione attraverso il motore dot di
GraphViz.
I difetti estetici di tali grafi sono quelli discussi nella sezione 3.4, tuttavia il layout gerarchico di
GraphViz è corretto e gradevole, e perciò è stato concordato con il team di Spagic che questo fosse
l’algoritmo di appoggio per la nostra implementazione.
Nei prossimi paragrafi di questa sezione descriviamo la progettazione del nostro algoritmo, basata
sull’algoritmo gerarchico di GraphViz.
L’intero algoritmo è stato sviluppato all’interno di una nuova classe java SugiyamaLayoutAlgorithm,
provvista di metodi per ognuno dei passi dell’algoritmo, e facente uso di nuove classi per un più
agevole accesso alla struttura del grafo, come ad esempio la classe Rank.
Pagina 33
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
5.1. L’algoritmo gerarchico per grafi orientati
In questa sezione illustriamo la progettazione dei passi dell’algoritmo di layout che è stato
successivamente implementato in Java. La teoria di questo algoritmo si basa fondamentalmente
sulla letteratura esistente sugli algoritmi gerarchici, e in particolare sull’algoritmo con cui opera il
motore di GraphViz.
Per tracciare il digrafo è d’aiuto supporre che abbia una determinata direzione globale del flusso,
per esempio dall’alto verso il basso. Sulla base di questo presupposto, sono stati formulati molti
metodi per tracciare digrafi, basati sui seguenti criteri estetici:
1. Mostrare la struttura gerarchica del grafo, cercando di dirigere gli archi nella stessa direzione
generale, evidenziando così i nodi sorgente e i nodi destinazione.
2. Evitare anomalie nella visualizzazione che non favoriscono la comprensione del grafo, come ad
esempio l’incrocio di archi.
3. Miminizzare la lunghezza degli archi, in modo che i nodi correlati siano facilmente identificabili.
4. Favorire la simmetria e il bilanciamento.
Non c’è modo di ottimizzare simultaneamente secondo tutti questi criteri.
Perciò faremo alcune supposizioni di semplificazione, e considereremo delle euristiche che
eseguono rapidamente producendo dei buoni risultati nei casi comuni. Per un’indagine su altri
principi estetici, consigliamo di consultare gli algoritmi di graph-drawing di Eades e Tamassia. Il
layout del grafo sarà guidato dai criteri che abbiamo menzionato, e segue l’approccio di Warfield e
Sugiyama.
G=(V,E)
V = { 1, 2, 3, 4, 5, 6, 7, 8 , 9, 10, 11}
E = { (1,2) , (2,3) , (3,2) ,
(3,4) , (3,5) , (3,6) ,
(4,7) , (5,8) , (6,9) ,
(7,10) , (8,10) , (9,10) ,
(10,11) , (11,1) }
x
Sugiyama
Automatic
Layout
Algorithm
y
Figura 6 - Input e output dell'algoritmo
L’input dell’algoritmo è un grafo G = ( V, E ), che deve essere non vuoto, connesso, privo di nodi
isolati, privo di cappi e archi multipli e può contenere cicli. Le caratteristiche che abbiamo appena
elencato sono proprie dei grafi di processo che andiamo a rappresentare, perciò non costituiscono
un limite. L’algoritmo assegna ad ogni nodo le coordinate x e y, che si riferiscono al vertice in alto a
sinistra dell’immagine del nodo, e assegna ad ogni arco una serie di punti di curvatura attraverso i
quali deve essere condotto, calcolati in modo che l’arco non attraversi dei nodi.
Pagina 34
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
Panoramica
L’algoritmo di graph drawing si compone di quattro passi principali ed altri passi che costituiscono
operazioni di supporto, che illustriamo di seguito.
L’intera esecuzione dell’algoritmo è sottoposta alla condizione di validità del grafo: come già
anticipato, deve essere non vuoto, connesso, privo di nodi isolati, privo di cappi e archi multipli. Se
tali condizioni sono rispettate, vengono eseguiti i seguenti passi:
Il primo passo rende aciclico il grafo, in modo temporaneo, per l’esecuzione dell’algoritmo.
Il secondo passo dispone i nodi in rank, ovvero in livelli verticali.
Il terzo passo è di preparazione per quelli successivi: crea infatti delle catene di nodi dummy
con cui sostituire gli archi di lunghezza non unitaria, allo scopo di condurre opportunamente gli
archi attraverso i rank, senza sovrapposizione con i nodi. In corrispondenza a questo passo si
trova in seguito nell’algoritmo un altro passo che ripristina gli archi originali.
Il quarto passo determina l’ordine dei nodi all’interno di ogni rank, in modo che vengano evitati
gli incroci di archi.
Il quinto passo individua la corretta posizione del nodo nella disposizione orizzontale del rank;
questo passaggio diverge dalle scelte progettuali e implementative di GraphViz ed è stato
ideato ad hoc.
Il sesto passo individua le coordinate da assegnare ai nodi; anche questo passaggio diverge
dalle scelte progettuali e implementative di GraphViz ed è stato ideato ad hoc.
1. public boolean run() {
2.
if( validGraph()) {
3.
breakCycles();
4.
rank();
5.
createVirtualStructures();
6.
order();
7.
position();
8.
assignCoordinates();
9.
hideVirtualStructures();
10.
return true;
11.
}
12. }
Figura 7 - L'algoritmo principale
Nelle prossime sezioni illustreremo i passi più nel dettaglio. In particolare descriveremo un modo
efficiente per effettuare il ranking dei nodi usando l’algoritmo del simplesso su reti, e una buona
euristica per ridurre gli incroci tra archi.
Pagina 35
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
5.2. Validità del grafo
Il controllo di validità del grafo prevede il controllo dei singoli casi di non validità.
Citiamo in questa sezione solamente il controllo relativo al fatto che il grafo sia connesso, mentre
gli altri controlli sono semplici e facilmente implementabili grazie alle strutture messe a
disposizione da Graph, GraphNode e GraphConnection di Zest.
Per controllare che il grafo sia connesso abbiamo utilizzato una ricerca in profondità, allo scopo di
verificare se con una sola invocazione della ricerca da un nodo qualsiasi del grafo venissero visitati
tanti nodi quanta è la cardinalità di V.
5.3. Rimozione dei cicli
Per poter avere un’assegnazione dei rank consistente, il grafo deve essere privo di cicli. Siccome il
grafo in input può contenere cicli, un passo di preprocessing deve individuarli e romperli attraverso
l’inversione di alcuni archi.
Ovviamente tali archi sono invertiti sono internamente, le frecce nel disegno finale manterranno la
medesima direzione assegnata inizialmente alla creazione del grafo.
Una procedura utile per rompere i cicli è bastata sulla ricerca in profondità. Gli archi vengono
percorsi nell’ordine naturale del grafo in input, partendo da un nodo sorgente o destinazione.
1. breakCycles() {
2.
setAllWhite();
3.
dfsFindCycles(node);
4.
reverseFeedbackArcs();
5. }
Figura 8 - Progettazione di breakCycles
La ricerca in profondità viene svolta con la ben nota tecnica della colorazione dei nodi: ogni nodo
inizialmente è bianco, poi viene colorato di grigio appena viene visitato, e infine viene colorato di
nero quando terminano le chiamate ricorsive sui suoi discendenti. Quando, osservando i
discendenti di un nodo, si incontra un nodo grigio, l’arco appena percorso è di feedback. Tutti gli
archi di feedback rilevati vengono salvati in una lista, e verranno infine invertiti logicamente,
scambiando sorgente e destinazione. Ovviamente a questo passaggio di inversione deve
corrispondere un passaggio di ripristino da utilizzare al termine dell’algoritmo.
È da notare che l’inversione di un arco può provocare la creazione di un arco multiplo, nel caso in
cui già esistesse un arco opposto tra gli stessi due nodi. In quel caso è necessaria la temporanea
rimozione dell’arco di feedback.
Pagina 36
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
breakcycle
rank
Figura 9 - Esempio
dell'effetto di breakcycle su un
grafo con due archi di
feedback
Vediamo brevemente la teoria che sta dietro a questo uso della ricerca in profondità.
La ricerca in profondità ha l’effetto di partizionare gli archi in due insiemi: archi d’albero e archi non
d’albero. L’albero definisce un ordine parziale sui nodi. Dato questo ordine parziale, gli archi non
d’albero possono essere ulteriormente partizionati in tre insiemi: cross, forward, back. Il primo
insieme contiene gli archi che connettono nodi non correlati nell’ordine parziale. Il secondo
contiene gli archi che connettono un nodo con un discendente. Il terzo insieme contiene gli archi
che connettono un discendente con uno dei suoi antenati. Risulta chiaro che aggiungere archi di
tipo forward o cross all’ordine parziale non crea cicli, mentre gli archi di tipo back sono quelli che
determinano i cicli. Siccome l’inversione degli archi di tipo back li rende archi di tipo forward, tutti i
cicli vengono spezzati attraverso questa procedura.
Ovviamente è ragionevole invertire un insieme di archi minimo, il più piccolo possibile. Una
difficoltà sta nel fatto che trovare l’insieme minino nel problema dell’ “insieme di archi di feedback”
è un problema NP-completo. E, fatto più importante, determinare esattamente l’insieme minimo
probabilmente non migliorerebbe il disegno del grafo.
Esperimenti hanno dimostrato come molti grafi orientati che provengono da applicazioni pratiche
abbiano una naturale direzione degli archi anche quando contengono dei cicli. L’input del grafo
normalmente riflette questa direzione naturale. Invertire l’arco sbagliato può compromettere il
disegno del grafo. Ad esempio, anche se il grafo di una invocazione ad una procedura ha dei cicli, ci
si aspetta di trovare le funzioni top-level nella parte alta del grafo, non in altri punti.
Dal punto di vista della stabilità, l’euristica della ricerca in profondità per la rottura dei cicli sembra
preferibile. Ottiene disegni di grafi più informativi di quelli che si ottengono con altre euristiche
come quella che suggerisce di collassare in un singolo nodo tutti i nodi che fanno parte di un ciclo,
oppure quella che posiziona tutti i nodi del ciclo sullo stesso rank, oppure quella che duplica uno
dei nodi del ciclo, come suggeriscono vari ricercatori come Carpano, Robbins e Sugiyama.
Pagina 37
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
5.4. Assegnazione del rank
Questo passo dell’algoritmo assegna ad ogni nodo v V del grafo G = ( V, E ), un valore intero (v),
consistente con gli archi relativi al nodo v: per ogni arco e = ( v, w ), appartenente ad E, l(e) >= (e)
dove la lunghezza l(e) di un arco e = ( v, w ) è definita come l(w) - l(v), e (e) rappresenta una soglia
di lunghezza minima. (e) di norma è 1 ma può eventualmente assumere anche un altro valore
intero positivo.
rank
0
1
2
createVirtualStructures
3
4
5
6
Figura 10 - Esempio dell'effetto di rank
Definizione del problema
Secondo uno dei principi estetici che abbiamo citato, gli archi devono essere corti. Oltre al fatto di
creare layout migliori, gli archi corti riducono il tempo d’esecuzione dei passi successivi il cui tempo
dipende dalla lunghezza totale degli archi. Perciò è desiderabile trovare un ranking ottimale dei
nodi, cioè uno per cui la lunghezza totale degli archi pesati sia minima.
Trovare un ranking ottimo può essere formulato come il seguente problema di programmazione
intera:
La funzione peso
e la funzione di lunghezza minima
mappano l’insieme degli archi E
rispettivamente in numeri razionali non negativi e interi non negativi.
Ci sono vari metodi per risolvere questo problema di programmazione intera in tempo polinomiale.
Un metodo consiste nel risolvere l’equivalente problema di programmazione lineare, e poi
trasformare la soluzione in una intera in tempo polinomiale.
Pagina 38
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
Un altro metodo consiste nel convertire il problema dell’assegnazione ottima dei rank
nell’equivalente problema di flusso di costo minimo, per il quale esistono algoritmi di complessità
polinomiale in tempo. Siccome la matrice dei vincoli è totalmente unimodulare, il problema può
anche essere risolto col metodo del simplesso, benchè non necessariamente in tempo polinomiale.
Simplesso su reti
Descriviamo ora un semplice approccio al problema, basato sulla formulazione del simplesso su
reti. Nonostante non sia stato provato che la sua complessità in tempo sia polinomiale, nella pratica
impiega poche iterazioni ed esegue rapidamente.
Iniziamo con alcune definizioni ed osservazioni.
Un ranking è detto feasible (fattibile) quando soddisfa i vincoli sulla lunghezza l(e) ≥ (e) per ogni
arco e. Dato un ranking, non necessariamente feasible, definiamo lo slack di un arco come la
differenza tra la sua lunghezza e la sua lunghezza minima. Perciò un ranking è feasible se per ogni
arco lo slack è non negativo. Un arco si dice tight (stretto) se lo slack è zero.
Un albero di copertura di un grafo induce un ranking, o una famiglia di ranking equivalenti. L’albero
di copertura si individua sul grafo non direzionato e privo di radice.
Questo ranking è generato scegliendo un nodo iniziale e assegnandogli un rank. Poi, per ogni nodo
adiacente nell’albero di copertura, gli si assegna un rank incrementato o decrementato della
minima lunghezza dell’arco che li connette, a seconda che il nodo sia la testa o la coda dell’arco.
Questo procedimento viene iterato finchè tutti i nodi hanno un rank assegnato.
Un albero di copertura si dice feasible se induce un ranking feasible. Per costruzione, tutti gli archi
nell’albero feasible sono stretti.
Dato un albero di copertura feasible, possiamo associare ad ogni arco d’albero un valore intero di
cut (taglio), nel modo seguente. Se quell’arco viene rimosso l’albero si spezza in due componenti
connesse, la componente di coda (contenente il nodo alla coda dell’arco) e la componente di testa
(contenente il nodo alla testa dell’arco). Il valore di cut è definito come la differenza tra la somma
dei pesi di tutti gli archi dalla componente di coda a quella di testa (compresi gli archi d’albero), e la
somma dei pesi di tutti gli archi dalla componente di testa a quella di coda (compresi gli archi
d’albero).
Pagina 39
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
Tipicamente (ma non nei casi degeneri) un valore di cut negativo indica che la somma delle
lunghezze degli archi pesati può essere ridotta allungando l’arco d’albero il più possibile finchè non
diventa stretto uno degli archi dalla componente di testa alla componente di coda.
Questo corrisponde a rimpiazzare l’arco d’albero nell’albero di copertura con il nuovo arco stretto,
ottenendo un nuovo albero di copertura.
Si nota facilmente che un ranking ottimo può essere usato per generare un altro ranking ottimo,
indotto da un albero di copertura feasible. Queste osservazioni sono la chiave per risolvere il
problema del ranking in un contesto grafico piuttosto che algebrico.
Gli archi d’albero con valori di cut negativi sono rimpiazzati da opportuni archi non d’albero, finchè
tutti gli archi d’albero hanno valori di cut non negativi.
Ogni implementazione di questa procedura deve utilizzare una tecnica per garantire che il
procedimento termini, ma questo non si è mai rivelato necessario nella pratica.
L’albero di copertura risultante corrisponde al ranking ottimale. Per ulteriori dettagli sulla
terminazione dell’algoritmo del simplesso e sull’ottimalità del risultato, si faccia riferimento alla
letteratura (Chvatal, Cunningham, Gansner).
Pagina 40
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
Progettazione di dettaglio di rank
1. rank() {
2.
feasibleTree();
3.
while( go ) {
4.
e = leaveEdge();
5.
if( e != null ) {
6.
f = enterEdge(e);
7.
exchange(e,f);
8.
}
9.
else go = false;
10.
}
11.
normalize();
12.
TBbalance();
13.
14.
fillRankStructure();
15. }
Figura 11 - Progettazione del ranking
La funzione feasibleTree costruisce un albero di copertura feasible iniziale. Questa procedura è
descritta più dettagliatamente in seguito. Il metodo del simplesso inizia con una soluzione feasible
e mantiene questa invariante.
leaveEdge ritorna un arco d’albero con un valore di cut negativo, oppure null se non ce ne sono e la
soluzione ottima è stata raggiunta. Un qualsiasi arco con un valore di cut negativo può essere
selezionato per la rimozione.
enterEdge individua un arco non d’albero per rimpiazzare e. Questo si fa spezzando l’arco e, che
divide l’albero nelle componenti connesse di testa e di coda. Tutti gli archi dalla componente di
testa a quella di coda vengono considerati, e quello con lo slack minimo viene selezionato. Questo
mantiene l’albero feasible.
In exchange gli archi vengono scambiati, aggiornando l’albero e i suoi valori di cut.
In normalize la soluzione viene normalizzata settando il rank minimo a zero.
In TBbalance i nodi che hanno i pesi degli archi entranti e uscenti uguali e più rank feasible vengono
spostati ad un rank feasible con il minor numero di nodi. Lo scopo è di ridurre l’affollamento dei
nodi e migliorare l’aspetto del disegno, secondo i principi già citati inizialmente. Queste operazioni
non cambiano il costo dell’assegnazione del rank. I nodi vengono gestiti con euristica greedy, il cui
funzionamento è sufficientemente buono.
Prima di passare allo step successivo è necessario che i nodi vengano salvati in una struttura dati
apposita per consentirne una gestione più comoda. A questo scopo l’algoritmo si dota di una lista di
Rank, oggetti al cui interno vengono salvati l’intero che identifica il livello e la lista dei nodi che vi
sono stati assegnati.
Pagina 41
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
Progettazione di dettaglio di feasibleTree
1. feasibleTree() {
2.
initRank();
3.
while (tightTree() < |V|) {
4.
e = a non-tree edge incident on the tree
5.
with a minimal amount of slack;
6.
delta = slack(e);
7.
if (incident node is e.head) delta = -delta;
8.
for v in Tree { v.rank = v.rank + delta; }
9.
}
10.
initCutvalues();
11. }
Figura 12 - Progettazione di feasibleTree
initRank calcola un ranking iniziale feasible. Questa versione tiene i nodi in una coda. I nodi
vengono inseriti nella coda quando hanno tutti gli archi entranti analizzati dall’algoritmo. Quando
un nodo viene rimosso dalla coda, gli viene assegnato il più piccolo rank che soddisfi i suoi archi
entranti, e i suoi archi uscenti devono essere analizzati. Nel caso più semplice in cui
= 1 per tutti
gli archi, ovvero il caso che andremo ad implementare, questo corrisponde a vedere il grafo come
un poset e ad assegnare l’elemento minimo al rank 0. Questi nodi vengono rimossi dal poset e il
nuovo insieme di elementi minimi vengono assegnati al rank 1, ecc.
tightTree individua un albero massimale di archi stretti, contenenti alcuni nodi fissati e ritorna il
numero di nodi nell’albero. Si noti che un albero massimale come questo è un albero di copertura
per il sottografo indotto dai nodi raggiungibili dal nodo fissato nel grafo non direzionato
sottostante, usando solo gli archi stretti. In particolare, tutti questi alberi hanno lo stesso numero di
nodi.
La porzione di codice dalla riga 4 alla 8 in figura individua un arco ad un nodo non d’albero, che sia
adiacente all’albero, e adatta il rank dei nodi d’albero per rendere questo arco stretto. Siccome
l’arco è scelto avendo lo slack minimo, il ranking risultante è ancora feasible. Perciò ad ogni
iterazione, l’albero guadagna almeno un nodo, e l’algoritmo alla fine termina con un albero di
copertura feasible. Questa tecnica è essenzialmente quella descritta da Sugiyama.
initCutvalues calcola i valori di cut per gli archi d’albero. Per ogni arco d’albero questo viene
calcolato marcando i nodi come appartenenti alla componente di coda o di testa, e poi calcolando
la somma dei pesi col segno di tutti gli archi le cui testa e coda si trovino in componenti diverse, con
segno negativo per gli archi che vanno dalla componente di testa a quella di coda.
Pagina 42
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
Un piccolo esempio di esecuzione dell’algoritmo di simplesso su reti è mostrato nella figura
sottostante.
Figura 13 - (a) e (b) - Verso un feasibleTree
Gli archi non d’albero sono tratteggiati e tutti gli archi hanno peso 1. Nella figura (a) mostriamo il
grafo dopo il ranking iniziale, con i valori di cut indicati. Ad esempio, il valore di cut dell’arco (g, h) è
-1, e corrisponde al peso dell’arco (g, h) (dalla componente di coda alla componente di testa) meno
il peso dell’arco (a, e) e (a, f) (dalla componente di testa a quella di coda). Nella figura (b), l’arco (g,
h) con un valore di cut negativo è stato rimpiazzato con un arco non d’albero (a, e), con i nuovi
valori di cut indicati. Siccome sono tutti non-negativi, la soluzione è ottima e l’algoritmo termina.
Dettagli implementativi
L’algoritmo del simplesso su reti e i risultati delle sue applicazioni sono ben noti e nella letteratura
si trovano studi che aiutano a metterne a punto l’implementazione (Chvatal).
Facciamo notare alcuni specifici dettagli implementativi che sono stati messi in pratica nella nostra
implementazione. Si tratta di ottimizzazioni utili, che diventano indispensabili qualora
un’implementazione debba essere applicata a grafi di dimensioni maggiori.
Il calcolo dell’albero feasible iniziale e dei valori di cut iniziali spesso occupa una parte significativa
del costo dell’intero algoritmo del simplesso su reti. Per molti grafi, nella pratica, la soluzione
iniziale è molto vicina alla soluzione ottima, perciò sono richieste poche iterazioni per raggiungere
la soluzione finale.
Pagina 43
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
Nella più semplice implementazione, i valori di cut iniziali possono essere trovati prendendo uno ad
uno ogni arco d’albero, spezzandolo, etichettando ogni nodo a seconda che appartenga alla
componente di testa o a quella di coda, e calcolando la somma. Questo procedimento ha costo
O(VE).
Per ridurre questo costo, notiamo che i valori di cut possono essere calcolati usando informazioni
locali ad ogni arco se la ricerca è ordinata dalle foglie dell’albero feasible verso l’interno.
È banale il calcolo dei valori di cut di un arco d’albero con un capo in una foglia dell’albero, poiché o
la componente di testa o la componente di coda consistono di un solo nodo.
Poi, assumendo che i valori di cut siano noti per tutti gli archi incidenti in un dato nodo tranne uno,
il valore di cut dell’arco rimanente sarà la somma dei valori di cut noti più un termine che dipende
solamente dagli archi incidenti nel nodo dato.
Illustriamo questo calcolo nella figura seguente nel caso in cui due archi d’albero, con valori di cut
noti, si connettono ad un terzo, con l’orientamento mostrato in figura. Gli altri casi vengono gestiti
in modo simile.
Figura 14 - Calcolo dei valori di cut
Assumiamo che i valori di cut di (u, v) e (v, w) siano noti. Gli archi etichettati con lettere maiuscole
rappresentano l’insieme di tutti gli archi non d’albero con la direzione data e le cui teste e code
appartengono alle componenti mostrate.
I valori di cut di (u, v) e (v, w) sono dati rispettivamente da:
c(u,w) = (u,w) + A +C + F - B - E -D
e
c(v,w) = (v,w) + L + I +D -K - J -C
Il valore di cut dell’arco (w,x) è quindi
c(w,x) = (w,x) +G -H + A - B + L -K
= (w,x) +G -H + (c(u,w) - (u,w) -C - F + E +D) + (c(v,w) - (v,w) - I -D + J +C)
= (w,x) +G -H + c(u,w) - (u,w) + c(v,w) - (v,w) - F + E - I + J
Pagina 44
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
un’espressione che coinvolge solo informazioni locali all’arco e valori di cut noti. Perciò calcolando i
valori di cut in modo incrementale, possiamo assicurare che ogni arco verrà esaminato solo due
volte, e questo riduce fortemente il tempo speso nel calcolo dei valori di cut iniziali.
Un’altra importante ottimizzazione, simile alla tecnica descritta da Chvatal, consiste nell’eseguire
un attraversamento dell’albero in postorder, partendo da un nodo radice fissato vroot, ed
etichettando ogni nodo v con il suo numero di attraversamento in postorder lim(v), con il numero
low(v) che è il più piccolo numero dei discendenti nella ricerca, e con l’arco parent(v) da cui il nodo
è stato raggiunto (figura seguente).
Figura 15 - Attraversamento in postorder con i nodi etichettati con (low,lim).
Questo ci fornisce un modo poco costoso per testare se un nodo giace nella componente di testa o
di coda in un arco d’albero, e se un arco non d’albero va da una componente all’altra. Per esempio
se e = (u, v) è un arco d’albero e vroot è nella componente di testa dell’arco (cioè lim(u) < lim(v))
allora un nodo w è nella componente di coda se e solo se low(u) ≤ lim(w) ≤ lim(u).
Questi numeri sono utilizzati anche per aggiornare l’albero in modo efficiente durante le iterazioni
dell’algoritmo del simplesso. Se f = (w, x) è l’arco entrante, i soli archi di cui vanno aggiornati i valori
di cut sono quelli nel percorso che connette w a x nell’albero. Questo percorso si determina
seguendo gli archi parent all’indietro da w a x finchè non si raggiunge l’ultimo antenato comune,
cioè il primo nodo l tale che low(l) ≤ lim(w) e lim(x) ≤ lim(l). Ovviamente questi parametri di
postorder devono essere aggiornati anche quando gli archi d’albero vengono scambiati, ma solo
per i nodi sotto il nodo l.
Il simplesso su reti è anche molto sensibile alla scelta dell’arco negativo da rimpiazzare. Si è
osservato che ricercando ciclicamente tra tutti gli archi d’albero, piuttosto che cercare dall’inizio
della lista degli archi d’albero ogni volta, permette di evitare molte iterazioni.
Pagina 45
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
5.5. Creazione strutture virtuali
Dopo l’assegnazione dei rank, gli archi che attraversano più di un livello vengono rimpiazzati con
catene di archi di lunghezza unitaria mediante l’uso di nodi virtuali. I nodi virtuali vengono collocati
nei rank intermedi, convertendo il grafo originale in un grafo i cui archi connettono solo nodi in
rank adiacenti. Questo perché da qui in poi non sarà sufficiente ordinare e gestire i nodi nei rank,
bensì sarà necessario considerare e gestire anche i punti di passaggio di un arco.
createVirtualStructure
0
0
1
1
2
2
3
3
4
4
5
5
6
6
order
Figura 16 - Esempio dell'effetto di CreateVirtualStructures
Per fare questo innanzitutto si localizzano nel grafo tutti gli archi di lunghezza non unitaria, quindi,
partendo dalla sorgente, fino ad arrivare alla destinazione, si creano man mano i nodi dummy, o
nodi virtuali, e le connessioni virtuali che li concatenano. I nodi e le connessioni create devono
essere marcate come virtuali per essere distinguibili dalle strutture originali del grafo. Le
connessioni originali nella nostra implementazione vengono solo “staccate” dalla sorgente e dalla
destinazione, e salvate in una lista, che consentirà alla fine il ripristino delle stesse. Nessuna
attenzione è richiesta per l’estetica del nodo e della connessione virtuale, essendo strutture
destinate ad essere utilizzate solo temporaneamente o in fase di test e debug del codice. L’unica
caratteristica che può essere utile a fini di debug è l’assegnazione di un nome identificativo univoco
per il nodo virtuale. A questo passaggio di creazione, ovviamente, corrisponde il passaggio inverso
di rimozione. Nel passaggio di ripristino degli archi lunghi originali, tuttavia, è necessaria una
procedura che conduca tali archi esattamente attraverso le coordinate prima occupate dai nodi
virtuali. I nodi dummy costituiscono, infatti, i punti di svolta o di curvatura degli archi lunghi da
ripristinare. Si individuano nel grafo, una ad una, le catene di nodi virtuali e percorrendo ognuna di
esse si salva una lista di punti di curvatura corrispondenti ai centri dei nodi virtuali; per ognuna di
esse viene quindi recuperata la connessione originale, e ad essa viene assegnato il router creato su
quei punti di curvatura.
Pagina 46
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
5.6. Ordinamento dei nodi nei rank
L’ordine dei nodi all’interno dei rank determina gli incroci tra archi nel layout, perciò un buon
ordinamento sarà quello con pochi incroci di archi. L’uso di euristiche è necessario poiché la
minimizzazione degli incroci tra archi nei layout di grafi con rank è un problema NP-completo,
anche per due soli rank (Eades, McKay e Wormald).
Numerose euristiche importanti per ridurre gli incroci tra archi nei grafi con rank sono basate sul
seguente schema suggerito da Warfield. Viene calcolato un ordine iniziale all’interno di ogni rank.
Poi viene eseguita una sequenza di iterazioni per migliorare gli ordinamenti. Ogni iterazione
attraversa il grafo dal primo rank all’ultimo, o viceversa. Quando un rank viene visitato, ad ognuno
dei suoi nodi viene assegnato un peso basato sulla posizione relativa dei nodi adiacenti nel rank
precedente. Quindi i nodi vengono riordinati in base a tali pesi.
order
0
0
1
1
2
2
3
3
4
4
5
5
6
6
position
Figura 17 - Esempio dell'effetto di order
Due metodi comuni per l’assegnazione dei pesi ai nodi sono la funzione baricentro (Sugiyama) e la
funzione mediana (Eades, Wormald).
Supponiamo che v sia un nodo e P sia la lista delle posizioni dei nodi a lui adiacenti nel rank
precedente. Notiamo che la posizione di un nodo adiacente è nient’altro che il numero ordinale
nell’ordine corrente.
Il metodo del baricentro definisce il peso del nodo v come la media degli elementi in P. Il metodo
della mediana definisce il peso del nodo v come la mediana degli elementi in P. Quando il numero
degli elementi in P è pari, ci sono due mediane, e questo dà luogo a due metodi della mediana,
quello che sceglie sempre la mediana di sinistra e quello che sceglie sempre la mediana di destra.
Pagina 47
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
Il metodo della mediana ha performance migliori del metodo del baricentro e ha un leggero
vantaggio teorico, dal momento che Eades e Wormald hanno mostrato che il layout con il metodo
della mediana di un grafo di due livelli ha non più di tre volte il minimo numero di incroci d’archi.
Nessun limite simile è noto per il metodo del baricentro.
L’euristica qui utilizzata per l’ordinamento dei nodi è un raffinamento del metodo della mediana,
con due innovazioni. La prima consiste nel fatto che, in presenza di due valori di mediana, usiamo
un valore interpolato che dipende dal lato in cui i nodi sono più concentrati. Il secondo
miglioramento usa un’euristica aggiuntiva che riduce gli incroci ovvi dopo che i vertici sono stati
ordinati, trasformando un dato ordinamento in uno localmente ottimo rispetto alla trasposizione di
vertici adiacenti. Questo comporta una riduzione degli incroci del 20-50% in più.
Per statistiche più dettagliate, far riferimento all’articolo di Gansner.
Pagina 48
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
Progettazione di dettaglio di order
1. order() {
2.
initOrder();
3.
for i = 0 to maxIterations {
4.
int oldCrossing = crossing();
5.
saveOrders();
6.
wmedian(i);
7.
transpose();
8.
if( oldCrossing < newCrossing ) {
9.
restoreOrders();
10.
}
11.
}
12. }
Figura 18 - Progettazione di order
initOrder inizialmente ordina i nodi in ogni rank. Questo può essere fatto con una ricerca in
ampiezza o in profondità nel grafo, partendo dai nodi del rank minimo. Qui scegliamo
l’implementazione con la ricerca in profondità. Ai vertici sono assegnate le posizioni nei rispettivi
rank in ordine da sinistra a destra man mano che la ricerca avanza. Questa strategia assicura che
l’ordine iniziale di un albero non abbia alcun incrocio. Questo è importante perché tali incroci sono
ovvi e si possono evitare facilmente.
maxIterations è il numero minimo di iterazioni, settato, nel nostro caso, a 24. Ad ogni iterazione,
viene innanzitutto calcolato il numero di crossing, e l’ordine viene salvato prima di essere
modificato dall’interazione corrente; se il numero di incroci non diminuisce, l’ordine precedente
viene ripristinato. In generale un’implementazione può anche avvalersi di una strategia adattativa
che itera finchè la soluzione non viene migliorata almeno di una certa percentuale rispetto alle
iterazioni precedenti.
wmedian riordina i nodi dentro ogni rank, basandosi sull’euristica della mediana pesata.
transpose scambia ripetutamente nodi adiacenti sullo stesso rank se questo comporta una
diminuzione del numero di incroci. Di queste funzioni diamo una descrizione più dettagliata qui di
seguito.
Progettazione di dettaglio di median e medianValue
L’euristica della mediana pesata viene mostrata nella figura che segue. A seconda della parità del
numero dell’iterazione corrente, i rank sono attraversati dall’alto verso il basso o dal basso verso
l’alto. Presentiamo qui una sola delle due direzioni poiché l’altra è analoga.
Pagina 49
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
1. wmedian(iter) {
2.
if( iter % 2 == 0 ) {
3.
for r = 1 to maxRank {
4.
for node in rank r
5.
median = medianValue(node, i-1);
6.
node.setMedian(median);
7.
sort(r, median);
8.
}
9.
else {…}
10. }
Figura 19 - Progettazione di wmedian
Nell’attraversamento dei rank in avanti, il ciclo principale parte dal rank 1 e termina al rank
massimo. Ad ogni rank ai nodi viene assegnata una mediana basata sui vertici adiacenti del rank
precedente. Poi i vertici nel rank vengono ordinati in base ai valori di mediana. Si deve fare una
considerazione importante sulla gestione dei vertici che non hanno adiacenti nel rank precedente:
in questa implementazione tali vertici vengono fissati a sinistra dei rimanenti vertici.
1. medianValue(v, adjRank) {
2.
P = adjPosition(v, adjRank);
3.
m = |P| / 2;
4.
if |P| = 0
5.
return -1;
6.
if |P| % 2 == 1
7.
return P[m];
8.
if |P| == 2
9.
return (P[0] + P[1])/2;
10.
else {
11.
left = P[m-1] - P[0];
12.
right = P[|P|-1] - P[m];
13.
return (P[m-1]*right + P[m]*left)/(left+right);
14.
}
15. }
Figura 20 - Progettazione di medianValue
Il valore di mediana di un nodo è definito come la posizione mediana dei vertici adiacenti nel rank
indicato, se unicamente determinata. Altrimenti è l’interpolazione tra le due posizioni mediane.
Generalmente la mediana pesata dipende dal lato in cui i nodi sono più concentrati.
La funzione adjPosition ritorna un array ordinato delle posizioni attuali dei nodi adiacenti a v nel
dato rank adiacente.
Ai nodi privi di adiacenti viene assegnato il valore di mediana -1. Questo viene usato nella funzione
di ordinamento per indicare che questi nodi devono essere posizionati a sinistra.
Pagina 50
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
Progettazione di dettaglio di transpose
La figura seguente mostra l’euristica di trasposizione.
1. transpose()
2.
improved = true;
3.
while (improved) {
4.
improved = false;
5.
for r = 0 to maxRank {
6.
for i = 0 to |r|-2 {
7.
v = r.nodes.get(i);
8.
w = r.nodes.get(i+1);
9.
int crossBefore = crossing();
10.
exchangeOrders(rank,v,w);
11.
int crossAfter = crossing();
9.
if crossAfter < crossBefore
10.
improved = true;
11.
else
11.
exchangeOrders(rank,v,w);
12.
}
13.
}
14.
}
15. }
Figura 21 - Progettazione di traspose
Il ciclo principale itera finchè il numero di incroci tra archi può essere ridotto da trasposizioni. Come
nel ciclo della funzione di ordinamento, si può eventualmente applicare una strategia adattativa
per terminare il ciclo una volta che il miglioramento sia una certa percentuale del numero di
incroci.
Ogni coppia di vertici adiacenti viene esaminata. La funzione crossing conta il numero di incroci,
dapprima con v che appare alla sinistra di w in quel rank, poi con v che appare alla destra di w in
quel rank; se si è avuto un miglioramento si mantiene quell’ordinamento per quei due nodi,
altrimenti si ripristina il loro ordine iniziale.
Quando si ordinano i nodi in base alla mediana e si effettua una trasposizione tra nodi adiacenti,
può verificarsi l’uguaglianza nel confronto tra mediane o tra numero di incroci di archi. È stato
ritenuto utile invertire i nodi con valori uguali durante l’ordinamento o i passi di trasposizione, sia
negli attraversamenti in avanti che all’indietro.
Un punto che val la pena di sottolineare è la possibilità di eseguire l’algoritmo di ordinamento dei
nodi due volte: una che inizia dai nodi del rank minimo e ricerca sugli archi uscenti, una che inizia
dai nodi del rank massimo e ricerca usando gli archi entranti. Questo permette di scegliere al
termine la migliore tra le due soluzioni.
Pagina 51
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
5.7. Posizionamento dei nodi
Una volta ottenuto un ordinamento corretto all’interno dei rank, è necessario individuare qual è la
corretta posizione dei nodi. In questo passaggio ancora non si assegnano coordinate, che sarà il
lavoro del prossimo passo descritto. Qui si considera di disporre i nodi del grafo all’interno di una
griglia, le cui righe corrispondono ai rank, e le cui colonne determinano quella che qui chiamiamo la
position dei nodi.
position
0
0
0
1
1
2
2
3
3
4
4
5
5
6
6
1
2
3
assignCoord
Figura 22 - Esempio dell'effetto di position
L’euristica scelta è piuttosto semplice e intuitiva, e particolarmente adatta al tipo di grafi per il
quale il progetto si applica.
1. position() {
2.
initPositions();
3.
int fullRankIndex = fullRank();
4.
//downward from the full rank
5.
for i = fullRankIndex+1 to maxRank {
6.
positioningInRank(i, true);
7.
}
8.
//upward from the full rank
9.
for i = fullRankIndex-1 to minRank {
10.
positioningInRank(i, false);
11.
}
12. }
Figura 23 - Progettazione di position
Pagina 52
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
position innanzitutto inizializza la posizione di ogni nodo del grafo banalmente utilizzando il numero
d’ordine attribuitogli dal passo precedente, perciò i nodi inizialmente si trovano tutti ammassati
sulla sinistra. Viene poi individuato il rank col maggior numero di nodi, perché quello determinerà
le posizioni di tutti gli altri nodi del grafo. Per quel rank le posizioni rimangono quelle assegnate
dall’inizializzazione.
Verranno quindi posizionati i nodi dei rank sottostanti a quello full, partendo da quello subito sotto,
fino all’ultimo rank (downward); e, in modo analogo, verranno poi posizionati i nodi dei rank
sovrastanti quello full, partendo da quello subito sopra fino al primo rank (upward).
positioningInRank agisce nel modo che ora descriviamo. Calcola per ogni nodo nel rank il valore
della mediana, rispetto al rank sopra nel caso di downward, rispetto al rank sotto se si tratta di
upward. Il valore di mediana è considerato come il miglior valore di posizione che il nodo possa
assumere, e, se nessun altro nodo occupa quella posizione, essa sarà assegnata al nodo. Se invece
la posizione è occupata da un altro nodo allora esso dovrà essere posizionato nella più vicina
posizione libera, coerentemente con l’order di quel nodo rispetto all’order del nodo che già occupa
quella posizione. Si itera sempre più a sinistra o sempre più a destra (a seconda che il nodo
occupante abbia order rispettivamente maggiore o minore) finchè non si trova una posizione libera.
Un caso a parte è costituito dai nodi che non hanno adiacenti nel rank sopra nel caso di downward,
o nel rank sotto nel caso di upward. Questi sono caratterizzati da valore di mediana -1 e vengono
memorizzati in una lista apposita, da gestire successivamente in positioningInRank, dopo che quelli
con adiacenti son stati posizionati. La gestione che abbiamo progettato consiste nel posizionare tra
questi ultimi i nodi senza adiacenti, in modo coerente con l’order assegnato.
Pagina 53
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
5.8. Assegnazione delle coordinate
La griglia che citavamo al passo precedente viene qui effettivamente calcolata, perché questo è
l’ultimo step, incaricato di assegnare le coordinate ai nodi. Si ricorda che le coordinate assegnate ai
nodi virtuali andranno a determinare i punti di svolta degli archi non unitari.
Innanzitutto c’è la necessità di conoscere l’altezza di ogni riga e la larghezza di ogni colonna della
griglia nella quale andranno idealmente disposti i nodi. L’altezza di una riga è determinata dalla
massima tra le altezze dei nodi di quel rank (sommata ad un margine aggiuntivo), e, con lo stesso
principio, la larghezza di una colonna sarà determinata dalla massima tra le larghezze dei nodi con
quella position (sommata ad un margine aggiuntivo).
A questo punto si possono scorrere i rank, e assegnare le coordinate ai nodi, in modo che ognuno di
essi sia piazzato centralmente in larghezza e in altezza all’interno della giusta cella della griglia, con
particolare attenzione al fatto che l’assegnazione della coordinata è relativa al vertice in alto a
sinistra del nodo, per come è stabilito da Zest, non al centro del nodo come comunemente si
potrebbe pensare. Le coordinate x e y calcolate vengono quindi passate a Zest attraverso
l’opportuno metodo ed è cura di Zest stesso e delle librerie grafiche sottostanti produrre il
rendering del grafo.
assignCoord
0
1
2
3
0
0
0
1
1
2
3
1
2
3
hide
virtual
structures
2
3
4
4
5
6
5
6
Figura 24 - Esempio dell'effetto di assignCoordinates
Solo dopo quest’ultimo step vengono intraprese le operazioni di postprocessing per ripristinare le
strutture originali del grafo, come già citato nella sezione 5.5. Mostriamo qui di seguito il risultato
grafico sull’esempio che ha accompagnato la descrizione di tutti gli step.
Si noti che l’esempio è molto simile al grafo di processo “Esempio 4” alla sezione 6.2, quindi si
suggerisce di osservare tale immagine per avere un’idea della resa grafica finale ottenuta
attraverso la libreria Java implementata.
Pagina 54
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
5. Fase di progettazione
hideVirtualStructures
0
1
2
3
0
0
0
1
1
2
2
3
3
4
4
5
5
6
6
1
2
Figura 25 - Esempio dell'effetto di hideVirtualStructures
Pagina 55
3
end
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
6. La libreria realizzata
6. La libreria realizzata
6.1. Dettagli implementativi
Come si legge nei requisiti, la libreria implementata in questo progetto doveva disporre, oltre che
dell’algoritmo di autolayout, anche delle funzionalità di esportazione dell’immagine del grafo come
file JPEG, o PNG, nonché della possibilità di creare nodi con un’estetica migliore e più flessibile di
quella fornita da GraphViz. Vediamo questi due punti separatamente.
L’estrazione di un file di immagine del grafo
Nell’implementazione di questa funzionalità è stato indispensabile l’aiuto della community di Zest,
che attraverso il forum e newsgroup ha reso disponibili le conoscenze personali degli utenti di Zest.
L’implementazione dell’estrazione dell’immagine come file PNG (ad esempio), innanzitutto
necessita di conoscere le dimensioni dell’intero grafo in larghezza e altezza. Crea quindi una Image
(org.eclipse.swt.graphics.Image) vuota usando tali dimensioni. Su tale image crea un oggetto GC
(org.eclipse.swt.graphics.GC), ovvero un contesto grafico. Su tale contesto grafico costruisce un
oggetto SWTGraphics (org.eclipse.draw2d.SWTGraphics), che passa come parametro per invocare
il metodo paint sulla IFigure (org.eclipse.draw2d.IFigure) costituita dal grafo. Quindi copia l’area del
contesto grafico che contiene l’immagine, nell’oggetto Image vuoto creato inizialmente.
A questo punto, l’oggetto image contiene il rendering del grafo, ed è ora necessario che venga
salvato un file immagine con l’opportuna codifica.
A questo scopo si crea un ImageLoader (org.eclipse.swt.graphics.ImageLoader), la classe SWT usata
per caricare o salvare immagini nei possibili formati: BMP (Windows o OS/2 Bitmap), ICO (Windows
Icon) , JPEG, GIF, PNG, TIFF.
Dell’oggetto
ImageLoader
viene
settato
il
campo
data
con
l’oggetto
ImageData
(org.eclipse.swt.graphics.ImageData) della Image usata fin qui.
Quindi finalmente si può invocare il metodo save(String filename, int format) sull’ImageLoader che
ci
consente
la
creazione
effettiva
del
file,
ad
esempio
loader.save("myGraph.png",
SWT.IMAGE_PNG).
Ovviamente al termine di questo metodo si deve invocare dispose() sugli oggetti GC, Image, e
SWTGraphics, perché vengano rilasciate le risorse di sistema.
Pagina 56
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
6. La libreria realizzata
L’estetica dei nodi
Nell’implementazione di questa funzionalità è stata indispensabile la consultazione delle API
Specification per una maggiore comprensione delle librerie grafiche sottostanti a Zest.
Come già anticipato, l’unico modo per uscire dai limiti estetici dei GraphNode è quello di utilizzare i
CGraphNode di Zest, ovvero la versione customizzabile nell’aspetto dei nodi.
Tale libertà di customizzazione, tuttavia, obbliga l’utilizzatore ad implementare da zero la figura e il
suo contenuto, con cui sostituire il classico rounded rectangle dei GraphNode. Ovviamente sarebbe
stato preferibile avere la possibilità di customizzare la shape semplicemente con l’uso di un
setShape, ma tale funzionalità non è ancora disponibile nonostante molti utenti di Zest ne sentano
l’esigenza. Abbiamo perciò implementato un metodo che crea ad hoc una Figure
(org.eclipse.draw2d.Figure) per i nostri nodi customizzati, da passare al costruttore di CGraphNode.
In questo metodo innanzitutto creiamo una Label (org.eclipse.draw2d.Label), ovvero una figura in
grado di fare il display di testo e/o immagine, e questo ci consente di creare il nodo con un’icona
così come richiesto dai requisiti. Questa label andrà quindi aggiunta ad una Figure, alla quale
compete la shape del nodo.
Per realizzare grafi di processo come quelli forniti dal team di Spagic, abbiamo dovuto realizzare le
seguenti forme:
CIRCLE, a rappresentare il Flow Object di Start Event;
BOLD_CIRCLE, a rappresentare il Flow Object di End Event;
ROUNDED_RECTANGLE, a rappresentare il Flow Object di Task Activity;
DIAMOND, a rappresentare il Flow Object di Gateway, anche detto router in Spagic Studio.
Tuttavia, la realizzazione di altre forme, anche più complesse, diventa molto semplice seguendo
l’implementazione di queste figure di base.
Pagina 57
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
6. La libreria realizzata
6.2. I risultati ottenuti
Vediamo ora alcuni esempi di come possono cambiare i grafi di processo attraverso l’uso della
libreria sviluppata in questo progetto. Per ogni esempio mostreremo:
il grafo così come sarebbe ottenuto dal motore di GraphViz, con degli esempi di etichette,
posizionate sui nodi in modo simile a come accade attualmente in Spagic, mostrando così il
tipico aspetto del grafo di processo visualizzato attualmente in Spagic Monitor;
lo stesso grafo, generato come immagine dall’esecuzione del codice sviluppato in questo
progetto, scegliendo alcune delle possibilità a disposizione per le caratteristiche estetiche dei
nodi (colori ed esempi di icone);
per il primo esempio, anche la fase di design del processo: il diagramma visualizzato in Spagic
Studio per quel processo.
Le strutture dei grafi che presentiamo come esempi appartengono a processi effettivamente in uso
da parte di business users di Spagic; in queste immagini i testi delle etichette sono stati sostituiti
con testi generici e a solo scopo dimostrativo.
Esempio 1
Figura 26 - Design del processo Esempio1 in Spagic Studio
Pagina 58
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
6. La libreria realizzata
Figura 27 - Diagramma per il
processo Esempio1 generato da
GraphViz per Spagic Monitor
Figura 28 - Diagramma per
il processo Esempio1 generato
dalla nuova libreria
Pagina 59
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
6. La libreria realizzata
Esempio 2
Figura 29 - Diagramma per il
processo Esempio2 generato da
GraphViz per Spagic Monitor
Pagina 60
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
6. La libreria realizzata
Figura 30 - Diagramma per il
processo Esempio2 generato dalla
nuova libreria
Pagina 61
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
6. La libreria realizzata
Esempio 3
Figura 31 - Diagramma per il processo
Esempio3 generato da GraphViz per Spagic
Monitor
Pagina 62
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
6. La libreria realizzata
Figura 32 - Diagramma per il
processo Esempio2 generato
dalla nuova libreria
Pagina 63
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
6. La libreria realizzata
Esempio 4
Figura 33 - Diagramma per il
processo Esempio4 generato da
GraphViz per Spagic Monitor
Pagina 64
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
6. La libreria realizzata
Figura 34 - Diagramma per il
processo Esempio4 generato dalla
nuova libreria
Pagina 65
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
6. La libreria realizzata
Nota sull’efficienza
La libreria realizzata utilizza euristiche che consentono un’esecuzione efficiente in tempo per tutti i
casi più comuni. Il suo utilizzo è pensato per diagrammi di processi, i quali sono caratterizzati da un
numero di nodi piuttosto contenuto, nell’ordine di qualche decina, e sicuramente sotto il centinaio.
Questo non costituisce un limite fintanto che la libreria è utilizzata per gli scopi per i quali è stata
pensata. Si immagini infatti un BPD di centinaia di nodi: esso sarà un diagramma talmente
complesso da essere illeggibile dagli stessi utenti, e sarebbe comunque sgradevolmente
voluminoso per essere monitorato in uno strumento di console.
L’efficienza di questo codice sviluppato in Java è certamente inferiore a quello sviluppato in C su cui
esegue GraphViz, per la nota efficienza del codice procedurale in C. Tuttavia, si accetta la perdita di
efficienza nell’implementazione Java dello stesso pseudocodice, in cambio di un drastico aumento
di espressività e leggibilità, indispensabili perché il codice possa essere in futuro manutenuto e
modificato senza difficoltà dal team di Spagic, così come dal team di Zest, o di qualunque altro
team di programmatori.
Pagina 66
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
7. Fase di test
7. Fase di test
Lo sviluppo della libreria ha visto una fase di implementazione delle funzionalità grafiche ed
estetiche, ed una fase di implementazione dell’algoritmo di autolayout. Una volta testato il corretto
funzionamento della grafica di nodi e connessioni, si sono sfruttate tali funzionalità grafiche per
una più agevole fase di verifica dell’implementazione dell’algoritmo di autolayout.
Lo sviluppo dell’algoritmo di autolayout è avvenuto per fasi, corrispondenti agli step descritti nella
sezione 5. Ognuna di queste fasi ha visto una fase di implementazione, seguita da una fase di
verifica e validazione. La strategia di verifica è stata volta a garantire che eventuali errori emersi in
una particolare fase fossero il risultato di problemi o incongruenze relativi alla fase stessa e non a
fasi precedenti. Grazie a questo principio è stato possibile testare ogni step dell’algoritmo
sfruttando gli step precedentemente implementati e correttamente funzionanti, allo scopo rendere
i test semplici da realizzare e i risultati dei test immediatamente comprensibili.
La verifica del codice sviluppato in una fase veniva realizzata attraverso test volti a controllare che
l’output di una fase fosse corretto e conforme alle aspettative. Tali test hanno utilizzato esempi di
grafo come quelli che si possono osservare alla sezione 6, ovvero grafi di processo forniti dal team
di sviluppo Spagic, che li ha tratti da ambienti di produzione che utilizzano Spagic come soluzione di
integrazione tra applicativi. Tali grafi rappresentano perciò reali processi in uso. Il set di grafi
fornito, inoltre, spazia dai grafi più semplici a quelli più complessi, a rappresentare nel modo più
completo i possibili grafi per i quali l’algoritmo sarà utilizzato. La selezione dei grafi
“rappresentanti” dei possibili utilizzi è stata per lo più di competenza del team Spagic, che possiede
l’esperienza e la conoscenza degli usi di questo prodotto. A questi esempi sono stati aggiunti
numerosi altri, finalizzati al test di particolari casistiche. Si tratta per lo più di test effettuati
manualmente, facendo girare l’algoritmo su tali grafi e rilevando ad ogni step le incongruenze,
risolte completamente prima di cominciare lo sviluppo della fase successiva.
La tabella seguente spiega più in dettaglio le funzionalità testate.
validGraph
Questo passo è stato testato eseguendo l’algoritmo su grafi non
accettabili creati ad hoc: grafo vuoto, grafo con nodi isolati, grafo
con cappi, grafo con archi multipli, grafo non connesso.
breakCycle
Questo passo è stato testato eseguendo l’algoritmo su grafi con e
senza cicli. In particolare, dapprima su grafi con un singolo ciclo,
poi su grafi con più cicli, verificando che il metodo rilevasse
Pagina 67
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
7. Fase di test
correttamente gli archi di feedback.
Successivamente è stato testato il corretto funzionamento
dell’inversione logica degli archi di feedback, e prima di
procedere alle fasi successive è stato testato che anche il
ripristino della direzione originaria degli archi fosse
correttamente implementato.
In questa fase si è rilevato che l’inversione è solamente logica: i
metodi utilizzati per invertire gli archi non hanno alcun effetto a
livello grafico poiché la libreria grafica sottostante continua a
disegnare l’arco con la direzione con cui è stato creato. Questo
aspetto non è stato ulteriormente indagato poiché per gli usi del
nostro algoritmo questo comportamento è irrilevante.
rank
Questo passo è stato testato su tutti i grafi di esempio,
osservando quale rank venisse assegnato dall’algoritmo
implementato da GraphViz. Essendo il layout di GraphViz
considerato corretto, si sono confrontati i risultati della nostra
implementazione con i risultati di GraphViz sullo stesso grafo.
Le fasi successive dell’algoritmo necessitavano della creazione
delle strutture virtuali, e all’implementazione di questa è seguito
il test sulla corretta creazione. Tale test è consistito nella
visualizzazione delle strutture virtuali con cui gli archi non unitari
venivano logicamente sostituiti, attraverso l’output grafico
createVirtualStructures
dell’algoritmo. Ovviamente, prima di implementare le fasi
hideVirtualStructures
successive, si è implementata la rimozione delle strutture virtuali,
e testato (sempre graficamente) il corretto funzionamento.
In particolare, in quest’ultimo test si è testato anche il routing
degli archi non unitari.
order
Innanzitutto sono stati testati singolarmente i metodi che
compongono questa fase: il metodo di inizializzazione degli
order, il metodo di valore mediano e il metodo della mediana, il
metodo di trasposizione e il metodo che conta gli incroci tra gli
archi. Una volta garantito il corretto funzionamento dei singoli
metodi, si è passati al test dell'intero metodo order sui grafi di
esempio, su cui erano già stati eseguiti i passi precedenti.
Sebbene l'ordinamento dei nodi fosse talvolta diverso da quello
eseguito da GraphViz per gli stessi grafi, il numero di incroci di
archi risultante appariva il medesimo, quindi si è ritenuto che lo
step sia stato correttamente implementato.
Pagina 68
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
7. Fase di test
position
assignCoordinates
L'euristica implementata per assegnare l'effettiva posizione dei
nodi è stata testata sempre attraverso l'esecuzione della stessa
sui grafi di esempio, verificando che effettivamente ai nodi
venisse assegnata la posizione corretta. La verifica dei risultati dei
test è stata facilitata dal fatto che la libreria grafica sottostante
(Zest) permettesse l'interazione con i nodi nella finestra del
grafo, in modo da poter simulare manualmente l'euristica scelta,
e confrontarne il risultato con l'assegnazione ottenuta.
Per testare quest'ultimo step è stato sufficiente eseguirlo sugli
esempi di grafi, verificando visivamente che il risultato fosse
coerente con le aspettative, ovvero che i nodi fossero disposti
idealmente sulla griglia che è stata implementata, ottenendo
come risultato un allineamento dei nodi ordinato ed
esteticamente gradevole.
Pagina 69
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
8. Tracciamento dei requisiti
8. Tracciamento dei requisiti
Nella tabella seguente illustriamo come i requisiti siano stati rispettati, controllo che è stato
effettuato anche dal team di Spagic in fase di consegna.
Linguaggio e sviluppo:
1. Deve essere sviluppata in Java, per consentire l’integrazione
all’interno di Spagic.
2. Deve far parte di un progetto maturo, supportato e ben
documentato; deve essere rilasciata in una versione testata e
stabile (non in versione alpha). Inoltre deve trattarsi di un
progetto sufficientemente valido da scongiurarne l’abbandono
da parte dei developer, e per il quale si esclude con
ragionevole certezza una chiusura del codice per i rilasci futuri.
Zest è sviluppata in Java e
così anche la nuova libreria
costruita su di esso.
Come già verificato in fase di
scelta della libreria, Zest fa
parte di un progetto maturo,
stabile e ben supportato.
Attraverso lo studio della
libreria Zest si è ovviato al
problema della mancanza di
documentazione.
Licenza:
3. Deve essere free e open source, con una licenza compatibile
con i fini dell’intero progetto Spagic, quindi deve essere
modificabile e utilizzabile a scopo commerciale. Deve avere
perciò licenza LGPL, EPL, o compatibile con queste.
Come già verificato in fase di
scelta, la licenza di Zest è
EPL, e con la stessa licenza è
rilasciato il nuovo codice
sorgente.
Funzionalità:
4. Deve essere in grado di rappresentare grafi, più in particolare
diagrammi in BPMN, permettendo la rappresentazione di tutte
le parti che ne compongono la struttura: nodi e archi, con le
Queste sono funzionalità
fornite da Zest nativamente.
etichette testuali.
5. Nella rappresentazione dei nodi deve essere prevista anche
l’informazione visuale: per i nodi devono essere specificabili
forma, dimensione, colorazione ed immagine contenuta,
mentre per gli archi è gradito che sia specificabile lo stile.
6. Deve essere possibile esportare il grafo rappresentato
sottoforma di immagine bidimensionale, in formato JPEG o
PNG.
Pagina 70
Queste
funzionalità
di
estetica dei nodi sono state
implementate a partire dalle
strutture
messe
a
disposizione da Zest.
Questa funzionalità è stata
implementata
attraverso
nuovi metodi che sfruttano le
classi di SWT e Draw2d.
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
8. Tracciamento dei requisiti
7. Deve essere implementato nella libreria un algoritmo di
autolayout, che generi layout verticali (ed eventualmente
anche orizzontali), in grado di disporre in modo ordinato i nodi,
Questa funzionalità è stata
implementata con la classe
SugiyamaLayoutAlgorithm
descritta nelle sezioni 5 e 6.
affinché il diagramma risulti leggibile e dall’aspetto gradevole.
8. Deve presentare le funzionalità ai punti 6 e 7, ma in passaggi
distinti, in modo che rimangano disponibili le coordinate dei
vertici generate dall’algoritmo di layout indipendentemente
dall’esportazione del grafo come immagine, per poter
utilizzare tali coordinate per la creazione di mappe via CSS.
Le coordinate dei nodi del
grafo, una volta calcolate,
vengono mantenute come
informazione
all’interno
degli oggetti GraphNode e
continuano
ad
essere
disponibili.
9. Non deve precludere la possibilità che l’immagine del
diagramma
dell’istanza
di
processo
venga
creata
dinamicamente piuttosto che essere creata una volta soltanto
e poi personalizzata attraverso l’uso di fogli di stile.
Pagina 71
Nessuna caratteristica della
libreria preclude questa
possibilità.
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
9. Conclusioni
9. Conclusioni
Sviluppi futuri
Come già anticipato, il risultato di questo progetto, ovvero la libreria creata, sarà utilizzato per
migliorare l’aspetto grafico della console di monitoring dei processi in Spagic. L’integrazione della
libreria in Spagic è previsto a breve, non appena saranno implementate la parte che fornirà in
automatico all’algoritmo le informazioni sulla struttura del grafo su cui eseguire e il sistema di
mappe html e css per la pagina web di processo, che renda interattiva la visualizzazione
dell’immagine del diagramma, e ne consenta la visualizzazione delle proprietà e dello stato.
Un altro utilizzo di questa libreria è come possibile miglioramento del progetto Zest. La libreria,
infatti, implementa funzionalità che non erano nativamente disponibili in Zest, e perciò è stata
proposta come contribuzione al progetto Zest. I creatori del progetto Zest sono stati contattati via
mailing list del progetto GEF, e di persona dai componenti del team di Engineering in occasione
dell’EclipseCon 2010. La libreria di questo progetto sarà perciò sottoposta all’attenzione del team di
Zest, e, con opportune modifiche che la rendano perfettamente integrabile nel progetto originale,
potrà divenire un’utile contribuzione, e sarà resa disponibile alla comunità scientifica non solo
tramite il codice sorgente aperto di Spagic, ma anche attraverso il codice sorgente aperto del plugin
di Eclipse, Zest.
Ringraziamenti
Si ringraziano sentitamente tutti coloro i quali sono stati di supporto allo svolgimento di questo
progetto e di questa tesi. In particolare si ringrazia il Dott. Gianfranco Boccalon e tutto il team di
Spagic e di Engineering.
Pagina 72
Università degli Studi di Padova - LS Informatica
Generazione di grafi in BPMN - Contiero Erika
10. Bibliografia
10. Bibliografia
“Graph Drawing - Algorithms for the Visualization of Graphs” G. Di Battista, P. Eades, R.
Tamassia, I. G. Tollis - 1998 - Prentice Hall
“Introduction to BPMN” Stephen A. White; IBM Corporation
www.graphviz.org
www.graphviz.org/pub/graphviz/development/doxygen/html/index.html
“A Technique for Drawing Directed Graphs” Emden R. Gansner, Eleftherios Koutsofios, Stephen
C. North, Kiem-Phong Vo; AT&T Bell Laboratories
Carpano, M., “Automatic display of hierarchized graphs for computer aided decision analysis”
IEEE Transactions on Software Engineering SE-12(4), 1980, pp. 538-546.
Chvatal, V., “Linear Programming”, W. H. Freeman, New York, 1983.
Cunningham, W. H., “A network simplex method” Mathematical Programming 11, 1976, pp.
105-116.
Eades, P., B. McKay and N. Wormald, “On an Edge Crossing Problem” Proc. 9th Australian
Computer Science Conf., 1986, pp. 327-334.
Eades, P. and Roberto Tamassia, “Algorithms for Automatic Graph Drawing: An Annotated
Bibliography” Technical Report CS-89-09 (Revised Version), Brown University, Department of
Computer Science, Providence RI, October 1989.
Gansner, E. R., S. C. North and K.-P. Vo, “DAG - A Program that Draws Directed Graphs”
Software - Practice and Experience 17(1), 1988, pp. 1047-1062.
Gansner, E. R., S. C. North and K.-P. Vo, “On the Rank Assignment Problem”.
Sugiyama, K., S. Tagawa and M. Toda, “Methods for Visual Understanding of Hierarchical
System Structures” IEEE Transactions on Systems, Man, and Cybernetics SMC-11(2), February,
1981, pp. 109-125.
www.eclipse.org/gef/zest/
Pagina 73