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/