Class K2Tree

• Defined in File K2Tree.h

Class Documentation

class K2Tree

the adjacency matrix of a static directed graph as a k^2-tree

Public Types

using Edge = std::pair<std::size_t, std::size_t>

Public Functions

K2Tree(void) = default

K2Tree(std::size_t n, const std::vector<Edge> &e, std::size_t k = 2)

the graph of n nodes and the edges e (repeated ones counted once)

Pre:

k >= 2 and the nodes of the edges in [ 0 , n )

Post:

the cells marked are the distinct edges

std::size_t order(void) const

the number of nodes, n

std::size_t edges(void) const

the number of distinct edges

std::vector<std::size_t> neighbors(std::size_t u) const

the successors of u, in increasing order

Pre:

u < order()

std::vector<std::size_t> reverseNeighbors(std::size_t v) const

the predecessors of v, in increasing order

Pre:

v < order()

bool hasEdge(std::size_t u, std::size_t v) const

whether ( u , v ) is an edge

Pre:

u , v < order()

const BitVector &levels(void) const

T, the marks of the levels but the last.

const BitVector &leaves(void) const

L, the marks of the cells.

std::size_t sizeInBits(void) const

the bits of T, L and the rank directory of T