Genealogy Display Program: A Larger Example of Use of STL

David R. Musser

The SIGACT Theoretical Computer Science Genealogy lists information on earned doctoral degrees (adviser, university, and year) of theoretical computer scientists worldwide. The website provides a convenient means of looking up individuals a few at a time. To get the "big picture," though, it's useful to display the entire forest of academic ancestor trees represented in the TCS Genealogy data base. The treeform program does that, working from an ascii file version (72k) of the data (obtained from and slightly updated) and producing a listing (102K) that displays the tree structure using indentation. The students of each Ph.D advisor are listed in order of date of the students' Ph.Ds (oldest first).

The output contains many fascinating details, but it is also instructive to examine the program to see how it combines several components of STL (vectors, maps, multisets, the generic find algorithm, and library- and user-defined function objects) to do the job efficiently and succinctly.

This program has been compiled and executed successfully with the GNU C++ compiler (version 2.7.2), the Apogee apCC compiler (SUN Unix, version 3.0), and the IBM Visual Age C++ compiler (Windows 95, version 3.5). Note that one header file needed, bstring.h, is not part of STL but is available here. (If you already have the STL version from the Rensselaer ftp site, bstring.h is included.)