A Java Library of Graph Algorithms and Optimization + CD
The series ‘Discrete Mathematics and Its Applications’ has delivered an unusual fruit this time: a library of algorithms for various combinatorial problems programmed in Java. The book covers all the usual areas of algorithmic graph theory and optimization ranging from the random generation of graphs, connectivity, network flows and graph embedding, to linear and quadratic optimization, each area being discussed in a separate chapter. The chapters share a common structure and each of them lists a bunch of related problems. All problems are first described and then an outline of the algorithm is presented, followed by a full program. The program is accompanied by a description of inputs and outputs and a simple example of its use. The code of the programs is also available on a CD included in the book.
However, serious users of the book will notice several drawbacks: the description of the algorithms sometimes lacks important details such as the time complexity (which is surprising, especially in exponential algorithms for NP-complete problems) and the program code is often hard to understand because the aspiration to make all programs self-contained has led to avoiding all abstractions and repeating the same code patterns in many places. For some problems, faster and more easily implemented algorithms are already known. In short, it is a good book for anybody who needs to solve an isolated problem but more experienced programmers will probably still prefer the existing open-source program libraries like LEDA or Pigale.