Il sistema LEDA: applicazioni ed estensioni con primitive insiemistiche

0.1 Introduzione 
 
La programmazione Object Oriented ha aperto nuovi orizzonti per quanto 
riguarda il problema del riutilizzo del Software. Il sistema L.E.D.A. (Library of 
Efficient Data Types and Algorithms) rappresenta un tentativo, peraltro ben 
riuscito, di fornire un valido strumento di lavoro a coloro che si occupano di 
algoritmi nelle aree della geometria computazionale e del calcolo combinatorico, 
siano essi principianti o esperti. 
 
La Tesi è sostanzialmente divisa in due parti: 
- nella prima cercheremo di introdurre il sistema LEDA, estrapolandone i 
dettagli con l'obiettivo dichiarato di fornire una vera e propria guida da 
affiancare al manuale di LEDA; in particolare analizzeremo le peculiarità del 
sistema attraverso una breve, ma completa, descrizione di tutte le 
caratteristiche di base fornendo, se necessario, utili esemplificazioni di 
carattere implementativo; 
 
- la seconda parte è invece dedicata alle applicazioni. Vedremo innanzitutto 
come sia stato possibile estendere il sistema con nuove primitive 
insiemistiche. In particolare sono state implementate, ed integrate con quelle 
già presenti, opportune procedure che realizzano le operazioni di unione, 
intersezione, differenza, differenza simmetrica nonche utili operatori di 
confronto tra insiemi. I tipi di dato set ed int_set di LEDA, che implementano 
appunto gli insiemi, sono stati quindi notevolmente potenziati. 
 
Un cenno a parte merita l'introduzione del tipo di dato tupla la cui 
implementazione, oltre a rendere disponibili tutte le operazioni di base (quali 
concatenazione, inserimento, cancellazione, ricerca, ...), supporta anche la 
possibilità di considerare tuple non omogenee. Le nuove potenzialità sono state 
opportunamente evidenziate, implementando in C++, l'algoritmo di Martelli-
Montanari per l'unificazione di termini nella logica del primo ordine. 
Si è così iniziato un lavoro che dovrebbe portare all'immersione del linguaggio 
Set12 nel C++ (con LEDA naturalmente).  
L'eleganza e la facilità d'uso del sistema LEDA risultano essere sicuramente non 
inferiori a quelli del linguaggio Setl2, i problemi di inefficienza di quest 'ultimo 
vengono però ovviati grazie alle librerie precompilate di LEDA. Per finire 
soffermeremo la nostra attenzione su alcuni interessanti programmi, con il preciso 
intento di evidenziare l'estrema facilità con cui sia possibile realizzare, con 
LEDA, l'interfaccia grafica degli stessi. 
Capitolo 1 
Il sistema L.E.D.A.: 
Overview 
 
1.1 Che cosa è LEDA. 
L.E.D.A., acronimo di Library of Efficient Data Types and Alghorithms, è una 
libreria software scritta in C++ contenente tipi di dati e algoritmi di geometria 
computazionale e calcolo combinatorico. 
Questo sistema, sviluppato a Saarbrucken in Germania, presso il Max Planck 
Institute fur Infurmatik, dal gruppo di ricerca dei proff. Kurth Mehlhorn e Stefhan 
Naher, è nato nel 1989 ed è tuttora in fase di continuo sviluppo. Come noto, 
purtroppo non esistono librerie standard per il calcolo combinatorico e per la 
geometria computazionale, così come invece avviene per altre branche della 
cosiddetta Computing Area. Diversi packages (LINPACK, EISPACK, SPSS, 
CPLEX, ..:) vengono infatti sfruttati appieno in statistica, in analisi numerica, 
nella programmazione lineare, ecc. .Questo stato di cose è dovuto alla continua 
reimplementazione di strutture dati di base e di algoritmi che fra le altre cose 
rallenta inevitabilmente la ricerca. 
D'altra parte, difficilmente al di fuori delle stesse ricerche, si adoprano 
investimenti per trovare soluzioni più efficienti, semplicemente perche a priori 
non è detto che l'implementazione in questione venga riutilizzata in futuro. 
La situazione paradossale che ne nasce fa sì che le scoperte scientifiche vengano 
recepite molto lentamente. Spesso quindi sono utilizzati in pratica metodi meno 
efficienti di quelli conosciuti. Solo con l'avvento della programmazione ad oggetti 
si è cominciato a parlare in maniera più seria di riutilizzo del software anche 
qell'ambito del calcolo combinatorico dove come noto si utilizzano complesse 
strutture dati (alberi, grafi, insiemi, ...). Grazie alla O.O.P.(Object Oriented 
Programming) ogni struttura dati può diventare un tipo di dati vero e proprio. 
 LEDA sfrutta appieno questa possibilità; in questo modo applicazioni anche 
