TABLE OF CONTENTS (H)

LASAGNE USER GUIDE

Running LASAGNE

Assume you have downloaded the file lasagne_x_y.jar into the directory $HOME. In order to execute the application, you simply have to double click on this file. If a directory called NETWORKS does not exists in the directory $HOME, then it will be created the first time LASAGNE is run: this is the directory where the application will look for graphs to be analyzed.

The LASAGNE interface

The LASAGNE Graphical User Interface (in short, GUI) is shown in Figure 1.
LASAGNE GUI
Figure 1: The LASAGNE GUI.
This interface is basically split into the following five parts.
  • Tree file browser. This is the tree depicted in the left panel of the interface. It allows to navigate within the NETWORKS directory.
  • File table. This table shows all the graph files contained in the directory currently selected in the tree file browser. Only files whose name ends with .nde are shown in this table: it is assumed that any such file contains the description of a graph in the NDE format (see the appendix).
  • Toolbar. This set of buttons allows the user to perform all available operations (see below). Each button has associated a tooltip, which appears whenever the user hovers the mouse over the button, without clicking it.
  • Graph information panel. In this panel, basic information about the currently loaded graph and its associated file are shown. The diameter value is shown when either the exhaustive method or the iFUB method has been executed (see below).
  • Console. In this text area some information messages are shown concerning the executed operations and their results (in the figure, for example, the messages by producing the execution of the computation of the diameter via the exhaustive method).
We now describe each of the operations available in the toolbar.
LASAGNE information window
Figure 2: The LASAGNE information window.

The about button

By clicking the button, the user can obtain some information concerning the LASAGNE application (see Figure 2). In particular, LASAGNE makes use of the following three Java binary libraries.
  • The Apache log4j library (version 1.2.16) which enables logging at runtime.
  • The Apache Commons CLI library (version 1.2) which provides an API for parsing command line options passed to programs.
  • The GRAL library (version 0.8) which provides tools for displaying plots (graphs, diagrams, and charts).
Apart from standard graph algorithms (such as breadth-first search, Dijkstra, and Tarjan algorithms), LASAGNE implements the algorithms described in our papers (see the Publications page). If you use LASAGNE in your research, it would be nice if you cite the corresponding paper(s).

The new folder button

This button allows the user to create a new sub-directory of the directory currently selected in the tree file browser. If no directory is currently selected, then a warning message is shown. Otherwise the user is asked to specify the name of the new sub-directory: if a sub-directory with the same name is already contained in the current directory, then a warning message is shown.

Figure 3: Specifying the URL of a file to be downloaded.

The download button

This button allows the user to download a file from the web and to save it in the directory currently selected in the tree file browser. If no directory is currently selected, then a warning message is shown. Otherwise the user is asked to specify the URL of the file (see Figure 3): this URL has to end either with .nde or with the .zip suffix (in the latter case, the file is assumed to be a zipped NDE file, and it will be automatically unzipped before being saved in the currently selected directory). Note the dialog window asking to specify the URL of the file allows the user to paste into the text area the content of the clipboard: this might turn out to be a useful feature when dealing with long URLs.

The open button

This button allows the user to open the file currently selected in the file table. If no file is currently selected, then a warning message is shown. Otherwise a progress dialog is shown until the entire file has been read and the corresponding graph stored in memory. Some basic information about the opened graph are, in this case, shown in the graph information panel. If the graph is too big it may happen that a warning message is shown, suggesting to increase the heap size of the Java Virtual Machine: in this case, it is necessary to execute LASAGNE from the terminal (see the appendix).

The (strongly) connected component button

This button allows the user to compute the maximum (strongly) connected component of the currently opened graph. If no graph is currently open, then a warning message is shown. Otherwise the user is warned about the fact that the NDE file corresponding to the maximum (strongly) connected component of the currently opened graph will be created: the name of this file is obtained from the name of the file corresponding to the currently opened graph, by adding the string -mcc just before the suffix .nde. If the graph is too big it may happen that a warning message is shown, suggesting to increase the stack size of the Java Virtual Machine: in this case, it is necessary to execute LASAGNE from the terminal (see below).

The file delete button

This button allows the user to delete the file currently selected in the file table. If no file is currently selected, then a warning message is shown. Otherwise a confirmation dialog is shown: if the user confirms the operation, then the file is deleted.

The folder delete button

This button allows the user to delete the non-root directory currently selected in the tree file browser with all its contents. If no directory is currently selected or if the currently selected directory is the root NETWORKS directory, then a warning message is shown. Otherwise a confirmation dialog is shown: if the user confirms the operation, then the directory (with all its contents) is deleted.

The diameter button

