BFS set of a graph G=(V, E). (II)

[Marko Riedel <mriedel@neuearbeit.de>]

Greetings.

The BSF routine that I posted (message "BFS set of a graph G=(V, E).") 
computes a hash table at every iteration of a loop although the hash
table never changes. I fixed this in the version that is included with
this message.

Regards,

Marko Riedel

sub bfs {
  my ($g, $marked, $stack, $perm, $perms) = @_;
  my ($n) = (scalar @$g);

  if(not defined $marked){
    $perms = {}; $marked = [0 x $n]; 
    for(my $i=0; $i<$n; $i++){
      $marked->[$i] = 1;
      bfs($g, $marked, 0, [$i], $perms);
      $marked->[$i] = 0;
    }
    return $perms;
  }

  my (%next);
  for(my $j=$stack; $j<scalar @$perm; $j++){
    foreach my $v (@{ $g->[$perm->[$j]]}){
      $next{$v} = 1 if not $marked->[$v];
    }
  }

  foreach my $v (keys %next){
    $marked->[$v] = 1;
  }

  my ($stackperms) = permute([@$perm[$stack..$#$perm]]);
  foreach my $stackperm (@$stackperms){
    @$perm[$stack..$#$perm] = @$stackperm;

    if(scalar @$perm==$n){
      $perms->{"@$perm"} = $perm;
      next;
    }

    bfs($g, $marked, scalar @$perm, [@$perm, keys %next], $perms);
  }

  foreach my $v (keys %next){
    $marked->[$v] = 0;
  }

  return;
}