Class BVGraph
Defined in File BVGraph.h
Class Documentation
-
class BVGraph
a static directed graph with the lists compressed by reference, copy blocks, intervals and gaps
Public Types
-
using List = std::vector<std::size_t>
-
using Interval = std::pair<std::size_t, std::size_t>
an interval of extra nodes, its left extreme and its length
Public Functions
-
BVGraph(void) = default
-
explicit BVGraph(const std::vector<List> &a, std::size_t w = 7, std::size_t r = 3, std::size_t lmin = 4)
the graph of the adjacency lists a, with the window w, chains of references at most r long and intervals at least lmin long
- Pre:
each a[ u ] strictly increasing in [ 0 , n ), w , r >= 1 and lmin >= 2
-
std::size_t order(void) const
the number of nodes, n
-
std::size_t edges(void) const
the number of edges, m
-
std::size_t codeBits(void) const
the bits of the lists
-
std::size_t sizeInBits(void) const
the bits of the lists and of their places
Public Static Functions
-
static BitVector copyList(const List &s, const List &ref)
the copy list of s against the reference list ref: a bit per item of ref, 1 if it is in s
-
static std::pair<bool, std::vector<std::size_t>> copyBlocks(const BitVector &c)
the copy blocks of the copy list c: its first bit and the lengths less 1 of its runs but the last
-
static std::pair<std::vector<Interval>, List> intervals(const List &e, std::size_t lmin)
the runs of at least lmin consecutive integers of the strictly increasing e, and the residuals
-
static std::vector<std::uint64_t> residualGaps(const List &res, std::size_t x)
the residuals res of x as written: the first as signedToNatural() of its difference from x, the others as the gaps less 1
-
using List = std::vector<std::size_t>