ashacat came home Thursday with the most devious homework problem yet from her programming for Anthropologist class. When I say most devious homework problem yet I mean that her Prof. has upped the difficulty level by, um two orders of magnitude. The previous 'hardest' assignment was along the lines of 'define two matrices, add their contents together and store in a 3rd matrix', or 'read a file from disk and write it out to both the screen and a new disk file'. This week's challenge is: take a kinship diagram for a community and determine an index of relatedness for each married couple'. Gork?

So, we got to talking about it over dinner with taichigeek. A kinship diagram is like a family tree, only its for all the families in a given community. An 'index of relatedness' is how many steps you have to go to find a common ancestor. The idea is that couples with a high degree of relatedness indicate a community that does a lot of cousin marriages vs. a community with a lot of outsider marriages. A kinship diagram is essentially a network of nodes, each node being a person. Generating an index of relatedness is essentially computing a shortest-path from one spouse-node to the other (and no, you can't go via the kids, you have to look 'up' to the ancestors). Calculating a shortest path through a network can only mean one thing: Dijkstra.

Edsger Dijkstra was a Dutch computer scientist who passed away in 2002. The contribution that makes his name a household word among network geeks is Dijkstra's algorithm. There are other methods for computing the shortest path through a network, but Dijkstra's algorithm is just about the most efficient there is. So efficient that pretty much every network routing protocol sophisticated enough to do more than merely count hops uses Dijkstra (e.g. OSPF, and ATM's PNNI to name two).

I've always wondered wondered how the guts of Dijkstra's algorithm actually worked. Seriously, how could I resist? I spent a chunk of last night and a couple hours this morning banging out first a Perl script that used Dijkstra to generate shortest-path routes through a network of nodes, and then twisting it to meet the particular requirements of this kinship mapping assignment. This page (Comp150PPP Assignment 2) was particularly helpful.

The full-on kinship mapping version is something of a train wreck (if I were writing it for production and not as a teaching aide for Asha I'd use a SQL database and not a mish-mash of text files and arrays, but the class is pretty basic, so nothing too complicated). If you'd like a real April fool's gag, you can examine what I loosely refer to as my coding style: the basic Dijkstra program, input file, and output.

Oh, and we made two runs to the dump and cut down last year's ornamental grasses here. And then it rained.

Joie de geek or Je ne sais dork - you be the judge.