This project contains an implementation of a linear-time sampling algorithm for geometric inhomogeneous random graphs (GIRG) with a special case implementation for hyperbolic random graphs (HRG). Details on the algorithms as well as the models can be found in our corresponding paper: Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs (conference version, journal version).
We provide a C++ library and a command line client for each of the two generators.
The most recent version of the generators can be installed from our personal package archive (PPA link).
sudo add-apt-repository ppa:chistopher/ppa
sudo apt-get update
sudo apt-get install libgirgs-all
The libgirgs-all package depends on all sub-packages:
- the runtime
libgirgs - the cli's
libgirgs-cli - the headers and cmake files
libgirgs-dev - and the debug runtime
libgirgs-dbg
If you installed libgirgs-cli you can verify the install by running genhrg --version.
The result should look something like this.
HyperGIRGs command line interface.
girgs v1.0.2 (8a6647cd7ec2)
Generator for Geometric Inhomogeneous Random Graphs
Karlsruhe Institute of Technology
https://github.com/chistopher/girgs/
christopher.weyand@kit.edu
A Win64 installer for each release can be downloaded from the release page. It features similar components as the ubuntu PPA. If a more recent version is desired, the project can be build and installed from source.
A packaged build is not available. Feel free to open a pull request. However, building from source should work just as detailed below. We will add osx to the travis builds as soon as their images have CMake >=3.12.
An integration into the NetworKit framework is planned.
To build the project from source you need
- CMake 3.12+
- C++11
- OpenMP
- OPTIONAL: CPU with BMI2 instruction set
The optional development components use
- Google Test
- Google Benchmark
- Doxygen, which uses Graphviz
- Boost
The simplest way to build the project is
cmake -DCMAKE_BUILD_TYPE=Release -B build
cmake --build build
or for a debug build
cmake -DOPTION_BUILD_TESTS=ON -B build-debug
cmake --build build-debug
The project can be installed globally with the install target.
Alternatively, there is the pack target which generates a debian package that can be installed via aptitude or dpkg.
The project contains two CLI's: gengirg and genhrg.
You can use --version to determine the version of your respective generator.
The GIRG generator features the following input parameters.
./gengirg --help
usage: ./gengirg
[-n anInt] // number of nodes default 10000
[-d anInt] // dimension of geometry range [1,5] default 1
[-ple aFloat] // power law exponent range (2,3] default 2.5
[-alpha aFloat] // model parameter range (1,inf] default infinity
[-deg aFloat] // average degree range [1,n) default 10
[-wseed anInt] // weight seed default 12
[-pseed anInt] // position seed default 130
[-sseed anInt] // sampling seed default 1400
[-threads anInt] // number of threads to use default 1
[-file aString] // file name for output (w/o ext) default "graph"
[-dot 0|1] // write result as dot (.dot) default 0
[-edge 0|1] // write result as edgelist (.txt) default 0
The HRG generator features the following input parameters.
./genhrg --help
usage: ./genhrg
[-n anInt] // number of nodes default 10000
[-alpha aFloat] // model parameter range [0.5,1] default 0.75
[-t aFloat] // temperature parameter range [0,1) default 0
[-deg aFloat] // average degree range [1,n) default 10
[-rseed anInt] // radii seed default 12
[-aseed anInt] // angle seed default 130
[-sseed anInt] // sampling seed default 1400
[-threads anInt] // number of threads to use default 1
[-nkr 0|1] // use NetworKit R estimation default 0
[-file aString] // file name for output (w/o ext) default "graph"
[-edge 0|1] // write result as edgelist (.txt) default 0
[-coord 0|1] // write hyp. coordinates (.hyp) default 0
The library is based in the cmake-init project template. Detailed information on the build system design can be found there.
For the standard use case, we provide a buffered edge list generation supporting parallel execution in the headers hypergirgs/Generator.h and girgs/Generator.h.
#include <hypergirgs/Generator.h>
auto R = hypergirgs::calculateRadius(n, alpha, T, deg);
auto radii = hypergirgs::sampleRadii(n, alpha, R, rseed);
auto angles = hypergirgs::sampleAngles(n, aseed);
// generates edge list as vector<pair<int,int>>
auto hrg_edges = hypergirgs::generateEdges(radii, angles, T, R, sseed);Internally, the algorithm is templated with a callback that is called for each emitted edge. Using lambdas, a custom callback can be used as follows.
#include <hypergirgs/HyperbolicTree.h>
auto callback = [] (int a, int b, int tid) { ... }; // tid is thread id
auto generator = hypergirgs::makeHyperbolicTree(radii, angles, T, R, callback);
generator.generate(seed);For details we refer to our example applications in source/examples/ or the CLI's in source/cli/.
Also, a deployed version of the documentation is available at weyand.dev/girgs.
To include girgs into your CMake project, it's as simple as this.
cmake_minimum_required(VERSION 3.12)
project(ineedgirgs CXX)
find_package(girgs REQUIRED)
add_executable(main main.cpp)
target_link_libraries(main PRIVATE girgs::girgs)If you have girgs installed globally (e.g. via the Debian package), they are found automatically.
If you want to link against a source build, then add the girgs repo to your CMAKE_PREFIX_PATH or specify it directly when configuring the build.
That is, in your repo do cmake -Dgirgs_DIR=~/repos/girgs/ -B build-debug.