GitLab

This implements a general wrapper for dense_hash_map and dense_hash_set,
that falls back to unordered_map and unordered_set, if sparsehash is not
enabled.

This also changes the semantics of random_rewire() when parallel edges
/ self loops are forbidden, but the initial graph contains them. Now,
instead of throwing an exception, the rewiring is attempted, with no
new parallel edges / self-loops being created. Under some
circumstances, if the degree sequence is graphical, eventually the
graph can become simple after sufficiently many sweeps.

This also improves some of the existing shuffling strategies with a fast
alias sampling. The parameter names of the random_graph() and
random_rewire() functions have been made more consistent.

Dumping boost::adjacency_list<> improves memory usage by a factor of
two, and also slightly improves performance in some cases.

This enables the inclusion of the non-boost tr1 headers if a recent
enough version of libstdc++ is detected. This als fixes a bug with
clang when sparsehash pulls unwanted tr1 headers.

The object may be globally reset via the seed_rng() function.

This makes the code more efficient if the input parameter combinations
are much larger than the graph itself.

This fixes a bug in the "correlated" mode in random_rewire().

This implements a general "blockmodel" generation / rewiring algorithm,
using Gibbs acceptence / rejection sampling (a.k.a Metropolis-Hastings).

This also implements some optimizations in the rewiring code, which
makes it more efficient on filtered graphs.

This introduces several simplifications and corrections to the graph
rewire algorithm, to guarantee unbiased sampling.

Now a move is outright rejected if it produces a
self-loop/parallel-edge, instead of retried. This also adds a
"non-sweep" mode, where edges are rewired randomly, possibly with
repetition.

The edge moves are now simplified to the target of the edges only,
since swaping sources is redundant.

The number of iterations can now be explicitly modified, so it is not
necessary to call the function more than once, and it is emphasized in
the documentation that only after sufficiently many iterations can the
graph be guaranteed to be fully mixed.

This enables support for older versions of GCC (>=4.2), by falling back
to the boost tr1 implementation when the GCC version is less than 4.4.

This includes also some internal refactoring, and bug fixes.

This extensively modifies the random_rewire() algorithm, so that only
either the source or the edge of each edge is rewired (not both, as
previously), and no parallel edges are created during the algorithm (if
desired).

The new version is much faster, and never gets stuck. However, more than
one run may be necessary in order to obtain a uniform shuffling.

This fixes a implicit directionality bug in random_rewire() with
undirected graphs.

This fixes a problem, where the underlying edge directionality would
cause correlations to arise when rewiring undirected graphs. Now each
edge is correctly considered in both possible orientations, which are
chosen randomly.