traversal.pm

nasm早期的源代码,比较简单是学习汇编和编译原理的好例子

}

sub postorder {
    my $self = shift;
    $self->_order( 'postorder' );
}

sub unseen {
    my $self = shift;
    values %{ $self->{ unseen } };
}

sub seen {
    my $self = shift;
    values %{ $self->{ seen } };
}

sub seeing {
    my $self = shift;
    @{ $self->{ order } };
}

sub roots {
    my $self = shift;
    @{ $self->{ roots } };
}

sub is_root {
    my ($self, $v) = @_;
    for my $u (@{ $self->{ roots } }) {
	return 1 if $u eq $v;
    }
    return 0;
}

sub tree {
    my $self = shift;
    $self->{ tree };
}

sub graph {
    my $self = shift;
    $self->{ graph };
}

sub vertex_by_postorder {
    my ($self, $i) = @_;
    exists $self->{ postorder } && $self->{ postorder }->[ $i ];
}

sub postorder_by_vertex {
    my ($self, $v) = @_;
    exists $self->{ postordern } && $self->{ postordern }->{ $v };
}

sub postorder_vertices {
    my ($self, $v) = @_;
    exists $self->{ postordern } ? %{ $self->{ postordern } } : ();
}

sub vertex_by_preorder {
    my ($self, $i) = @_;
    exists $self->{ preorder } && $self->{ preorder }->[ $i ];
}

sub preorder_by_vertex {
    my ($self, $v) = @_;
    exists $self->{ preordern } && $self->{ preordern }->{ $v };
}

sub preorder_vertices {
    my ($self, $v) = @_;
    exists $self->{ preordern } ? %{ $self->{ preordern } } : ();
}

sub has_state {
    my ($self, $var) = @_;
    exists $self->{ state } && exists $self->{ state }->{ $var };
}

sub get_state {
    my ($self, $var) = @_;
    exists $self->{ state } ? $self->{ state }->{ $var } : undef;
}

sub set_state {
    my ($self, $var, $val) = @_;
    $self->{ state }->{ $var } = $val;
    return 1;
}

sub delete_state {
    my ($self, $var) = @_;
    delete $self->{ state }->{ $var };
    delete $self->{ state } unless keys %{ $self->{ state } };
    return 1;
}

1;
__END__
=pod

=head1 NAME

Graph::Traversal - traverse graphs

=head1 SYNOPSIS

Don't use Graph::Traversal directly, use Graph::Traversal::DFS
or Graph::Traversal::BFS instead.

    use Graph;
    my $g = Graph->new;
    $g->add_edge(...);
    use Graph::Traversal::...;
    my $t = Graph::Traversal::...->new(%opt);
    $t->...

=head1 DESCRIPTION

You can control how the graph is traversed by the various callback
parameters in the C<%opt>.  In the parameters descriptions below the
$u and $v are vertices, and the $self is the traversal object itself.

=head2 Callback parameters

The following callback parameters are available:

=over 4

=item tree_edge

Called when traversing an edge that belongs to the traversal tree.
Called with arguments ($u, $v, $self).

=item non_tree_edge

Called when an edge is met which either leads back to the traversal tree
(either a C<back_edge>, a C<down_edge>, or a C<cross_edge>).
Called with arguments ($u, $v, $self).

=item pre_edge

Called for edges in preorder.
Called with arguments ($u, $v, $self).

=item post_edge

Called for edges in postorder.
Called with arguments ($u, $v, $self).

=item back_edge

Called for back edges.
Called with arguments ($u, $v, $self).

=item down_edge

Called for down edges.
Called with arguments ($u, $v, $self).

=item cross_edge

Called for cross edges.
Called with arguments ($u, $v, $self).

=item pre

=item pre_vertex

Called for vertices in preorder.
Called with arguments ($v, $self).

=item post

=item post_vertex

Called for vertices in postorder.
Called with arguments ($v, $self).

=item first_root

Called when choosing the first root (start) vertex for traversal.
Called with arguments ($self, $unseen) where $unseen is a hash
reference with the unseen vertices as keys.

=item next_root

Called when choosing the next root (after the first one) vertex for
traversal (useful when the graph is not connected).  Called with
arguments ($self, $unseen) where $unseen is a hash reference with
the unseen vertices as keys.  If you want only the first reachable
subgraph to be processed, set the next_root to C<undef>.

=item start

Identical to defining C<first_root> and undefining C<next_root>.

=item next_alphabetic

Set this to true if you want the vertices to be processed in
alphabetic order (and leave first_root/next_root undefined).

=item next_numeric

Set this to true if you want the vertices to be processed in
numeric order (and leave first_root/next_root undefined).

=item next_successor

Called when choosing the next vertex to visit.  Called with arguments
($self, $next) where $next is a hash reference with the possible
next vertices as keys.  Use this to provide a custom ordering for
choosing vertices, as opposed to C<next_numeric> or C<next_alphabetic>.

=back

The parameters C<first_root> and C<next_successor> have a 'hierarchy'
of how they are determined: if they have been explicitly defined, use
that value.  If not, use the value of C<next_alphabetic>, if that has
been defined.  If not, use the value of C<next_numeric>, if that has
been defined.  If not, the next vertex to be visited is chose randomly.

=head2 Methods

The following methods are available:

=over 4

=item unseen

Return the unseen vertices in random order.

=item seen

Return the seen vertices in random order.

=item seeing

Return the active fringe vertices in random order.

=item preorder

Return the vertices in preorder traversal order.

=item postorder

Return the vertices in postorder traversal order.

=item vertex_by_preorder

    $v = $t->vertex_by_preorder($i)

Return the ith (0..$V-1) vertex by preorder.

=item preorder_by_vertex

    $i = $t->preorder_by_vertex($v)

Return the preorder index (0..$V-1) by vertex.

=item vertex_by_postorder

    $v = $t->vertex_by_postorder($i)

Return the ith (0..$V-1) vertex by postorder.

=item postorder_by_vertex

    $i = $t->postorder_by_vertex($v)

Return the postorder index (0..$V-1) by vertex.

=item preorder_vertices

Return a hash with the vertices as the keys and their preorder indices
as the values.

=item postorder_vertices

Return a hash with the vertices as the keys and their postorder
indices as the values.

=item tree

Return the traversal tree as a graph.

=item has_state

    $t->has_state('s')

Test whether the traversal has state 's' attached to it.

=item get_state

    $t->get_state('s')

Get the state 's' attached to the traversal (C<undef> if none).

=item set_state

    $t->set_state('s', $s)

Set the state 's' attached to the traversal.

=item delete_state

    $t->delete_state('s')

Delete the state 's' from the traversal.

=back

=head2 Backward compatibility

The following parameters are for backward compatibility to Graph 0.2xx:

=over 4

=item get_next_root

Like C<next_root>.

=item successor

Identical to having C<tree_edge> both C<non_tree_edge> defined
to be the same.

=item unseen_successor

Like C<tree_edge>.

=item seen_successor

Like C<seed_edge>.

=back

=head2 Special callbacks

If in a callback you call the special C<terminate> method,
the traversal is terminated, no more vertices are traversed.

=head1 SEE ALSO

L<Graph::Traversal::DFS>, L<Graph::Traversal::BFS>

=head1 AUTHOR AND COPYRIGHT

Jarkko Hietaniemi F<[e-mail]>

=head1 LICENSE

This module is licensed under the same terms as Perl itself.

=cut