A Directed Graph as a Wavelet Tree

The wavelet tree holds S, all out-neighbourhoods concatenated; the bitvector B holds the out-degrees in unary. Together they answer out- and in-neighbour queries symmetrically.

colour = a vertex's identity position under inspection cells being scanned B's 1 = list separator

Pick an operation and press Run. Watch the query bounce between the graph, the sequence S, and the bitvector B.

Result —

Operation

Vertex v

Vertex u

—

Vertices 5

Delay 750ms

out-neighbour: select₁(B,v) finds v's block, then read S inside it. in-neighbour: select_u(S,i) finds an edge into u, then B maps that S-position back to its source vertex. degrees are a gap in B (out) or a symbol count in S (in).