NAME

Graph::DFS - a base class for depth-first graph traversal

SYNOPSIS

use Graph;

my $graph = Graph->new;

# ... fill $graph ...

use Graph::DFS;

$df = Graph::DFS->new( { ... } );

# Either...

$df->( $graph ); # process all of it

# ...or

while ( $vertex = $df->( $graph ) )  {
    # do something about the $vertex ...
}

DESCRIPTION

This class contains various methods for graph depth-first traversal, applicable by the Graph class.

Currently only one method is defined: the constructor new.

CONSTRUCTOR

The constructor new compiles a state machine that knows how to walk Graphs using depth-first traversal. The state machine is returned as an anonymous subroutine.

You can (and you probably will want to) pass parameters to the compilation of the state machine. You can walk the graph either in single steps or iteratively.

For example to print out all the vertices of the graph you can use either:

$df = Graph::DFS->
          new( { for_vertex => sub { my $vertex = shift;
                                        print "vertex = $vertex\n" } } );

$df->( $graph );

or

$df = Graph::DFS->
          new( { return_vertex => 1 } );

while( $vertex = $df->( $graph ) ) {
    print "vertex = $vertex\n"
}

for_vertex runs the anonymous subroutine for each vertex while return_vertex being true causes each vertex to be returned iteratively. return_vertex could also be an anonymous subroutine in which case the result of calling it with the vertex as the argument of the anon sub would be returned.

The vertices are returned in the order they are met: this is in effect the preorder of the graph.

Analogous `hooks' (callbacks) exist for

edges: as each edge is seen: for_edge and return_edge

roots: each tree of the depth-first forest has a root vertex: for_root and return_root

paths: a path is ready when the depth-first traversal can proceed no deeper: for_path and return_path

done vertices: a vertex is `done' when it no more has unseen descendant vertices: for_done_vertex and return_done_vertex This is in effect the postorder of the graph.

In addition to these hooks each vertex gets two integer `timestamps' as attributes (see Graph): Seen and Done. The timestamps correspond to for_vertex, for_done_vertex. Two additional timestamps called SeenG and DoneG record the `global' timestamps of the whole traversal.

        $g = Graph->new;

	$g->add_edges(qw(a b b c b d d e));

        $w = Graph::DFS->new;

        $w->( $g );

        foreach $v ( sort $g->vertices ) {
            print $v, " ", $v->Seen,  " ", $v->Done,
                      " ", $v->SeenG, " ", $v->DoneG, "\n";
        }

should output the following

a 0 4 0 9
b 1 3 1 8
c 2 0 2 3
d 3 2 4 7
e 4 1 5 6

SEE ALSO

Graph.

VERSION

See Graph.

AUTHOR

Jarkko Hietaniemi <jhi@iki.fi>

COPYRIGHT

Copyright 1998, O'Reilly and Associates.

This code is distributed under the same copyright terms as Perl itself.