### Running LASAGNE

Assume you have downloaded the file `lasagnex_y.jar` into the directory `$HOME` (from now on, we will refer to the version 1_1). In order to execute the application, you have to open a console, go to the the directory `$HOME`, and type the following command

java -jar lasagne1_1.jar

The following usage message should be printed on the console

usage: java -jar lasagne1_1.jar -4sweep <<file> <r>> Execute 4-sweep on file r times -all <<file>> Execute LCC and iFUB on file -dd <<file> <k>> Execute the EW method on file klog(n) times -diam <<file>> Compute diameter of file by executing all visits -h Print the help message -i Print info about the software -ifub <<file>> Execute iFUB starting from highest degree node -lcc <<file>> Compute and save largest (strongly) connected component of file

For example, if you type the following command

java -jar lasagne1_1.jar -i

the following information message will be printed on the console

LASAGNE is currently maintained by Pierluigi Crescenzi (contact developer: pierluigi.crescenzi@unifi.it) Roberto Grossi Leonardo Lanzi Andrea Marino LASAGNE implements algorithms described in: P. Crescenzi, R. Grossi, C. Imbrenda, L. Lanzi, A. Marino Finding the Diameter in Real-World Graphs. Experimentally Turning a Lower Bound into an Upper Bound ESA 2010: 302-313 P. Crescenzi, R. Grossi, L. Lanzi, A. Marino A Comparison of Three Algorithms for Approximating the Distance Distribution in Real-World Graphs TAPAS 2011: 92-103 P. Crescenzi, R. Grossi, M. Habib, L. Lanzi, A. Marino On Computing the Diameter of Real-World Undirected Graphs Theoretical Computer Science, 514, 84-95 (2013) P. Crescenzi, R. Grossi, L. Lanzi, A. Marino On Computing the Diameter of Real-World Directed (Weighted) Graphs SEA 2012: 99-110 If you use LASAGNE, please cite the corresponding paper(s).

### Extracting the largest connected component of a graph

Assume that in the directory `$HOME` you also have the file `advogato.nde`, which corresponds to a collaboration network (available on this web site). If you type the following command

java -jar lasagne1_1.jar -lcc advogato.nde

the following messages will be printed on the console

Graph file: advogato.nde (481379 bytes) Number of nodes: 7420 Number of edges: 48037 Oriented: false Weighted: false advogato-mcc.nde Number of CC: 2074 Size of LCC: 5272 LCC file: advogato-mcc.nde

The NDE file corresponding to the largest (strongly) connected component of the input graph has been be created: the name of this file is obtained from the name of the file corresponding to the input graph, by adding the string `-mcc` just before the suffix `.nde` (in our case, the file `advogato-mcc.nde` has been created).

### Computing the diameter (text-book method)

If you type the following command (note that we are now using the largest connected component)

java -jar lasagne1_1.jar -diam advogato-mcc.nde

the following messages will be printed on the console

Graph file: advogato-mcc.nde (499045 bytes) Number of nodes: 5272 Number of edges: 45903 Oriented: false Weighted: false Diameter is 9

The diameter of the input graph has been computed by executing the breadth-first search or the Dijkstra algorithm starting from each node of the graph: this operation can thus take quite a long time. Even though this operation is not really necessary (since the iFUB methods are much more efficient), we decided to include it in the application in order to appreciate the advantage of using the iFUB methods with respect to using the text-book exhaustive method.

### Computing a lower bound of the diameter (the 4-sweep method)

If you type the following command (note that now there are two parameters)

java -jar lasagne1_1.jar -4sweep advogato-mcc.nde 5

the following messages (or similar ones) will be printed on the console

Number of nodes: 5272 Number of edges: 45903 Oriented: false Weighted: false Lower bound is 9 at iteration 0 Lower bound is 9 at iteration 1 Lower bound is 9 at iteration 2 Lower bound is 9 at iteration 3 Lower bound is 9 at iteration 4 Lower bound is 9

A lower bound of the diameter of the input graph has been computed by making use of the 4-SWEEP method, which is repeated as many times as the value of the second parameter. The largest lower bound will be reported on the console at the end of the executions. Even if the 4-SWEEP method has been experimentally shown to be very effective, the user should be aware that the reported value is a lower bound which not necessarily coincides with the exact value of diameter.

### Computing the diameter (iFUB method)

If you type the following command (note that there are two parameters)

java -jar lasagne1_1.jar -ifub advogato-mcc.nde

the following messages (or similar ones) will be printed on the console

Graph file: advogato-mcc.nde (499045 bytes) Number of nodes: 5272 Number of edges: 45903 Oriented: false Weighted: false Diameter is 9 Number of BFSes: 2

The diameter of the input graph has been computed by executing the iFUB method, starting from the node with highest degree. The value of the diameter and the number of breadth-first searches will be reported on the console at the end of the execution.

### Computing the largest connected component and the diameter (iFUB method)

If you type the following command (note that there are two parameters)

java -jar lasagne1_1.jar -all advogato.nde

both the computation of the largest connected component and the computation of the diameter (iFUB method) are executed (note that the file corresponding to the largest connected component is overwritten).

### Computing the distance distribution

If you type the following command (note that there are two parameters)

java -jar lasagne1_1.jar -dd advogato.nde 10 > advogato.dd

The distance distribution of the input graph is computed, by making use of the sample-based Eppstein-Wang method with the sample size equal to k×logn, where k is the value of the second parameter and n denotes the number of nodes in the graph. At the end of the execution, the values of the distance distribution are shown on the console: for this reason, it is better to redirect the output to a file (in our case, the file `advogato.dd`). Note that if k is equal to 0, then the exact distance distribution is computed by using a sample equal to the set of all nodes: this operation can thus take quite a long time but it can be used to evaluate the quality of the approximate distance distribution.

### Running LASAGNE with greater heap or stack

The user can run `LASAGNE` with either a greater heap or a greater stack. For example, the command

java -Xms1024M -Xmx2048M -Xss128000K -jar lasagne1_1.jar -dd advogato.nde 10 > advogato.dd

will execute distance distribution computation with a starting heap size equal to one gigabit, with a maximum heap size equal to 2 gigabits, and with a stack size equal to 128 megabits.

### The NDE format

A file specifying a graph in the NDE (Nodes-Degrees-Edges) format should contain the following information.

- One line containing the number of nodes and two 0/1 flags specifying whether the graph is directed and whether it is weighted, separated by one space.
- For each node, one line containing the index of the nodes, its outdegree and, if the graph is directed, its indegree, separated by one space.
- For each edge, one line containing the indices of its extremes and, if the graph is weighted, its weight, separated by one space.

### Using the source code in Eclipse

`LASAGNE` is an open-source project. Once an Eclipse project has been created, it suffices to substitute the empty `src` directory of the project with the `src` directory contained in the `LASAGNE` distribution and to include in the build path of the project the following library.

`commons-cli-1.2.jar`- Downloadable from
`http://commons.apache.org/cli/`

- Downloadable from