note
blokhead
Here is a simple approach:
<p>
Say your starting vertex is A. First, find the [http://mathworld.wolfram.com/BiconnectedGraph.html|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:
<p>
<ul><li>
Two vertices are in the same biconnected component if and only if there is a cycle in the graph that visits both.
</ul>
<p>
Now that you have A's biconnected component, there are a few cases:
<p>
<ul>
<li> 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.
<li> 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).
<li> 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).
</ul>
<p>
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 [mod://Graph].pm, it has a method for computing biconnected components, and that will be the main step in this algorithm.
<p>
Now, if you are interested in finding the <i>smallest</i> 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.
<!-- Node text goes above. Div tags should contain sig only -->
<div class="pmsig"><div class="pmsig-137386">
<p>
blokhead
</div></div>
644868
644868