complesse possono essere realizzate concentrandosi solo sul nocciolo del 
problema in questione, senza doversi preoccupare di implementare le strutture 
dati di base che fra l'altro nel sistema LEDA sono realizzate utilizzando le 
tecniche più efficienti conosciute. In alcuni casi l'utente può addirittura scegliere 
tra differenti implementazioni.  
LEDA rappresenta quindi il tentativo di co1Inare il gap oggi esistente tra ricerca, 
insegnamento, ed implementazione effettiva di strutture dati e algoritmi. 
Prima di entrare nei dettagli del sistema specificandone le modalità di 
installazione, la struttura interna, le possibili applicazioni ed estensioni 
esaminiamone brevemente le caratteristiche generali: 
- LEDA fornisce una vasta collezione di tipi di dati e algoritmi facilmente 
utilizzabili anche dai cosiddetti beginners. Sono presenti la maggior parte 
delle strutture dati e degli algoritmi trattati nella letteratura specifica. 
- Per ciascun tipo di dato e algoritmo, LEDA specifica una breve ma chiara 
introduzione di base, che allo stesso tempo risulta essere generale ed astratta. 
L'astrazione consente di distinguere nettamente il tipo di dato astratto e la 
struttura dati utilizzata per implementarlo. Questa distinzione spesso non 
viene considerata nella letteratura mentre è invece di fondamentale 
importanza nello sviluppo e/o utilizzo di una libreria. D'altra parte la 
generalità consente di considerare le varie implementazioni possibili. Tutti i 
tipi di dati sono infatti realizzati utilizzando i metodi asitonticamente migliori 
a tutt'oggi conosciuti. E' noto però che nella pratica, lavorando con input di 
grandezza relativamente piccola, può benissimo capitare che la migliore 
efficienza, cioe il più basso running-time, si raggiunga sfruttando 
un'implementazione diversa da quella asintoticamente migliore. 
- Molti tipi di dati sono parametrizzati, il che significa che possono essere 
utilizzati con un qualunque altro tipo di dati sia per quanto riguarda 
l'informazione specifica sia per quanto riguarda l'eventuale key. Nasce così la 
possibilità di dare vita a strutture dati molto complesse nella maniera più 
naturale. 
- Per motivi di efficienza è spesso necessario accedere per posizione alle varie 
strutture. dati. È stato introdotto allora il concetto di item. 
- La realizzazione di funzionali interfacce grafiche è facilitata da opportune 
primitive che consentono di generare finestre, bottoni e pannelli interattivi 
senza particolari difficoltà implementative. È anche possibile rappresentare 
graficamente i tipi di dati LEDA presenti nella libreria geometrica (quali 
segmenti, punti, linee, ...). Ciò è realizzato, almeno per quanto riguarda il 
sistema operativo UN IX, interfacciando il linguaggio C++ con le librerie 
grafiche XII. 
- Notevolmente efficace poi è l'interfaccia del tipo di dato grafo. Sono previste 
infatti, oltre alle primitive di iterazione standard (per ogni arco (w, v), per 
ogni nodo(v,G), ..) altre primitive molto potenti quali la cancellazione o 
l'inserimento di nuovi archi e/o nodi, insieme ad innumerevoli altre funzioni 
che permettono di scrivere programmi sui grafi in una forma del tutto analoga 
a una tipica presentazione di un algoritmo di un qualsiasi libro di testo. 
- LEDA è realizzato come già detto in C++ (supporta molti compilatori anche 
se con qualche problema), in particolare tutti i tipi di dati sono implementati 
come classi. È quindi richiesta agli utenti una certa familiarità con il 
linguaggio, che permetta loro di interagire al meglio con il sistema. Sia i tipi 
di dati che gli algoritmi sono immagazzinati in librerie precompilate al 
momento dell'installazione del sistema che devono solo essere linkate 
all’applicazione. Ciò insieme alla potenza espressiva propria di LEDA riduce 
notevolmente sia i tempi di compilazione che la lunghezza del codice 
prodotto. 
- Sfruttando appieno le caratteristiche del C++, LEDA si presta bene ad essere 
esteso con l'aggiunta di nuovi tipi di dati e nuovi algoritmi. Come vedremo 
più avanti, ciò si realizza o aggiungendo nuove funzioni membro alla classe 
corrispondente al tipo di dato in questione, o creando apposite classi C++ che, 
sfruttando i meccanismi di ereditarietà tipici della programmazione a oggetti, 
implementino tipi di dati user-defined. Per quanto riguarda poi le applicazioni 
specifiche del sistema LEDA esse abbracciano diverse aree della 
computazione quali ad esempio: machine learning, scheduling, VLSI, 
geometria computazionale, ... 
Le seguenti pubblicazioni esemplificano l'uso di LEDA in vari domini: 
- K. Melhorn, S. Naher - An implementation of the Hopcroft and Tarjan 
Planarity Test and Embedd'ing Algorithm - MPI-I-93-151, Ottobre 1993. 
- Michael Muller, Joachim Ziegler - An implementation of a Convex Hull 
Algorithm - MPI-I-94-105, Febbraio 1994. 
- K. Melhorn, S. Naher - The implementation of Geometric Algorithms - 
Aprile 1994. 
-  K. Melhorn, S. N aher -LEDA - A platform for Combinatorial and 
Geometric Computing - 
- K. Melhorn, Christian Uhrig - The Mincut Algorithm of Stoer and Wagner - 
Dicembre 1994. 
 
