Нахождение эйлерова пути в Perl - PullRequest
Новая
       7

Нахождение эйлерова пути в Perl

1 голос
/ 27 октября 2010

У меня есть код, который пытается найти путь Эйлера , как это. Но почему-то это не работает. Что не так с кодом? 

use strict;
use warnings;
use Data::Dumper;
use Carp;

my %graphs = ( 1 => [2,3], 2 => [1,3,4,5], 3 =>[1,2,4,5], 4 => [2,3,5], 5 => [2,3,4]);
my @path = eulerPath(%graphs);

sub eulerPath {
    my %graph = @_;

    # count the number of vertices with odd degree
    my @odd = ();
    foreach my $vert ( sort keys %graph ) {
        my @edg = @{ $graph{$vert} };
        my $size = scalar(@edg);
        if ( $size % 2 != 0 ) {
            push @odd, $vert;
        }
    }

    push @odd, ( keys %graph )[0];

    if ( scalar(@odd) > 3 ) {
        return "None";

    }

    my @stack = ( $odd[0] );
    my @path  = ();

    while (@stack) {
        my $v = $stack[-1];

        if ( $graph{$v} ) {
            my $u = ( @{ $graph{$v} } )[0];
            push @stack, $u;

            # Find index of vertice v in graph{$u}

            my @graphu = @{ $graph{$u} };  # This is line 54.
            my ($index) = grep $graphu[$_] eq $v, 0 .. $#graphu;
            delete @{ $graph{$u} }[$index];
            delete @{ $graph{$v} }[0];

        }
        else {

            push @path, pop(@stack);
        }

    }

    print Dumper \@path;
    return @path;
}

Я получаю ошибку: 

Use of uninitialized value in hash element at euler.pl line 54

Я ожидаю, что он вернет вывод: 

$VAR = [5, 4, 3, 5, 2, 3, 1, 2, 4];

На самом деле я пытался имитировать рабочий код в Python: 

def eulerPath(graph):
    # counting the number of vertices with odd degree
    odd = [ x for x in graph.keys() if len(graph[x])&1 ]
    print odd
    odd.append( graph.keys()[0] )

    if len(odd) > 3:
        return None

    stack = [ odd[0] ]
    path = []

    # main algorithm
    while stack:
        v = stack[-1]
        if graph[v]:
            u = graph[v][0]
            stack.append(u)
            # deleting edge u-v
            #print graph[u][ graph[u].index(v) ]
            #print graph[u].index(v)
            del graph[u][ graph[u].index(v) ]
            del graph[v][0]
        else:
            path.append( stack.pop() )

    return path

stack_ = eulerPath({ 1:[2,3], 2:[1,3,4,5], 3:[1,2,4,5], 4:[2,3,5], 5:[2,3,4] })
print stack_

Ответы [ 2 ]

1 голос
/ 08 января 2012

Я попробовал предложение Outis , и Neversaint работает как надо :)

Wget
http://misccb.googlecode.com/git-history/a4c46aaecbda3c103b92d0152fa2cdbdf4da4ea0/euler.pl

Perl euler.pl

$ VAR1 = [ 5, 4, 3, 5, 2, 3, 1, 2, '4' ];

1 голос
/ 27 октября 2010

В Perl delete не переиндексируется. Из документации Perl :

delete () также может использоваться для массивов и срезов массивов, но его поведение не так просто. Несмотря на то, что exist () вернет false для удаленных записей, удаление элементов массива никогда не изменит индексы существующих значений; используйте для этого shift () или splice ().

Как отмечено в документации, вы можете использовать splice для удаления и переиндексации. 

        my @graphu = @{ $graph{$u} };  # This is line 54.
        my ($index) = grep $graphu[$_] eq $v, 0 .. $#graphu;
        splice @{ $graph{$u} }, $index, 1;
        splice @{ $graph{$v} }, 0, 1;

В дополнение к этому, есть проблема с проверкой, есть ли у узла какие-либо не пройденные пути: 

    my $v = $stack[-1];

    if ( $graph{$v} ) {
        my $u = ( @{ $graph{$v} } )[0];

Одно из различий между Perl и Python состоит в том, что Perl заставляет вас обрабатывать разыменования. $graph{$v} изначально содержит ссылку на массив; пока он продолжает ссылаться на массив, выражение является истинным, и этот тест всегда будет успешным. В соответствующем операторе Python (if graph[v]:) оценивается значение graph[v] (список). Попробуйте: 

    my $v = $stack[-1];

    if ( @{$graph{$v}} ) {
        my $u = ( @{ $graph{$v} } )[0];

при отладке

Я не собираюсь приводить здесь основы отладки Perl (поскольку кто-то уже сделал как часть документации по Perl, и лень может быть хорошей вещью), но краткий обзор кажется в порядке. Суть отладки заключается в проверке данных (так называемое «состояние программы») в программе во время ее работы. Вы можете сделать это с помощью скаффолдинга, который печатает данные в различных точках программы (для этого полезен Dumper), или с помощью интерактивного отладчика для пошагового выполнения программы. Интерактивные отладчики предпочтительнее, потому что они дают вам больше контроля и, как правило, быстрее (если вы не распечатали важный фрагмент данных в коде скаффолда, вам нужно будет перезапустить программу; с отладчиком нет необходимости перезапускать) ,

Используя любую технику, проверьте переменные в вашей подпрограмме eulerPath: @graph, @stack, $v, $u. Сделайте это с вашей исходной программой, промежуточной программой, которая заменяет delete с splice, и с программой, которая вносит все предложенные изменения. Посмотрите, сможете ли вы по данным выяснить, что пошло не так и вызвало ошибки, и что потом привело к изменениям, которые я предложил.

...