Marshall Farrier's tech blog

This library is a Java implementation of the graph datastructures and algorithms presented in Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 3rd ed.(CLRS). I have also used some ideas from Robert Sedgewick's graph algorithms books (in C as well as in Java) and a few other sources. I started developing the library late last fall while working through the graph theoretical portion of CLRS. To begin with, I just found it helpful for getting a solid grasp of the material in the book. But then I also discovered that Java has no standard support for graphs (although there are several unofficial graph libraries for Java easily found by googling). Boost, by way of contrast, does provide C++ support for graphs. Since I intend to continue the study of graph theory both from a mathematical perspective and from the computer science standpoint, I thought it would be useful essentially to convert my current knowledge into code so that I could continue to refine it as I learn more about the subject.

In its current form the library does not support multigraphs but does support both directed and undirected graphs and, for convenience, allows for alphabetical as well as numerical labeling of vertices. While the latter feature has made the code a good deal more expansive than it would have been otherwise, I don't think it has incurred any significant cost in terms of runtime. Standard numbering begins at 0 (in contrast to CLRS's starting at 1) but the graph constructor allows lettering to start at any letter and continue consecutively up to 'z' or 'Z'. Overflowing beyond 'z' or 'Z' will raise an exception. The library also does not support discontinuous labeling, such as 'a', 'b', 'c', 'x', 'y', 'z'. Once you specify a starting letter in your constructor, the remaining vertices will be labeled consecutively up to the size of the graph, which is also specified in the constructor.

The hardest part of developing this library was working out a viable structure for the graph objects. Once I had done that in a way that seems viable (after numerous versions that I ended up rejecting), it became more or less trivial to convert the pseudo-code from CLRS into Java code for the library. The only difficulties were really just making sure that the numbering matched up properly (i.e., translating between their numbering starting at 1 and mine starting at 0). Nonetheless, I haven't yet finished all of the algorithms in the book because I did spend a lot of time working on the basic structure of the various graph objects as well as some helper classes. And I've tested the code mainly on examples from the book but haven't tried it yet on large graphs to see where the performance limitations might lie.

Following CLRS, the library offers the alternatives of storing edges in a linked list for each vertex (usually better for sparse graphs) or in a 2-dimensional array, as a matrix (better for dense graphs). The following tree shows the various graph classes, some helper classes, and the inheritance relationships between Graph objects:

The documentation of the library will have to be incremental. While the class hierarchy provides a basic overview, the user will for now unfortunately have to just look at the code to find the signature and outputs of the various methods. Since it is a work in progress, it doesn't make much sense at this point even to attempt a complete documentation. However, the library has reached a point where others might be interested in taking it for a spin, participating in its development or providing helpful ideas and critique. Time permitting, I'll provide as much documentation as I can as the library develops.

Over and above the basics needed for working with any graph (e.g., inserting an edge), the library currently includes some of the juicier algorithms in the LinkedListGraph and WeightedLinkedListGraph classes. I will in fact probably try to implement all functionality first on the linked list style graphs (again following CLRS) before developing the corresponding methods for matrix graphs. Currently, the LinkedListGraph class supports:

• breadthFirstSearch()
• depthFirstSearch()
• topologicalSort()
• stronglyConnectedComponents()

And the WeightedLinkedListGraph class supports additionally:

• minSpanningTreeKruskal() // Kruskal's algorithm
• minSpanningTreePrim() // Prim's algorithm

The .zip downloadable file contains the complete folder that I use in Eclipse. It should import easily in its entirety if you use Eclipse. For other IDEs you can extract and copy-paste.

Download from GitHub

Documentation