Sets of Nodes ( node_set )

Definition

An instance S of the data type node$\_$set is a subset of the nodes of a graph G. S is said to be valid for the nodes of G.

#include < LEDA/node_set.h >

Creation

node_set

S(graph G)

creates an instance S of type node$\_$set valid for all nodes currently contained in graph G and initializes it to the empty set.

Operations

void	S.insert(node x)	adds node x to S.
void	S.del(node x)	removes node x from S.
bool	S.member(node x)	returns true if x in S, false otherwise.
node	S.choose()	returns a node of S.
int	S.size()	returns the size of S.
bool	S.empty()	returns true iff S is the empty set.
void	S.clear()	makes S the empty set.

Implementation

A node set S for a graph G is implemented by a combination of a list L of nodes and a node array of list_items associating with each node its position in L. All operations take constant time, except for clear which takes time O(S). The space requirement is O(n), where n is the number of nodes of G.