next up previous contents index
Next: Sets of Edges ( Up: Graphs and Related Data Previous: Two-Dimensional Node Maps (   Contents   Index


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.


next up previous contents index
Next: Sets of Edges ( Up: Graphs and Related Data Previous: Two-Dimensional Node Maps (   Contents   Index
LEDA research project
2000-02-09