1.2 Dove trovare LEDA. 
Il sistema, tuttora in via di sviluppo (attualmente la versione più recente è la 3.1.2 
ma è già allo studio la versione 3.2), è disponibile mediante anonymous ftp 
all'indirizzo: ftp.mpi-sb.mpg.de nella directory: /pub/LEDA.  
A tal proposito elenchiamo i files che contengono LEDA con accanto il sistema 
operativo cui sono destinati non che il tipo di compressione utilizzata: 
 - LEDA-(version).tgz  UNIX (tar + gzip ); 
 - LEDA-(version).tar.z  UNIX (tar + compress); 
 - LEDA-(version).zip  MsDos (zip). 
 
E possibile anche consultare gli articoli pubblicati nonche una versione postscript 
del manuale LEDA. Da poco tempo poi è a disposizione un server WWW 
all'indirizzo: http://www.mpi-sb.mpg.de/LEDA/leda.html. Fra non molto sarà poi 
reso pubblico anche il file FAQ (Frequently Asked Questions) che conterrà 
appunto le risposte alle domande più frequenti poste dagli utenti LEDA. Per 
maggiori informazioni è possibile contattare direttamente il gruppo di lavoro 
scrivendo all'indirizzo: [email protected]. LEDA non è di pubblico dominio 
ma può essere usato liberamente per scopi didattici e/o scientifici. In ogni caso è 
disponibile una licenza commerciale. 
Capitolo 2 
L'installazione 
 
2.1 Primi passi. 
La decompressione del file LEDA-(version) provoca la creazione di una serie di 
sottodirectory: 
- incl/ 
 LEDA include directory. Contiene tutti i file header del sistema. 
- src/ 
 Files sorgenti LEDA. 
- prog/ 
 Programmi con esempi. In particolare sono presenti una serie di demo che 
illustrano le potenzialità del sistema nei vari campi di applicazione. 
- web/ 
 Sorgenti cweb. 
- man/ 
 Manuale utente (formato TeX). E disponibile una versione interattiva che 
fornisce, a richiesta, tutte le informazioni riguardo anche solo un particolare tipo 
di dato. 
- util/ 
 Utility varie. 
 
