Solving a deep recursion problem

punkish has asked for the wisdom of the Perl Monks concerning the following question:

Monks,

My mind is in a bend over what I thought was a simple problem to solve. After many hours of struggling, I am coming to you for light --

I have simple schema

CREATE TABLE node (node_id, <bunch of other node related columns>);
CREATE TABLE edge (edge_id, from_node_id, to_node_id, <bunch of other 
+edge related columns>);
[download]

Note: In spite of edges being terminated in from_node and to_node, they are really not directed.

Given a node_id, I want all the edges that node_id appears in. So far so good. I've got this solved. The problem happens in implementing a limit clause with a difference. I want to be able to limit the number of degrees away from the initial node the query recurses into. In other words, if node 1 is connected to nodes 2 and 3, and 3 is connected to 4 and 5, but if I say limit=1 then only the edges (1,2) and (1,3) are retrieved. If I say limit=2, then besides the above two edges, (3,4) and (3,5) are also retrieved.

I've got some non-working code below. My problem is tracking which iteration I am on.

sub _edges {
  my (%args) = @_;
  
  my $node_id = $args{node_id};
  my $limit   = $args{limit} || 1;
  my $edges   = $args{edges} || [];
  my $iter    = $args{iter}  || 1;
  my $seen    = $args{seen}  || [];
  
  
  if ($iter > $limit) {
    return $edges;
  }

  
    my $sth = $dbh->prepare(qq{
      SELECT e.edge_id, e.to_node_id AS node_id 
      FROM edge e JOIN node n ON e.to_node_id = n.node_id 
      WHERE e.from_node_id = ?
        UNION 
      SELECT e.edge_id, e.from_node_id AS node_id 
      FROM edge e JOIN node n ON e.from_node_id = n.node_id 
      WHERE e.to_node_id = ?
    });
    $sth->execute($node_id, $node_id);
     
    my $res = $sth->fetchall_arrayref({});
    
    push(@$edges, @$res);
    
    foreach my $e (@$res) {
      unless (_seen($seen, [$node_id, $e->{node_id}])) {
        push @$seen, [$node_id, $e->{node_id}];
        _edges(
          dbh        => $dbh, 
          node_id    => $e->{node_id}, 
          node_name  => $e->{node_name}, 
          limit      => $limit, 
          abbreviate => $abbreviate, 
          iter       => $iter, 
          edges      => $edges, 
          seen       => $seen
        );
      }
    }
    $iter++;
  
  return $edges;
}

sub _seen {
  my ($i, $j) = @_;
  
  for (@$i) {
    return 1 if (
      (($_->[0] == $j->[0]) && ($_->[1] == $j->[1])) || 
      (($_->[0] == $j->[1]) && ($_->[1] == $j->[0]))
    );
  }
  
  return 0;
}
[download]

--

when small people start casting long shadows, it is time to go to bed

Comment on Solving a deep recursion problem Select or Download Code

Replies are listed 'Best First'.
Re: Solving a deep recursion problem by pc88mxer (Vicar) on Feb 18, 2008 at 17:43 UTC
For better efficiency I would use a hash instead of your `sub _seen`. Also, I'd organize the algorithm to be something like this: `my %seen; my @nodes = ([$start, 0]); # $start is the starting node while (@nodes) { my ($node, $dist) = @{shift(@nodes)}; my @adj = ...nodes adjacent to $node...; for (@adj) { next if $seen{$_}; $seen{$_} = 1; if ($dist < $MAX) { push(@nodes, [$_, $dist+1]); ...add $_ to list of interesting nodes... } } }` [download] This replaces the recursion with iteration.	[reply] [d/l] [select]
Re: Solving a deep recursion problem by NetWallah (Canon) on Feb 18, 2008 at 18:17 UTC
Untested suggestion: I think the $iter++ is performed too late to be useful. I would suggest changing to : `iter => ++$iter,` [download] in the recursive call. "As you get older three things happen. The first is your memory goes, and I can't remember the other two... " - Sir Norman Wisdom	[reply] [d/l]