Class Buckets

Defined in File Heuristics.h

Class Documentation

class Buckets

the structure with buckets of exercise 19.17: for k = 0 , 1 the nodes by the number h of their edges to \( V_k \), bucket( k , h ), its size dim( k , h ), and the least and largest bucket not empty; a node leaves a bucket in O( 1 ) by its place in it

Public Functions

explicit Buckets(int n)

the empty structure for the nodes [ 0 , n )

Pre:: n >= 0

void insert(int u)

u with no edges to either side

Pre:: u is a node out of the structure

void remove(int u)

Pre:: u is in the structure

void inc(int k, int u)

u has one more edge to \( V_k \)

Pre:: u is in the structure, k is 0 or 1, and u has fewer than n edges to \( V_k \)

bool contains(int u) const

Pre:: u is a node

int count(int k, int u) const

Pre:: k is 0 or 1 and u is a node

const Nodes &bucket(int k, int h) const

Pre:: k is 0 or 1 and 0 <= h <= n

int dim(int k, int h) const

Pre:: k is 0 or 1 and 0 <= h <= n

int min(int k) const

Pre:: k is 0 or 1

int max(int k) const

Pre:: k is 0 or 1

int choose(int k) const

the node to add to \( V_k \): in the least bucket of \( V_{1-k} \), the one with most edges to \( V_k \), the first of the bucket on ties

Pre:: k is 0 or 1 and the structure is not empty
Post:: the result is in the structure