Construct Graph from a Degree Sequence

A degree sequence is a sequence of numbers representing the degrees of the vertices of a graph; it is typically presented in descending arrangment, such as {4,4,3,3,2,2}. That degree sequence corresponds to a graph with 6 vertices (A,B,C,D,E,F, let's call them) with the edges: A-B, A-C, A-D, A-E, B-A, B-C, B-D, B-F, C-A, C-B, C-E, D-A, D-B, D-F, E-A, E-C, F-B, F-D. As you can see, A has 4 edges, B has 4 edges, C has 3 edges, D has 3 edges, E has 2 edges, and F has 2 edges. It is possible to have multiple distinct graphs with the same degree sequence ({2,2,2,1,1} is the example shown at the above URL). This function only produces one.

sub graph_from_degree_sequence {
  # create edge hash and empty graph
  my $v = 'a';
  my %e = map +($v++ => $_), @_;
  my %g;

  # algorithm is as follows:

  while (1) {
    # sort the vertices of the graph by degree (high to low)
    my @order = sort { $e{$b} <=> $e{$a} } keys %e;

    # if the degree of the vertex with the highest
    # degree is zero, then we're done
    last if $e{$order[0]} == 0;

    # otherwise, connect this vertex to the next N
    # vertices (in order of their degrees), where N is
    # the degree of the vertex with the highest degree
    for (1 .. $e{$order[0]}) {
      # decrement the connected vertex's degree, and
      # check to see if it's less than zero -- if it
      # is, this degree sequence cannot produce a graph
      --$e{$order[$_]} < 0 and return;

      # create the edges between the two
      push @{ $g{$order[0]} }, $order[$_];
      push @{ $g{$order[$_]} }, $order[0];
    }

    # set the degree of this vertex to zero, which
    # means it is not to be connected to anymore
    $e{$order[0]} = 0;
  }

  return \%g;
}
[download]

The code could be modified to remove completed vertices from %e, and then check to ensure that the degree of the vertex with the highest degree is equal to or less than the number of eligible vertices:

sub graph_from_degree_sequence {
  my $v = 'a';
  my %e = map +($v++ => $_), @_;
  my %g;

  while (1) {
    # this will only have non-zero-degree vertices
    my @order = sort { $e{$b} <=> $e{$a} } keys %e

      # if there aren't any, we're done
      or last;

    # if there aren't enough available vertices to
    # connect to, this degree sequence is no good
    return if @order < $e{$order[0]};

    for (1 .. $e{$order[0]}) {
      # each vertex's degree is guaranteed to be at
      # least 1, so if it becomes 0, make it ineligible
      --$e{$order[$_]} or delete $e{$order[$_]};

      # create the edges between the two
      push @{ $g{$order[0]} }, $order[$_];
      push @{ $g{$order[$_]} }, $order[0];
    }

    delete $e{$order[0]};
  }

  return \%g;
}
[download]

This second method seems to be faster than the first method in most cases. The trade is deleting hash elements, instead of sorting extra values that can't be used, and (through benchmarking) it appears to pay off.

Comment on Construct Graph from a Degree Sequence Select or Download Code

Replies are listed 'Best First'.
Re: Construct Graph from a Degree Sequence by Zaxo (Archbishop) on Jun 18, 2005 at 03:10 UTC
I think this would go well using the Graph module. It would be more self-documenting, and would seperate the algorithm from the graph representation. I'll try a translation if you like. After Compline, Zaxo	[reply]
Re^2: Construct Graph from a Degree Sequence by japhy (Canon) on Jun 18, 2005 at 16:22 UTC
I had emailed Jarkko when I posted this; I haven't heard back from him. You and I both could translate and compare. Kind of like L~R's "Perl time capsule" thing. One thing to add to the algorithm, which I forgot, is a quick check to ensure the sum of the degrees is even. Silly me. Jeff `japhy` Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and `perl` hacker How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart	[reply]
Re^2: Construct Graph from a Degree Sequence by japhy (Canon) on Jun 20, 2005 at 21:29 UTC
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] Jeff `japhy` Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and `perl` hacker How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart	[reply] [d/l]