CIT 594 Graph API Hints
Spring 2006, David Matuszek

In my second lecture on Abstract Data Types I gave the following definitions:

When you build an API (Application Programmer Interface), you want a necessary and sufficient set of methods, with possibly a few (but not too many) convenience methods. Think of these as "basic building blocks." The API should be complete enough to allow the user to implement complex algorithms on the ADT; the API itself should not provide complex algorithms, just the tools to build those complex algorithms.

Some of the Java APIs provide methods that use complex algorithms. These are present because (1) Sun knows from experience that the methods will get a lot of use, and (2) Sun programmers can do a careful, efficient implementation.

In that same talk, I provided this classification of operations on an ADT:

I went on to say that the constructors and transformers must together be able to create all legal values of the ADT, and that the accessors must be able to extract any data from the ADT.

If you think about some of the ADTs that Java provides--for example, Stacks, ArrayLists, or HashMaps--you will see that in each case, the constructors create an "empty" structure, which you can then modify by mutative transformers (push, pop, add, remove, put). You can use accessors (peek, get, size, etc.) to learn about all necessary details of the ADT, though you may need several method calls to get to any particular piece of data.

So as you decide what methods to supply in your graph ADT, ask yourself the following questions:

Bottom line: More is not better! A small set of simple operations should be your goal. It's even nicer if all your operations are O(1).

Or, to put things another way: If you do it right, this is an easy assignment; but if you do it wrong, it can be an arbitrarily difficult assignment.