Thore Husfeldt

Images for Karger’s algorithm

with 2 comments

10 repetitions of the contraction procedure. The 5th repetition finds the minimum cut of size 3.

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.

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

Advertisements

Written by thorehusfeldt

September 7, 2012 at 11:26

Posted in Uncategorized

2 Responses

Subscribe to comments with RSS.

  1. could you please provide the python code you wrote for implementing karger’s min cut algorithm using networkx… Thanks

    anon

    October 13, 2012 at 09:54

  2. The Python code for the algorithm itself couldn’t be more beautiful. It’s something like this:

    while(len(G)>2):
    e= random.choice(G.edges())
    G = contract(G, e)

    The only (slight) difficulty is writing the code for contract. (Which is not part of the networkx library.) My own code contains too much cruft for the visualisation (juggling coordinates, unpinning vertex positions, etc.) to be interesting.

    thorehusfeldt

    October 23, 2012 at 17:59


Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: