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.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.