view release on metacpan or  search on metacpan

t/03rand.t  view on Meta::CPAN

        LEFT JOIN temp_dfa_path p2
          ON (p1.rowid + 1 = p2.rowid)
        LEFT JOIN view_transitions_as_5tuples v
          ON (v.src_state = p1.state AND
            (v.dst_state = p2.state
               OR (v.via IS NULL AND v.dst_state = v.src_state)))
    WHERE v.dst_state IS NOT NULL
  });

  $dfa->_dbh->rollback();

  return @result;
}

for ( 1 .. 100 ) {
  my $g = random_graph();
  my $start = random_element( $g->vertices );
  my $final = random_element($start, $g->all_successors($start));

  my %nullable;
  $nullable{ $_ } = rand() < $nullable_odds for $g->vertices;

  my %matches;
  for my $v ($g->vertices) {
    next if $nullable{$v};
    for my $ch (@alphabet) {
      $matches{$v}{$ch} = rand() < $matches_odds;
    }
    $matches{$v}{random_element( @alphabet )} = 1;
  }

  my ($dfa, $start_id) = get_dfa($g, $start, $final,
    \%nullable, \%matches);

  my @accepting = $dfa->cleanup_dead_states(sub {
    scalar grep { $_ eq $final } @_;
  });

  my %accepting_id = map { $_ => 1 } @accepting;

  ok scalar(@accepting), 'at least 1 accepting state';

  my $dead_state_id = $dfa->dead_state_id;

  for my $dfa_path_counter ( 1 .. 16 ) {
    my @dfa_path = random_dfa_path($dfa, $start_id, 100, @accepting);

    next unless @dfa_path > 1;

    my @xxx = dfa_path_join_5tuple($dfa, @dfa_path);

    ok((any {
    my ($dst_pos, $dst_state, $dst_vertex) = @{$_}[4,5,6];
      1
      and $dst_pos == @dfa_path
      and $dst_vertex eq $final
      and grep { $_ eq $dst_state } @accepting
    } @xxx), "joined 5tuples contain final");

    ok((all { $g->has_edge($_->[2], $_->[6] ) } @xxx),
      "random dfa path corresponds to original graph over 5tuples");
  }

  my %all_transitions = map {
    join(" ", @$_) => 1
  } $dfa->transitions_as_3tuples;

  for my $path_counter ( 1 .. 16 ) {

    my @path = random_path_between($g, $start, $final, 32);

    ok @path > 0, "found random path in graph";
    is $path[0], $start, "random path begins with start vertex";
    is $path[-1], $final, "random paths ends with final vertex";

    my @inputs = inputs_from_vertex_path(\%matches,
      \%nullable, @path);

    my @dfa_trail = simulate_dfa_on_input($dfa, $start_id, @inputs);

    my $last_state = @dfa_trail ? $dfa_trail[-1][3] : $start_id;
    my $last_accepts = grep { $_ eq $last_state } @accepting;

    ok $last_accepts, "DFA accepts random path $path_counter";

    my %trail_transitions = map {
      join(" ", @{$_}[1,2,3]) => 1
    } @dfa_trail;

    ok((all { exists $all_transitions{$_} } keys %trail_transitions),
      "proper computation of trail transitions and all transitions");

    my @dfa_path = ($start_id, map { $_->[3] } @dfa_trail);

    my %dfa_vertices = do {
      my $i = 0;
      map {
        $i++;
        map { join(" ", ($i - 1, $_)), 1 } $dfa->vertices_in_state($_)
      } @dfa_path;
    };

    my %vpp = map { join(" ", @$_), 1 }
      path_to_vertex_pos_pairs(\%nullable, @path);

    ok((all { exists $dfa_vertices{$_} } keys %vpp),
      "vertex path corresponds to dfa trail plus vertices");
  }

}

done_testing();

__END__