Customer Reviews

Algorithms in Java, Part 5: Graph Algorithms (3rd Edition) (Pt.5)

5 star:		(3)
4 star:		(1)
3 star:		(0)
2 star:		(0)
1 star:		(0)

 

 

In my work, I have a bunch of interlinked objects. I can use tables to display these, but showing linkages is awkward. It is far more natural to graph them. This lets me use evolution, for the human eye and brain are excellent at processing images and discerning patterns in them. But I also want to algorithmically find groupings and invariant properties of the graphs. There is a danger here. In graph theory, it is very easy to inadvertantly pose a simple question that is computationally hard to solve (NP-hard). Conversely, I don't want to reinvent the wheel. From graph theory, there may well be properties of my graph that I can easily extract. Certainly, the amount of research on graphs is voluminous.

But how does one take advantage of that? Consulting research journals in maths for papers on graph theory is really feasible only for the career mathematician. But for me, graphs are just a tool; not an ends per se. So I need a book that has the right amount of complexity. It needs to get enough into the subject, beyond the trivial exposition of definitions. Yet it should not bury me in lemmas and theorems.

I found such a book! This one. A well deserved third iteration. The explanations are extremely clear. Before I encountered this text, I used Donald Knuth's "Art of Computer Programming" (which is also put out by Addison-Wesley) and his treatment of graphs. But Sedgewick's discourse is far more extensive and, to me, just as well written.

A bonus is the extensive problem sets at the ends of each chapter. Even if I have no inclination to do them, the results they give are a valuable extension of the text, by providing an extra summary of the research. I only wish that Sedgewick would provide answers, like Knuth. But this is a just a quibble.

This edition has example code in Java. Certainly nothing wrong with that. [I program in Java.] But really the code should be a secondary consideration to you. If you are a programmer and you can understand the text, then you should be of a calibre that you can write the code.

Another reviewer gave this book a one star rating citing that the book falls short on practical examples.

In light of that, I'm concerned that other readers might overlook what, in my opinion, may be one of the most comprehensive and well written introductions to graph theory and graph algorithms that there is, and certainly one of the best that I have personally come across thus far.

Recently I took on a project wherein I needed to solve a shortest path problem for a particular kind of graph. I am not a specialist in graph theory and needed practical information that I could utilize immediately. For me, this book fit the bill and was a godsend.

It is true that I already had a practical real world application in mind before I even knew of this book but this book has exceeded both my needs and expectations.

It is easy for me to understand how you may not initially see the practical value of the information being presented, if the sole reason you're studying this book is simply because it is a part of your college curriculum. I think, however, that that does not lessen the value of the book, especially for those of us who do have practical applications for the material.

If you are looking for an informational resource for a real-world problem related to graph theory, you would do well to consider this book.

The book does actually open by citing several practical examples of areas where these algorithms can be applied, although, perhaps the reader who assigned the one star rating may have appreciated and benefited from a case study.

As a self-study effort, I read this book cover-to-cover -- worked through most proofs and produced working code for every algorithm discussed in this text. I've also done most exercise questions at the back of each section. This is by far the most comprehensive source on graph algorithms that I could find. Its sections on directed graph algorithms and network flow are presented in rigorous details.

As much as I admired the work presented in this text, every masterpiece has its flaws, and this one is no different. Many sections of the text had cryptic descriptions, ambiguous explanations, and fragmented code samples that required time to "reverse-engineer". It is as if the author wants the reader to prove his/her worth before presenting all the hidden gems in this book.

For example, the entire Network Flow chapter is filled with partial code fragments that the reader has to piece together manually. Key details like the Network class and the interface that it exposes, were missing and renders the code samples difficult to dig through. The modified Bellman-Ford algorithm that's used to discover negative cost cycles in residual networks -- the central piece of the puzzle -- was assigned as exercise without solutions. On one hand it served high pedagogical values, on the other it was tedious to work through by yourself without help from an instructor.

Sometimes when I read this book, I have to pause. My eyes are teary, and I think back to days of yesteryear. Yes, better days, when this book used to run free.

But, alas, those days have ended, and this book is no where to be found. My child, fret not, for the book will live again...

Michael "The Creator" Schidlowsky has well endowed the new version of this book with Java code obviously fondled by God himself. Legend has it that Michael, or "Mookie" as his name was in those days, brought forth dozens of great stone tablets, each on which was written a "Java file." Taken together, Mookie's tablets were a wonderful introduction to basic algorithms and data structures. Thank you, master.