Name: The Stanford GraphBase
ISBN: 9780321606327

The Stanford GraphBase

The Stanford GraphBase: A Platform for Combinatorial Computing represents the first fruits of Donald E. Knuth's preparation for Volume 4 of The Art of Computer Programming. The book's first goal is to demonstrate, through about 30 examples, the art of literate programming. Each example is a programmatic essay, a short story that can be read and enjoyed by human beings as readily as it can be read and interpreted by machines. In these essays/programs, Knuth makes new contributions to the exposition of several important algorithms and data structures, so the programs are of special interest for their content as well as for their style. The book's second goal is to provide a useful means for comparing combinatorial algorithms and for evaluating methods of combinatorial computing. To this end, Knuth's programs offer standard freely available sets of data - the Stanford GraphBase - that may be used as benchmarks to test competing methods. The data sets are both interesting in themselves and applicable to a wide variety of problem domains. With objective tests here made possible, Knuth hopes to bridge the gap between theoretical computer scientists and programmers' who have real problems to solve. As with all of Knuth's writings, this book is appreciated not only for the author's unmatched insight, but also for the fun and the challenge of his work, in which he invites us to participate.

What Hacker News says

taericMay 2023

I have tried a few blog posts with literate style code. Some in a notebook style, like https://taeric.github.io/cube-permutations-1.html. in general, that style seems easier nowadays.

There is Stanford GraphBase, and a really good MP3 book that are full programs. Not to mention TeX.

thread

taericMar 2022

https://smile.amazon.com/gp/product/1541259335 is also a great book. As is Stanford GraphBase.

My personal bet is that it is probably easier to collaborate on something like this than you would think. The imposed structure of programs, in general, already makes a lot of collaboration tough.

thread

taericFeb 2021

I actually have made it a point of order to try and pick up all literate programs in book form that I can. This one, is particularly dense, and big. So I have not made too much progress. :(

I have made better progress in the MP3 book. Which, I have enjoyed. Same for the Stanford Graphbase.

It is frustrating, as I am not a fan of c, all told. And I have not found any lisp literate programs. If you know of any, I'd be very interested.

thread

taericJul 2018

Oddly, I prefer a larger file over a myriad of smaller ones. If, line for line, they are the same, then fewer files is my preference.

Not that I want everything in one. Having a sort of chapter concept can help give consumable chunks of a program to understand.

There are several examples, but I'm finding The Stanford GraphBase to be very consumable. Even for somewhat dense c code.

thread

taericJun 2018

I get the impression that is supposed to be somewhat derisive. That said, I think the tools are more usable than people give them credit. They are just slower to get started with.

In particular, I've been picking up The Stanford Graphbase book recently and finding that after I have gotten used to reading more parts, the programs are getting a bit easier to understand. In ways that don't litter my mental model with tons of surface complexity.

What I mean by that is that if you look at the javadoc or "function/method" base of a complete system, it is easy to lose site of the whole. Granted, getting started with the larger texts of some other documents can have similar problems in reverse. It is hard to really get a handle on where in the system you are to start.

thread

theohNov 2017

A related question is "If I had the best professor in the world, what gems would they mention as examples of the beauty of computer science". These things maybe should be on the syllabus, but gems aren't necessarily seen as appropriate stepping stones in a learning process, and may only be accessible to the most capable students. Textbooks also, arguably, rarely offer charismatic enthusiasm or a glimpse of the sublime; they have to adopt a workaday attitude and play it safe.

Things that occur in books that might fit this bill of sublimity; Things that the very best practitioners get excited about:

Cormen names Tarjan's analysis of the complexity of the disjoint set union-find algorithm as his favourite thing[1]. Knuth is an appreciator of Tarjan's algorithm for finding strongly connected components[2]. Tarjan emerges as a contender for the algorithmicist's algorithmicist award.

[1] "It's not an algorithm, but a data structure. I've always marveled at the simple tree-based data structure for disjoint-set union, using union by rank and path compression (Section 21.3 in the third edition of CLRS). The code is amazingly simple, the data structure operations take just barely superlinear time, and the analysis (by Bob Tarjan) blows my mind."

[2] "While I was preparing for Volume 4 of TAOCP in the 90s, I wrote several dozen short routines using what you and I know as "literate programming." Those little essays have been packaged into The Stanford GraphBase (1994), and I still enjoy using and modifying them. My favorite is the implementation of Tarjan's beautiful algorithm for strong components, which appears on pages 512–519 of that book." and

"The data structures that he devised for this problem fit together in an amazingly beautiful way, so that the quantities you need to look at while exploring a directed graph are always magically at your fingertips. And his algorithm also does topological sorting as a byproduct."

Finding this kind of enthusiastic recommendation is always a joy.

thread