2.12. What we did not cover

Learning objectives

The class partition
The class dynamic_trees
The class tree_collection
The class file_istream
The class file_ostream
The class string_istream
The class string_ostream

There are some further classes belonging to the simple data types and container types of LEDA we did not describe in this introduction.

The classes partition, dynamic_trees, and tree_collection do not find immediate use in application programs. However, they can be used as constituents of other data types and algorithms.

For example, the class partition is an indispensable component of Kruskal's algorithm for the computation of minimum spanning trees, which we do not have to implement by ourselves thanks to LEDA. (Of course, it is up to us to write our own version of it; we then can go back to partition). A partition manages subsets of a set and allows the union of subsets to larger subsets.

An object of the type dynamic_trees is a set of trees whose edges are directed towards the root and provided with information. The class allows to make a tree a partial tree of another one. A tree_collection is almost the same; however, here it is the nodes carrying the information, not the edges.

The classes file_istream and file_ostream are equivalent to the classes istream and ostream, respectively, of the C++ standard library and only contained in LEDA for reasons of backward compatibility.

The two classes string_istream and string_ostream realize input and output streams, respectively, which work on strings, that is, they take their input from a string and write their output into an internal string buffer. According to Christian Uhrig of Algorithmic Solutions, “they provide nothing revolutionarily new”.

Further information about these classes can be found on the manual pages of the corresponding section of the manual.