I would say that the task of detecting circular references in a data structure does not involve sorting at all. Simply walk the data structure/hierarchy/whatever while keeping track of the path you followed to get there.

Here's some untested code to show what I mean:

sub is_circular {
  my $obj = shift; # Object to be traversed
  my $path = shift || [];

  # Check of $obj is in the $path
  foreach my $ancestor (@{$path}) {
    return 1 if $ancestor eq $obj;
  }

  # Check the children recursively, depth first
  # (My imaginary $obj conveniently has 
  # a method for getting an array of its children)
  foreach my $child ($obj->children) {
    return 1 if is_circular($child, [ @{$path}, $obj ] );
  }

  return 0;
}

[download]

This can be done recursively or in a linear fashion if this suits you better. Modules already exist but writing your own code would probably be faster than trying to fit an existing module with your particular data.

-- FloydATC

Time flies when you don't know what you're doing

In reply to Re: Sort mechanics problems with objects and potentially contradicting comparisons (would cause infinite loop) by FloydATC
in thread Sort mechanics problems with objects and potentially contradicting comparisons (would cause infinite loop) by anonymized user 468275

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.