Re: OT(ish) - Best Search Algorithm

[blokhead]

Here is a simple approach:

Say your starting vertex is A. First, find the biconnected component containing A. Biconnectivity means that there is no single vertex whose removal would disconnect the graph. But a consequence of this condition is what we're really looking for:

• Two vertices are in the same biconnected component if and only if there is a cycle in the graph that visits both.

Now that you have A's biconnected component, there are a few cases:

• The component contains just the single vertex A. This means A has 0 or 1 friends, and a cycle of your definition is not possible.
• The component has more than just A, but A is immediate friends with everyone in the component. Then all of A's non-immediate friends are outside of this component and therefore do not share a common cycle with A. This means that there is no cycle of your definition (you insist that the cycle visit a non-immediate-friend of A).
• Otherwise, there is a non-immediate friend of A within the component, say B. By the definition of biconnectivity, there is a cycle that visits both A and B. You can find it by any sort of search (breadth-first or depth-first) from A. Just find two vertex disjoint paths from A to B. You can restrict your search to within this biconnected component for efficiency (the cycle connecting the two vertices must stay within the biconnected component).

Sorry this is at such a high level with no code ;), but I think you should have no problem, if you were already considering implementing A* search on your own. Check out Graph.pm, it has a method for computing biconnected components, and that will be the main step in this algorithm.

Now, if you are interested in finding the smallest such cycle, I'm not sure exactly how to do it. You might want to find the non-immediate-friend of A who is closest to A, and use him as the basis of your cycle. But I don't think this is guaranteed to give the shortest cycle overall. But it would at least be a reasonable heuristic.