Here's my first attempt; it's got some extra goodies in it, but the premise is pretty much the same. The only real abstraction is the creation of the graph. The mechanics of the algorithm are still here:

# my $g = Graph->new_from_degree_sequence(\@degrees, \@vertices);
# my ($g, $iters) = Graph->new_from_degree_sequence(\@deg, \@vert);
# the vertices are optional

sub new_from_degree_sequence {
  my ($class, $deg, $vert) = @_;
  my $sorted = 1;

  # determine the sortedness of the degree sequence,
  # and do a checksum while we're at it
  {
    my $odd = $deg->[0] & 1;

    for (1 .. $#$deg) {
      $sorted &&= 0 if $deg->[$_] > $deg->[$_-1];
      $odd = !$odd if $deg->[$_] & 1;
    }

    $@ = "sum of degrees (@$deg) is odd", return if $odd;
  }

  # determine if the vertices are references,
  # and install default vertex names if needed
  my $ref = 0;
  if ($vert) { for (@$vert) { $ref = 1, last if ref } }
  else { $vert = [map chr(64 + $_), 1 .. @$deg] }

  # create the graph, and store the vertex-degree info
  my $graph = Graph::Undirected->new(vertices => $vert, refvertexed =>
+ $ref);
  my @v = map [$vert->[$_], $deg->[$_]], 0 .. $#$vert;

  my $iter = 0;

  # continue while there are still vertices left to connect
  # only sort the remaining vertices if they weren't already sorted
  while (@v and ($sorted ||= (@v = sort { $b->[1] <=> $a->[1] } @v))) 
+{
    # if we don't have enough vertices, stop
    $@ = "impossible degree sequence (@$deg)", return if @v < $v[0][1]
+;

    ++$iter;

    # connect the vertex with the highest degree (N)
    # to N other vertices with the highest degrees
    for (my $i = $v[0][1]; $i >= 1; --$i) {
      $graph->add_edge($v[0][0], $v[$i][0]);
      --$v[$i][1] or splice @v, $i, 1;
    }

    shift @v;

    # see if the remaining vertices need sorting
    for (1 .. $#v) { $sorted = 0, last if $v[$_][1] > $v[$_-1][1] }
  }

  return wantarray ? ($graph, $iter) : $graph;
}
[download]

---

---

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.