Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
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.

blokhead


In reply to Re: OT(ish) - Best Search Algorithm by blokhead
in thread OT(ish) - Best Search Algorithm by Melly

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • 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! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, 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, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &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.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others exploiting the Monastery: (6)
    As of 2014-10-02 05:01 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      What is your favourite meta-syntactic variable name?














      Results (49 votes), past polls