Finding the longest road in a Settlers of Catan game algorithmically

Question

I'm writing a Settlers of Catan clone for a class. One of the extra credit features is automatically determining which player has the longest road. I've thought about it, and it seems like some slight variation on depth-first search could work, but I'm having trouble figuring out what to do with cycle detection, how to handle the joining of a player's two initial road networks, and a few other minutiae. How could I do this algorithmically?

For those unfamiliar with the game, I'll try to describe the problem concisely and abstractly: I need to find the longest possible path in an undirected cyclic graph.

Answer 1

This should be a rather easy algorithm to implement.

To begin with, separate out the roads into distinct sets, where all the road segments in each set are somehow connected. There's various methods on doing this, but here's one:

1. Pick a random road segment, add it to a set, and mark it
2. Branch out from this segment, ie. follow connected segments in both directions that aren't marked (if they're marked, we've already been here)
3. If found road segment is not already in the set, add it, and mark it
4. Keep going from new segments until you cannot find any more unmarked segments that are connected to those currently in the set
5. If there's unmarked segments left, they're part of a new set, pick a random one and start back at 1 with another set

Note: As per the official Catan Rules, a road can be broken if another play builds a settlement on a joint between two segments. You need to detect this and not branch past the settlement.

Note, in the above, and following, steps, only consider the current players segments. You can ignore those other segments as though they weren't even on the map.

This gives you one or more sets, each containing one or more road segments.

Ok, for each set, do the following:

1. Pick a random road segment in the set that has only one connected road segment out from it (ie. you pick an endpoint)
2. If you can't do that, then the whole set is looping (one or more), so pick a random segment in this case

Now, from the segment you picked, do a recursive branching out depth-first search, keeping track of the length of the current road you've found so far. Always mark road segments as well, and don't branch into segments already marked. This will allow the algorithm to stop when it "eats its own tail".

Whenever you need to backtrack, because there are no more branches, take a note of the current length, and if it is longer than the "previous maximum", store the new length as the maximum.

Do this for all the sets, and you should have your longest road.