1
// This class allows to maintain a list of vertices,
2
// sorted by degree (largest degrees first)
3
// Operations allowed :
4
// - get the vertex having max degree -> Cost = O(1)
5
// - remove any vertex from the graph -> Cost = Sum(degrees of neighbours)
6
// [ could be O(degree) if optimized ]
16
int n; // INITIAL number of vertices
17
int dmax; // CURRENT Maximum degree
18
int *deg; // CURRENT Degrees (points directly to the deg[] of the graph
20
// Vertices are grouped by degree: one double-chained lists for each degree
21
int *list; // list[d-1] is the head of list of vertices of degree d
22
int *next; // next[v]/prev[v] are the vertices next/previous to v
23
int *prev; // in the list where v belongs
24
void pop(int); // pop(v) just removes v from its list
25
void insert(int); // insert(v) insert v at the head of its list
29
// Ctor. Takes O(n) time.
30
box_list(int n0, int *deg0);
35
// Self-explaining inline routines
36
inline bool is_empty() { return dmax<1; };
37
inline int get_max() { return list[dmax-1]; };
38
inline int get_one() { return list[0]; };
39
inline int get_min() {
45
// Remove v from box_list
46
// Also, semi-remove vertex v from graph: all neighbours of v will swap
47
// their last neighbour wit hv, and then decrease their degree, so
48
// that any arc w->v virtually disappear
49
// Actually, adjacency lists are just permuted, and deg[] is changed
50
void pop_vertex(int v, int **neigh);
53
} // namespace gengraph
added
removed
src/gengraph_box_list.h
