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.
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.