I presented Karger’s algorithm in class on Monday, and was a bit disappointed by the available illustrations of this beautiful algorithm, and graph contractions in general, in textbooks and on the web.

I think a lot of “free” intuition about an algorithm is gained from just seeing it run, and this particular algorithm is hard to do well on the blackboard. You need a big enough enough instance, which you need to update several times (requiring eraser work and covering you in dust), and then you’d have to repeat the whole thing several times.

So I spent some time drawing these illustrations myself. I implemented the algorithm in Python, using the nifty networkx library. The graphs are quite well laid out using neato from the graphviz package. For each contraction I pinned the other nodes, made the midpoint of the two contracted nodes the new starting point of the new, merged node, and let neato’s embedder move that new node around. (Though I ended up laying out the initial graph by hand, which is just so much nicer.)

Networkx lets you display graphs in mathplotlib, which works moderately well. I even had an animated run for the lecture. Sexy stuff. (But I’ve become somewhat soured on animations. Good, static “animations” of all the steps in an algorithm are much more instructive, a lesson I’ve learned from looking at the amazing illustrations appearing in the textbooks of Robert Sedgewick and Kevin Wayne.)

Mathplotlib doesn’t do curved edges, though. So in the end I wrote a bit more code that transforms a networkx graph (with layout) to a TikZ picture. The result is run trough LaTeX, converted to SVG, and Bob’s your uncle. Or Dave, in this case. Phew.

Uploaded to Wikimedia Commons, free to use and modify with attribution.

• File:10_repetitions_of_Karger’s_contraction_procedure.svg
• File:Single_run_of_Karger’s_Mincut_algorithm.svg
• File:Edge_contraction_in_a_multigraph.svg

By the way, the Wikipedia entry for Karger’s algorithm is not in good shape. (But does contain the images now…)