La directory principale contiene anche i seguenti files: 
 
- README 
 Breve introduzione integrata con alcune informazioni di base su LEDA. 
- INSTALL 
 Procedure d'installazione. 
 
- Changes 
 Cambiamenti più recenti rispetto alle versioni LEDA precedenti. 
 
- Fixes 
 Bugs corretti dall'ultima versione. 
 
- Makefile 
Make script grazie al quale il sistema procede alla compilazione dei sorgenti 
LEDA e alla creazione delle apposite librerie. 
 
- COMPILERS 
Problemi noti con alcuni compilatori. Il sistema infatti, nonostante possa essere 
utilizzato con la maggior parte dei compilatori C++ oggi !esistenti ( quali cfront, 
gcc, sunpro, watcom, emx, bcc, ztc), richiede che in alcuni casi particolari, si 
proceda all'espletamento di specifiche procedure alternative, che possono 
riguardare sia la fase d'installazione, sia le fasi successive più propriamente legate 
all'utilizzo dello stesso sistema. 
 
Per installare LEDA è innanzitutto necessario conoscere il tipo di macchina su cui 
si lavora non che versione e tipo del compilatore C++ che si utilizza. La versione 
attuale di LEDA supporta, a differenza di quelle precedenti, quasi tutti i sistemi 
operativi ( esistono delle particolari versioni commerciali che girano ad esmpio 
anche su OS/2 e Windows). È consigliabile utilizzare compilatori di recente 
realizzazione, o comunque non molto vecchi, che supportino i costrutti relativi ai 
template, grazie ai quali viene realizzata la parametrizzazione dei dati in LEDA. I 
template, infatti permettono di realizzare funzioni e classi senza fare riferimento a 
un particolare tipo. Ciò significa che è possibile realizzare operazioni astratte che 
saranno valide comunque, indipendentemente dal tipo con il quale si 
realizzeranno le applicazioni. Si può quindi procedere alla consultazione del file 
testo COMPILERS che fornisce utili indicazioni, circa gli eventuali problemi 
associati al compilatore che si intende utilizzare. 
 
2.2 Nostra esperienza 
Per 1 'installazione sulle Workstation HP, si è fatto uso del compilatore gcc-2.6.3 
della GNU (Free software). Si è dovuto necessariamente modificare nel file .cshrc 
l'ordine dei vari path; affinche tutto proceda bene /usr/local/bin deve precedere 
/usr e /usr/bin. Senza questo accorgimento, il sistema operativo, durante la 
compilazione (Gcc) di un qualsiasi programma, troverebbe l'assemblatore del 
linguaggio C di Unix anziche quello proprio. Così come riportato nel file 
INSTALL, è necessario effettuare un link simbolico per i file g++ e gcc. È poi 
sufficiente posizionarsi nella directory LEDA-(version) e digitare make. Grazie a 
una serie di makefiles collegati tra loro in maniera opportuna vengono create le 4 
librerie LEDA: libP.a, libG.a, libL.a, libWx.a.  
Nel nostro caso però la libreria lib Wx.a, non è stata inizialmente creata, in quanto 
le librerie XII richieste per la compilazione, non si trovavano nel path di default 
dei makefile LEDA. Si è quindi dovuto procedere alla modifica di qualche 
makefile, indicando esplicitamente, grazie ad opportune opzioni di compilazione, 
il giusto path sia per i file da includere, sia per la libreria libXll.a. 
Dopo la creazione delle librerie si può, o procedere alla loro installazione nelle 
apposite directory di sistema (Bisogna rivolgersi al superuser), o altrimenti 
utilizzare in fase di compilazione, rispettivamente le opzioni -I e -L seguite da un 
opportuno path che indichi al compilatore dove andare a reperire i file .h e le 
librerie. 
Come già accennato, nella directory prog sono presenti numerosi sorgenti relativi 
a programmi dimostrativi. Anche in questo caso si può procedere alla 
compilazione degli stessi grazie ad un apposito makefile. Mentre però la 
creazione delle librerie è stata portata a tennine in poco tempo, questa fase ha 
richiesto circa 2-3 ore di elaborazione. 
Per finire, accenniamo brevemente alle risorse fisiche necessarie, con particolare 
riguardo allo spazio fisico occupato dal sistema LEDA. Se, come del resto è 
naturale che si faccia, si procede alla compilazione dei sorgenti dimostrativi, 
l'intero sistema occupa circa 200MB. Caratteristico infatti dei programmi LEDA, 
e ciò vale in particolare per quelli che utilizzano funzioni grafiche, è il notevole 
spazio occupato dai corrispondenti files oggetto e dagli eseguibili. 
Capitolo 3 
Concetti di base 
 
