Adjacency List

An adjacency list is a graph representation stored as a list of lists--the first list contains and is indexed by each of the connected vertices in the graph. Each vertex $v$ in this list points to another list containing all other vertices connected to $v$ by some edge.

A list indexed by something other than a number (its offset from the array's virtual origin in memory) is called many things in different languages: the generic term is ``associative array''. In Perl this is called a ``hash''. In Java, this is called a Map. A Map is any structure that associates one object with another. So for your adjacency list, you want a Map which associates a named vertex with a list of its neighbors. Map is a Java interface which contains methods that accomplish this goal. The folks at Sun have also implemented a guaranteed logarithmic Map called TreeMap (located in the java.util package).

A Map is a collection of entries. An entry is a key-value pair. A value is retrieved by searching the map for its corresponding key. The map is sorted by its keys, so for a TreeMap, which sorts the entries for logarithmic-time retrieval, either the keys must be Comparable or a Comparator must be provided. For an adjacency list, the keys would be the names of the vertices in the graph and the values would be their corresponding neighbor lists. A map is described as ``mapping $x$ to $y$'' where $x$ and $y$ are types; since our vertices will have names, we will represent them with strings. The neighbor lists can really be any collection (a list or a set; edges in our graphs will be unique based on their endpoints, so we will never have more than one edge connecting two vertices $x$ and $y$). So our adjacency list is really just a map which maps Strings to Lists.

The goal for our adjacency list is to discover as efficiently as possible whether an edge $(x,y)$ exists. With TreeMap, which is guaranteed to behave logarithmically, given a key $k$, we can get its corresponding value in logarithmic time. However, our adjacency list maps strings to lists. We can get the list of neighbors for a given vertex in logarithmic time, but unless we can also then search that list for the other endpoint in logarithmic time, our overall complexity will still be linear. Remember that our lists are really sets due to uniqueness of edges. Java has another great class for us called TreeSet which is, as you've probably guessed, a guaranteed logarithmic set. If your adjacency list is built using a TreeMap which maps Strings to TreeSets, the overall complexity of locating an edge in your adjacency list will be $O(\log v + \log e)$. Not bad!

You don't need to write any new structures to implement a logarithmic adjacency list--just use the existing Java structures to your advantage. Your AdjacencyList class only needs a TreeMap which maps Strings to TreeSets and methods that interact with that TreeMap. (Note that as of Java 1.4, there is no formal way, as in C++ templates, to specify that you are creating a TreeMap that specifically maps Strings to TreeSets--that invariant is enforced only by what you put in the map. Java 1.5 addresses this issue). Your adjacency list has no formal requirements about how it is implemented--we will interact with it only via your command parser, so feel free to name the methods anything you want. You are not even required to write an AdjacencyList class if you don't feel the need to write one. The real requirement in place is that you must be able to acquire some collection object containing all vertices adjacent to a given vertex in logarithmic time or better. As long as this requirement is met, you have complete liberty in implementing this however you please.