First off, I know this response is not going to solve your problem. I do not know of an implementation you can use immediately. I do know that Graph::Base has some useful methods that you could use in writing your own solution. For example, methods are available to return biconnectedness and mean density statistics.

The only information (I'm no expert on graph theory!) that I can add to the NP-completeness issue comes from Steven S. Skiena's excellent The Algorithm Design Manual, page 324, which provides a thorough overview of this class of problem, including references to implementations.

"For sufficiently dense graphs, there always exists at least one Hamiltonian cycle, and further, such a cycle can be found quickly. An efficient algorithm for finding a Hamiltonian cycle in a graph where all vertices have degree >= n/2 is given in U. Manber. Introduction to Algorithms."

Here's hoping that your graphs are sufficiently dense! Happy solving.

In reply to Re: Re: Largest cycle in the graph by welchavw
in thread Largest cycle in the graph by artist

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!
  • 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! —
  • 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:
    & &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.