3.1 Implementazione dei tipi di dati 
Come già accennato LEDA è scritto in C++ (cfr.[St91]), linguaggio che come 
noto estende le potenzialità del C grazie alle caratteristiche proprie dei linguaggi 
Object Oriented: 
- Astrazione sui dati. 
- Overloading degli operatori. 
- Encapsulation. 
- Polimorfismo. 
- Ereditarietà. 
- Parametrizzazione dei dati (Template). 
 
La conoscenza specifica del linguaggio non è indispensabile anche se è 
fortemente consigliata soprattutto nei casi in cui ci si propone di realizzare 
applicazioni più particolari, come ad esempio l'estensione o la realizzazione di 
tipi di dati astratti, o quando si è interessati allo studio dei dettagli implementativi 
del sistema. 
In ogni caso riteniamo opportuno sottolineare che tutti i compilatori C++ 
supportano integralmente il linguaggio C. È quindi possibile avvicinarsi 
gradualmente al C++, tenendo comunque presente che per poter riuscire a 
programmare nell 'ambito della programmazione ad oggetti, sfruttandone appieno 
tutte le peculiadtà intrinseche, si deve necessariamente fare uso di una nuova 
filosofia di programmazione. 
Ogni tipo di dati in LEDA è implementato come una classe C++. Una classe 
comprende un insieme di dati ed una collezione di funzioni che possono essere 
applicate a quei dati. Queste funzioni, dette funzioni membro, vengono utilizzate 
per realizzare le operazioni opportune su un 'istanza del corrispondente tipo di 
dati. L'usuale sintassi utilizzata per individuare i campi di una struttura di tipo 
record è poi usata per invocare tali funzioni. 
Ad esempio se D è una classe con funzione membro f() allora D.f() chiama la f su 
D. Questa sintassi estremamente semplice fa sì che algoritmi anche molto 
complessi possano essere implementati in maniera semplice. Sottolineiamo 
inoltre che un programma scritto con l'ausilio di LEDA può essere facilmente 
compreso anche da chi non conosce tale sistema, e questo perche tutti i comandi e 
le dichiarazioni dei tipi di dati seguono il significato più ovvio. 
 
3.2 Descrizione dei tipi 
Per ogni tipo di dato il LEDA manual (cfr.[Nah95]) fornisce una dettagliata 
descrizione che comprende innanzitutto una definizione dell 'insieme di oggetti 
costituenti il tipo di dato astratto ( ed eventualmente parametrizzato), che utilizza 
notazione e concetti tipici della matematica standard. Successivamente si passa a 
descrivere come creare un oggetto di un dato tipo (possono infatti esserci diverse 
alternative). Una variabile di un dato tipo è introdotta mediante una tipica 
dichiarazione C++. Volendo ad esempio utilizzare una variabile di tipo window e 
una di tipo point cui associare rispettivamente i nomi A e B, basterà 
semplicemente dichiarare: 
 
window A; 
point E; 
 
L'inizializzazione delle variabili avviene proprio al momento della dichiarazione. 
Sarà 1'utente a decidere, grazie al classico meccanismo dei parametri di default, 
se settare o meno la variabile appena dichiarata con valori diversi a quelli 
altrimenti forniti automaticamente. 
Un cenno a parte meritano i tipi di dati parametrizzati. L'utilizzo dei templates, 
che come già accennato permette la generalizzazione dei tipi di ati astratti 
disponibili, richiede che al momento della dichiarazione, subito dopo il nome del 
tipo, vengano elencati tra brackets (<...>) i particolari tipi di dati cui fare 
riferimento nella specifica applicazione.