PCPlus 287: Calculate degrees of separation

In a week when I completed writing my 50th article for PC Plus, it’s kind of fitting to also republish a hoot of an article that I really enjoyed researching.

PCPlus logoAbout Bacon numbers.

Yes, it’s got Computer Science and it’s got Bacon. What more could any geek want? OK, it’s Bacon as in actor and not tasty porcine food, but at least the editors tossed in a gratuitous shot of some bacon on a fork. Betcha a bunch of PC Plus readers at least read the first few paragraphs...

The Bacon number is the basis of a fun trivia game: someone names an actor and everyone then has to work out the shortest number of steps between Kevin Bacon and that actor (the Bacon number), where a “step” is counted to mean “appeared in the same movie”. So if I say Tom Hardy as the actor (he played Eames in Inception) what’s the smallest number of linked movies before you get to Kevin Bacon? (The Oracle of Bacon suggests a Bacon number of 2: Tom Hardy was in Star Trek: Nemesis with J. Patrick McCormak, who was in Hollow Man with... Kevin Bacon.)

Although a fun pub game, there’s some Computer Science behind it. Graph theory to be general; and shortest path algorithms to be precise. Once you have a network of links and nodes (edges and vertices in the Graph Theory vernacular), given two nodes, how do you find the shortest path between them by counting the links?

The article then goes on to Dijkstra’s algorithm which considers the same problem, but now each link has a “weight” or a “cost” associated with it. Now you need to try and find the path between two nodes with the least weight or cost. Such algorithms are at the heart of route planning systems in GPS units.

This article first appeared in issue 287, November 2009. It was also published online at techradar.com.

You can download the PDF here.

Album cover for Forever's a Long Long TimeNow playing:
Orquestra Was - Excuse Me, Colonel. Could I Borrow Your Newspaper?
(from Forever's a Long Long Time)

Loading similar posts...   Loading links to posts on similar topics...

No Responses

Feel free to add a comment...

Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

  •  Emphasize with italics: surround word with underscores _emphasis_
  •  Emphasize strongly: surround word with double-asterisks **strong**
  •  Link: surround text with square brackets, url with parentheses [text](url)
  •  Inline code: surround text with backticks `IEnumerable`
  •  Unordered list: start each line with an asterisk, space * an item
  •  Ordered list: start each line with a digit, period, space 1. an item
  •  Insert code block: start each line with four spaces
  •  Insert blockquote: start each line with right-angle-bracket, space > Now is the time...
Preview of response