Static Graph Statistics

Project for developing and demonstrating the computation of graph statistics on static graphs.

All commands below are assumed to be issued from the cloned git repository folder. For any issues with reproducing the experiments, please contact Giorgio Audrito.

References

• FCPP main website: https://fcpp.github.io.
• FCPP documentation: http://fcpp-doc.surge.sh.
• FCPP presentation paper: http://giorgio.audrito.info/static/fcpp.pdf.
• FCPP sources: https://github.com/fcpp/fcpp.

Setup

The next sections contain the setup instructions based on the CMake build system for the various supported OSs and virtual containers. Jump to the section dedicated to your system of choice and ignore the others.

Windows

Pre-requisites:

• MSYS2
• Asymptote (for building the plots)
• Doxygen (for building the documentation)

At this point, run "MSYS2 MinGW x64" from the start menu; a terminal will appear. Run the following commands:

pacman -Syu

After updating packages, the terminal will close. Open it again, and then type:

pacman -Sy --noconfirm --needed base-devel mingw-w64-x86_64-toolchain mingw-w64-x86_64-cmake mingw-w64-x86_64-make git

The build system should now be available from the "MSYS2 MinGW x64" terminal.

Linux

Pre-requisites:

• Xorg-dev package (X11)
• G++ 9 (or higher)
• CMake 3.18 (or higher)
• Asymptote (for building the plots)
• Doxygen (for building the documentation)

To install these packages in Ubuntu, type the following command:

sudo apt-get install xorg-dev g++ cmake asymptote doxygen

In Fedora, the xorg-dev package is not available. Instead, install the packages:

libX11-devel libXinerama-devel.x86_6 libXcursor-devel.x86_64 libXi-devel.x86_64 libXrandr-devel.x86_64 mesa-libGL-devel.x86_64

MacOS

Pre-requisites:

• Xcode Command Line Tools
• CMake 3.18 (or higher)
• Asymptote (for building the plots)
• Doxygen (for building the documentation)

To install them, assuming you have the brew package manager, type the following commands:

xcode-select --install
brew install cmake asymptote doxygen

Execution

Preprocessing

It is possible to download sample graphs from UniMI repo.

Assume you have donwloaded the cnr-2000 datasets and stored them under java/data of the present repo:

• cnr-2000.graph
• cnr-2000.properties
• cnr-2000.urls (after unzipping the downloaded archive)

You can use the HBApp java application by issueing the following Maven commands, from the java directory:

> mvn compile

just once for compiling, and then for executing:

> mvn exec:java -Dexec.mainClass="HBApp" -Dexec.args="<cmd> data/<basename>"

Where <basename> is the basename of the graph files (e.g., cnr-2000), and <cmd> is one of the following:

• conv to create a .graph-txt file to be further converted before being processed with FCPP (see below)
• enc to do the opposite
• stats to compute graph statistics with the system by Vigna et al.

Centrality Statistics

In order to execute the statistics computation, type the following command in a terminal:

> ./make.sh [gui] run -O [targets...] - [params]

You can omit the gui argument if you don't need the graphical user interface; or omit the -O argument for a debug build (instead of an optimised build). On newer Mac M1 computers, the -O argument may induce compilation errors: in that case, use the -O3 argument instead. The possible targets are:

• logical_batch (for computing the statistics on a graph in batch mode)
• logical_gui (for computing the statistics on a graph with the GUI)
• physical_gui (for computing the statistics on a simulated physical network with the GUI)

The logical_batch and logical_gui targets take as a parameter the basename of the graph files under input. Such files are named <basename>.nodes and <basename>.arcs.

Running the above command, you should see output about building the executables and running them, graphical simulations should pop up (if there are any in the targets), PDF plots should be produced in the plot/ directory (if any are produced by the targets), and the textual output will be saved in the output/ directory.

Graphical User Interface

Executing a graphical simulation will open a window displaying the simulation scenario, initially still: you can start running the simulation by pressing P (current simulated time is displayed in the bottom-left corner). While the simulation is running, network statistics may be periodically printed in the console, and be possibly aggregated in form of an Asymptote plot at simulation end. You can interact with the simulation through the following keys:

• Esc to end the simulation
• P to stop/resume
• O/I to speed-up/slow-down simulated time
• L to show/hide connection links between nodes
• G to show/hide the grid on the reference plane and node pins
• M enables/disables the marker for selecting nodes
• left-click on a selected node to open a window with node details
• C resets the camera to the starting position
• Q,W,E,A,S,D to move the simulation area along orthogonal axes
• right-click+mouse drag to rotate the camera
• mouse scroll for zooming in and out
• left-shift added to the camera commands above for precision control
• any other key will show/hide a legenda displaying this list

Hovering on a node will also display its UID in the top-left corner.