view release on metacpan or  search on metacpan

lib/App/War.pm  view on Meta::CPAN

    $self->{items} ||= [];
    if (@_) {
        $self->{items} = [shuffle @_];
    }
    return @{ $self->{items} };
}

=head2 $war->rank

Starts the process of uniquely ordering the graph vertices.  This method
calls method C<tsort_not_unique> until it returns false, I<i.e.> we have a
unique topo sort.

=cut

sub rank {
    my $self = shift;
    while (my $v = $self->tsort_not_unique) {
        $self->compare($v->[0], $v->[1]);
    }
    return $self;
}

=head2 $war->tsort_not_unique

This method returns a true value (more on this later) if the graph
currently lacks a unique topo sort.  If the graph B<has> a unique sort, the
"war" is over, and results should be reported.

If the graph B<lacks> a unique topological sort, this method returns an
arrayref containing a pair of vertices that have an ambiguous ordering.
From L<http://en.wikipedia.org/wiki/Topological_sorting>:

=over 4

lib/App/War.pm  view on Meta::CPAN

topological sort order is unique; no other order respects the edges of the
path.

=back

This property of the topological sort is used to ensure that we have a
unique ordering of the "combatants" in our "war".

=cut

sub tsort_not_unique {
    my $self = shift;

    # search for unordered items by calculating the topological sort and
    # verifying that adjacent items are connected by a directed edge

    my @ts = $self->graph->topological_sort;

    for my $i (0 .. $#ts - 1) {
        my ($u,$v) = @ts[$i,$i+1];
        if (!$self->graph->has_edge($u,$v)) {

t/11-tsort.t  view on Meta::CPAN

use warnings FATAL => 'all';
use Test::More tests => 4;

use_ok('App::War');

my @items = qw{ apricot barista cargo };

my $war = App::War->new(items => \@items)->init;
ok($war);

ok($war->tsort_not_unique);

# resolve the graph
$war->graph->add_edge(0,1);
$war->graph->add_edge(1,2);
ok(!$war->tsort_not_unique);