#!/usr/bin/perl

# edge_classify
#
#       @C = $G->edge_classify()
#
#       Returns the edge classification as a list where each element
#       is a triplet [$u, $v, $class], the $u, $v being the vertices
#       of an edge and $class being the class.
#
sub edge_classify {
    my $G = shift;

    my $unseen_successor =
        sub {
            my ($u, $v, $T) = @_;

            # Freshly seen successors make for tree edges.
            push @{ $T->{ edge_class_list } },
                 [ $u, $v, 'tree' ];
        };
    my $seen_successor =
        sub {
            my ($u, $v, $T) = @_;

            my $class;

            if ( $T->{ G }->directed ) {
                $class = 'cross'; # Default for directed nontree edges.

                unless ( exists $T->{ vertex_finished }->{ $v } ) {
                    $class = 'back';

                } elsif ( $T->{ vertex_found }->{ $u } <
                          $T->{ vertex_found }->{ $v }) {
                    $class = 'forward';
                }
            } else {
                # No cross nor forward edges in
                # an undirected graph, by definition.
                $class = 'back';
            }

            push @{ $T->{ edge_class_list } }, [ $u, $v, $class ];
        };
    use Graph::DFS;
    my $d =
        Graph::DFS->
            new( $G,
                 unseen_successor => $unseen_successor,
                 seen_successor   => $seen_successor,
                 @_);

    $d->preorder; # Traverse.

    return @{ $d->{ edge_class_list } };
}