next up previous contents index
Next: Lists of Nodes ( Up: Graphs and Related Data Previous: Sets of Nodes (   Contents   Index


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.


next up previous contents index
Next: Lists of Nodes ( Up: Graphs and Related Data Previous: Sets of Nodes (   Contents   Index
LEDA research project
2000-02-09