Combining School and Fun

One of the classes I'm taking right now is the misnamed "Introduction to Graph Theory" (misnamed because it's a graduate course, and therefore hardly introductory). I'm writing some programs that implement some of the algorithms we're discussing in class, and I needed to find some big graphs to test them on. For a large undirected graph, I found the map of the Wing Commander Universe (warning: very large PNG). There are all kinds of things you can do with this graph, like find the shortest route between two star systems, or find the two systems that are the most distant from each other, and so on, along with more esoteric operations like finding a minimum spanning tree. This would be even more interesting if there were data available on how long it took ships to travel from jump-point to jump-point within each system, since the actual jumps are instantaneous, but there isn't. Eventually I might try out a graph layout algorithm on this to see if there's anything better than the standard layout. (The map started out clean and easy to read, but over time more jump-points were charted and added to the map, especially in the area between Sol and Kilrah, and the stars were never moved from their traditional places to make the map easier to read again.)

For a directed graph, I'm considering using the relationships among the mercenaries of Jagged Alliance 2. In this game, you can hire over 60 different mercenaries, each with his or her own distinct personality (and voice). Inevitably, there are personality conflicts, and some obsessed gamer kindly documented them all. Most mercenaries are neutral to each other, but almost every mercenary likes and hates a few others. (If you employ people they like, they're more likely to hire on again at the end of their contract, while being forced to work with people they hate is tough on morale.) Sometimes the feeling is mutual, as with Scope and Sidney (which is good) or with Lynx and Buzz (which is bad, since they hate each other's guts), but as often as not one merc is indifferent to the other or, worse, has the opposite feeling, as with Vicky and Gasket (he's hopelessly in love, and she's not amused). The challenge in the game is to find a group of mercenaries that like each other, or, at worst, are mostly indifferent. Seems to me that a program to find the largest group of mercenaries that doesn't have any "I hate you" relationships would be at least moderately challenging.