Algorithm Design and Engineering Group

Department of Computer and System Sciences, University of Rome "La Sapienza"

Software systems and libraries

Software systems

Leonardo IDE, a C programming environment for reversible execution and software visualization
Leonardo is an integrated environment for developing, executing, and visualizing C programs. It provides two major improvements over a traditional IDE. First, it provides a mechanism for visualizing computations graphically as they happen by attaching in a declarative style graphical representations to key variables in a program. As a second main feature, Leonardo includes the first run-time environment that supports fully reversible execution of C programs. The system is distributed with a collection of animations of more than 60 algorithms and data structures including approximation, combinatorial optimization, computational geometry, on-line and dynamic algorithms. Leonardo has been widely distributed on CD-ROM in computer magazines and is available for download in several software archives over the Web. It has received several technical reviews and thousands of downloads.

The Leonardo Virtual Machine (LVM)
A general-purpose multi-programmed runtime environment for program analysis, visualization, and debugging

Leonardo Web
A collection of tools for visualizing over the Web

Estimation of the number of vertices at distance k from all vertices of the graph
This software implements probabilistic counting and propagation of bit vectors to estimate the number of vertices at distance k from all the vertices of a graph.
This software has been used to count the number of so-called supporters of a page in the Webgraph. Detection of anomalies in the number of supporters at distance 1,2,3,.. is used for Web spam detection in [BeCaDo06-2] L. Becchetti, C. Castillo, D. Donato, S. Leonardi and R. Baeza-Yates. Using Rank Propagation and Probabilistic Counting for Link-Based Spam Detection. In Proceedings of the Workshop on Web Mining and Web Usage Analysis (WebKDD06), 2006..

Libraries and experimental packages

Two-Layer Crossing Problem
Experimental C platform for testing approximation algorithms for the Two-Layer Crossing Problem.

Fully Dynamic All-Pairs Shortest Paths
Experimental C platform for testing Fully Dynamic All-Pairs Shortest Paths algorithms on directed graphs.

Fully Dynamic Single-source Shortest Paths
Experimental C++ (based on LEDA) platform for testing Fully Dynamic Single-source Shortest Paths algorithms on directed graphs with negative and non-negative edge weights

The Leonardo Library (LL)
A cross-platform, open-source C toolkit for program development.

A library for measuring and generating large Webgraphs
A set of software tools for large scale simulation of stochastic models for the Webgraph and for measuring very large graphs stored on secondary memory. The available tools allow to measure degree distribution, dense subgraphs, Page Rank, strongly connected components, bow-tie structure, etc...

Counting subgraphs in large networks
This software provides the implementation of a set of algorithms for approximating the number of all the subgraphs of three and four nodes in both directed and undirected graphs. The software has been used for clustering and classifying different families of networks in "Mining large networks with subgraph counting "(I. Bordino, D. Donato, A. Gionis, and S. Leonardi, in Proceedings of the Eighth IEEE International Conference on Data Mining (ICDM 2008), pp. 737-742, 2008. ). Datasets are also made available.

Set operations for labeled graphs
This software extends the WebGraph(http://webgraph.dsi.unimi.it) framework by providing the implementation of a number of set operations that can be used to combine graphs represented in the compressed WebGraph format. The graphs are intended to be labeled on nodes and edges. Datasets are also made available.

Webmaster

Software systems
Leonardo IDE, a C programming environment for reversible execution and software visualization Leonardo is an integrated environment for developing, executing, and visualizing C programs. It provides two major improvements over a traditional IDE. First, it provides a mechanism for visualizing computations graphically as they happen by attaching in a declarative style graphical representations to key variables in a program. As a second main feature, Leonardo includes the first run-time environment that supports fully reversible execution of C programs. The system is distributed with a collection of animations of more than 60 algorithms and data structures including approximation, combinatorial optimization, computational geometry, on-line and dynamic algorithms. Leonardo has been widely distributed on CD-ROM in computer magazines and is available for download in several software archives over the Web. It has received several technical reviews and thousands of downloads.
The Leonardo Virtual Machine (LVM) A general-purpose multi-programmed runtime environment for program analysis, visualization, and debugging
Leonardo Web A collection of tools for visualizing over the Web
Estimation of the number of vertices at distance k from all vertices of the graph This software implements probabilistic counting and propagation of bit vectors to estimate the number of vertices at distance k from all the vertices of a graph. This software has been used to count the number of so-called supporters of a page in the Webgraph. Detection of anomalies in the number of supporters at distance 1,2,3,.. is used for Web spam detection in [BeCaDo06-2] L. Becchetti, C. Castillo, D. Donato, S. Leonardi and R. Baeza-Yates. Using Rank Propagation and Probabilistic Counting for Link-Based Spam Detection. In Proceedings of the Workshop on Web Mining and Web Usage Analysis (WebKDD06), 2006..

Libraries and experimental packages
Two-Layer Crossing Problem Experimental C platform for testing approximation algorithms for the Two-Layer Crossing Problem.
Fully Dynamic All-Pairs Shortest Paths Experimental C platform for testing Fully Dynamic All-Pairs Shortest Paths algorithms on directed graphs.
Fully Dynamic Single-source Shortest Paths Experimental C++ (based on LEDA) platform for testing Fully Dynamic Single-source Shortest Paths algorithms on directed graphs with negative and non-negative edge weights
The Leonardo Library (LL) A cross-platform, open-source C toolkit for program development.
A library for measuring and generating large Webgraphs A set of software tools for large scale simulation of stochastic models for the Webgraph and for measuring very large graphs stored on secondary memory. The available tools allow to measure degree distribution, dense subgraphs, Page Rank, strongly connected components, bow-tie structure, etc...
Counting subgraphs in large networks This software provides the implementation of a set of algorithms for approximating the number of all the subgraphs of three and four nodes in both directed and undirected graphs. The software has been used for clustering and classifying different families of networks in "Mining large networks with subgraph counting "(I. Bordino, D. Donato, A. Gionis, and S. Leonardi, in Proceedings of the Eighth IEEE International Conference on Data Mining (ICDM 2008), pp. 737-742, 2008. ). Datasets are also made available.
Set operations for labeled graphs This software extends the WebGraph(http://webgraph.dsi.unimi.it) framework by providing the implementation of a number of set operations that can be used to combine graphs represented in the compressed WebGraph format. The graphs are intended to be labeled on nodes and edges. Datasets are also made available.