Sets of Edges ( edge_set )

Definition

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

#include < LEDA/edge _set.h >

Creation

edge_set

S(graph G)

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

Operations

void	S.insert(edge x)	adds edge x to S.
void	S.del(edge x)	removes edge x from S.
bool	S.member(edge x)	returns true if x in S, false otherwise.
edge	S.choose()	returns an edge 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

An edge set S for a graph G is implemented by a combination of a list L of edges and an edge array of list_items associating with each edge 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 edges of G.