Algorithms on Trees and Graphs [Englisch] [Gebundene Ausgabe]

I'm pleased with the text in this book; the descriptions are almost all clear, and reading through the book gives me insight into some more interesting problems in trees and graphs. The high points of the book are its treaments of tree and graph isomorphism, but I also found the discussions of non-traditional traversal algorithms on trees and graphs very interesting. The author discussions leaf-first, breadth-first, and depth-first traversals and provides algorithms for their implementation. Many of the algorithms include correctness proofs.

These topics alone made the book worth its to me. A deep academic book that costs less than $50 is nearly unheared-of.

Unfortunately, there are two flaws that make the book hard to use. In a nutshell, the author expects the reader to buy into a couple of pretty invasive and expensive propositions.

First, the author decided to use literate programming for all of his presented algorithms and code fragments. This isn't so bad, since literate programming is about documenting code. If you suppose that the author wrote the code, then documented it, then calld it a book, using a tool like literate programming seems like a natural choice.

But if you're not familiar with literate programming, it's a bit of a chore. The author's introduction to literate programming doesn't help with some of the questions even an experienced programmer might have wend reading the text. More practically, literate programming enforces operators that are different than most C/C++ developers are familiar with, and can cause confusion when reading the text. ^ is used, for example, to indicate a logical and, where C/C++ developers expect it to indicate a bitwise-exclusive or.

While it's esay to eventually overcome such tricks of memory, I've been finding it hard to scan literate programs to find definitions and declarations. The author doesn't include a CD (and at this cover price, that is hard to fault) but also doesn't make his code available for download. His website includes a LEDA-based program that interactively demonstrates some algorithms, but doesn't include code for the algorithm his own books develops and discusses.

The other decision made by the author, to the overwhelming inconvenience of this reader, is the reliance on the LEDA library for his samples and programs. The algorithms are understandable without the library, but a reader without access to LEDA doesn't benefit from any of the visualizations the author provides. , and several include

In fact, the author spends about 40 pages discussing LEDA and the characteristics of its implementation. Maybe researchers working on tree and graph algorithms all use LEDA and have ready access to it, but the literate programming code provided to for some of the algorithms isn't useful to readers who aren't familiar with LEDA, as researching the definitions and declarations themsleves becomes arduous.

The bibliography is very diverse, with more than 380 entries and is well-cited throughout the book. Unfortunately, the author sometimes relies on the bibliography too much. On page 392, the author brings up "the so-called graph isopomorphism disease" without defining it himself; he instead relies on his bibliography entries to give the user any definition or background on the "disease".

Unfortunately, the index received not nearly as much attention as the bibliography; neglecting whitespace, it's scarcely more than a single page long!

The book appears to be something more than a research paper, but is written much like a research apper would be. The book probably also serves well for a class that teaches this subject, and assumes LEDA and literate programming as prerequisites. But as a commercial developer who's interested in applying advanced graph and tree algorithms to the work I'm doing, I found the book has limited its value by relying on LEDA and applying literate programming.

All this said, I still feel it's appropriate to give the book four stars. The material covered is hard to find elsewhere, and with some effort I can overcome the LEDA and literate programming hurdles. Since I don't use LEDA or literate programming day-to-day, I'll have to overcome that unfamiliarity every time I pick up the book as a reference.

This book's title is very misleading, as the author's focus really is on subgraph problems (e.g. subgraph and tree isomorphism, clique, independent set, and vertex cover).

The book barely mentions other graph theory topics such as distance algorithms (e.g. single-source shortest path, minimum-spanning tree, transitive closure), network flow, or graph colouring. This odd focus is really frustrating since the author spends a large number of pages on relatively simple topics such as tree traversal (34 pages on things like pre-order traversal) and graph traversal (42 pages on things like depth-first search). In fact, in section 5.3 on graph traversal applications, the author suggests that the reader may have already learned about algorithms such as shortest path or topological sorting, so he instead gives an example of ordered graph isomorphism. I do not understand why the author would make such an assumption; if the reader is assumed to already know about many applications of graph traversal, then why did the author spend 42 pages explaining what graph traversal is?

I believe one possible reason why the author does not discuss such "simpler" graph algorithms is that the LEDA library already has functions that implement algorithms like Dijkstra's, Bellman-Ford, MST, and max flow. However, the author does not spend time even defining what these problems are and only mentions the existence of these functions in the appendix.

Other things I did not like about the book:

- Much of the material seems to be simply cut-and-paste from one topic to the next. Case in point: the chunk of text saying "The problem of [problem] belongs to the class of NP-complete problems ... size of the graph" is pasted verbatim into at least four sections. Other lengthy passages are similarly pasted.

- The author's writing style makes reading the book more of a chore than it needs to be. My philosophy is that simple ideas should be explained simply, and I posit that this philosophy should be applicable to a depth-first traversal of a graph. However, the author is a bit formal in his explanation of DFS (among other topics), saying that "a simple procedure for a depth-first traversal of a graph consists of performing a preorder traversal upon each of the depth-first trees in the depth-first spanning forest of the graph" (p. 261). Compare this definition to the more fluid and intuitive definitions given by CLRS (2001) on page 540 and by Sedgewick's (Graph) Algorithms in C++ (2002) on page 87.

- As a minor point, the author uses the term "arc" whereas in the literature the more common term is "edge". I suppose this is not a big deal, but then the author defines a graph as having a vertex set V and an arc set E. Furthermore, in the LEDA appendix where the author is discussing the graph API that has word "edge" in the function calls (e.g. number_of_edges()), the author continues to use the term "arc".

- I am not sure if the C++ implementions using LEDA provided by the author really are helpful enough to outweigh their terseness and difficulty for reading. A better approach might have been CLRS-style pseudocode to explain the implementations. However, this book is really more of a LEDA applications guide, and I believe many people will find the code examples to be very helpful.

Now, here are the good points of this book that raise my rating from 3 stars to 4:

+ Chapter 2 is very, very nice. It uses a recurring example problem of tree edit-distance throughout four sections on backtracking, branch-and-bound, divide-and-conquer, and dynamic programming, thereby allowing the user to see how these different algorithmic approaches differ for a fixed problem. The discussion on tree edit-distance itself was new to me and very interesting.

+ The author makes nice use of examples throughout the book. Almost every theorem and definition is accompanied by an illustrated example.

+ The references are very thorough (at least for the time that the book was published), and the bibliographic section in each chapter, while short, frame the related work references very well.

+ The author consistently uses backtracking throughout the subgraph algorithm implementations, so it was good to hammer that down for the reader. However, it would have been nice to see the author discuss different implementations using dynamic programming (to attain some pseudo-polynomial time algorithm perhaps), approximation algorithms, or stochastic search (e.g. genetic algorithms).

In summary, this is a good book, but only if you are interested in the subgraph problems that the author covers.

Good on describing graph theory algorithms but is rendered bad due to that literate programming ... Simple algorithmic notation would have made the book much better...