This button allows the user to compute the diameter of the currently opened graph. If no graph is currently open, then a warning message is shown. Otherwise a progress dialog is shown (see left part of Figure 4) until the diameter is computed and its value shown in the graph information panel. The diameter is 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 FUB methods are much more efficient), we decided to include it in the application in order to appreciate the advantage of using the FUB methods with respect to using the text-book exhaustive method.
Diameter computation4-sweep computation
Figure 4: Computing the diameter (left) and the 4-SWEEP lower bound (right).

The 4-sweep button

This button allows the user to compute a lower bound of the diameter of the currently opened graph, by making use of the 4-SWEEP method. If no graph is currently open, then a warning message is shown. Otherwise the user is asked to specify how many runs the 4-SWEEP method has to be executed: the largest lower bound will be reported on the console at the end of the executions. During the executions, a progress dialog is shown (see the right part of Figure 4). 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.

The iFUB button

This button allows the user to compute the diameter of the currently opened graph, by making use of the iFUB methods. If no graph is currently open, then a warning message is shown. Otherwise the user is asked to specify how many runs the appropriate iFUB method has to be executed: the value of the diameter and the average number of either breadth-first searches or Dijkstra algorithm executions will be reported on the console at the end of the executions. During the executions, a progress dialog is shown (see the left part of Figure 5). Note that it is not necessary to execute the iFUB methods more than one time, since the value reported by these methods is always the exact value: however, it might be interesting to evaluate the average number of visits that these methods require on specific graphs.
Running iFUBRunning EW
Figure 1.5: Executing the iFUB (left) and the Eppstein-Wang (right) methods.

The distance distribution button

This button allows the user to compute the distance distribution of the currently opened graph, by making use of the sample-based Eppstein-Wang method. If no graph is currently open, then a warning message is shown. Otherwise the user is asked to specify the value of a constant k > 0: the size of the node sample is equal to k×logn, where n denotes the number of nodes of the graph. During the execution, a progress dialog is shown (see the right part of Figure 5). At the end of the execution, the values of the distance distribution are shown on the console and the distribution itself is graphically shown in a new window (see Figure 6).

Figure 6: Graphical representation of the distance distribution of a network.

The console activation button

LASAGNE implements two different loggers. One logger write all produced messages in the file called lasagne.log (which is created at the same level of the NETWORKS directory). The second logger write a subset of the produced messages on the console. This button allows the user to see or to not see all the produced messages on the console. In particular, when the button icon is an empty sheet, then only a subset of the messages will be shown on the console, while when the button icon is a full sheet, then all messages will be shown on the console.

The console erase button

This button allows the user to clean the console. A confirmation dialog is shown: if the user confirms the operation, then all the contents of the console will be deleted.

The logger activation button

This button allows the user to log or to not log all the produced messages in the file called lasagne.log (which is created at the same level of the NETWORKS directory).

Running LASAGNE from the terminal

LASAGNE can also be run from the terminal. To this aim, the user has to open a terminal, to set the current directory to the one containing the file lasagne_x_y.jar, and to type the following command:
java -jar lasagne_x_y.jar
By using the Java Virtual Machine arguments, the user can run LASAGNE with either a greater heap or a greater stack. For example, the command
java -Xms1024M -Xmx2048M -Xss128000K -jar lasagne_x_y.jar
will execute LASAGNE 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.

Running LASAGNE without the GUI

LASAGNE can also be run from the terminal without the GUI. To this aim, the user can open a terminal, set the current directory to the one containing the file lasagne_x_y.jar, and type the command
java -jar lasagne_x_y.jar -h
The following help message will be shown:
usage: OptionsTip
 -dd <<file> <k>>     Execute the EW method on file klog(n) times
 -h                   Print the help message
 -ifub <<file> <e>>   Execute iFUB on file k times
 -v                   Activate the full logging of the execution
By choosing the appropriate option and by specifying the required parameters the user can execute directly the iFUB methods and the Eppstein-Wang method on a specific file (which has not necessarily to be in the NETWORKS directory).

Appendix

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.

Figure 7: A directed graph.
For example, the directed (unweighted) graph shown in Figure 7 woulde be specified by the following NDE file (note that the indices of the nodes must start from 0).
9 1 0
0 3 3
1 2 1
2 2 2
3 2 3
4 2 2
5 1 1
6 2 2
7 2 3
8 2 1
0 2
0 4
1 0
1 3
2 1
2 6
3 6
3 0
4 2
4 8
5 3
6 5
6 7
7 4
8 7
8 3

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 libraries.
  • commons-cli-1.2.jar
    • Downloadable from http://commons.apache.org/cli/
  • GRAL-0.8-jar-with-dependencies.jar
    • Downloadable from http://trac.erichseifert.de/gral/
  • log4j-1.2.16.jar
    • Downloadable from http://logging.apache.org/log4j/1.2/