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

1

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

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_
  • 0
    В чем ошибка? Какой выход вы получаете? Работает ли код Python? Вы пробовали отладку? -1 за очень неполный вопрос.
  • 0
    Да, код Python работает. Ошибка обновлена выше.
Показать ещё 1 комментарий
Теги:
algorithm
graph-theory

2 ответа

1
Лучший ответ

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

delete() также может использоваться на массивах и средах массива, но его поведение менее прямолинейно. Хотя exists() вернет 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;

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

    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, а laziness может быть хорошей вещью), но краткий обзор выглядит по порядку. Суть отладки заключается в анализе данных (ака "состояние программы" ) в программе по мере ее запуска. Вы можете сделать это с помощью лесов, которые распечатывают данные в разных точках программы (для этого полезно использовать Dumper), или с помощью интерактивного отладчика для перехода через программу. Интерактивные отладчики предпочтительнее, потому что они дают вам больше контроля и, как правило, быстрее (если вы не распечатывали важную часть данных в коде эшафота, вам нужно перезапустить программу, а отладчик, не нужно перезапускать),

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

Поделиться
  • 0
    Благодарю. Но я все еще получаю ту же ошибку.
  • 0
    @neversaint: опубликуйте обновленный код
1

Я попробовал Outis предложение, и он работает по желанию Невершина:)

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

perl euler.pl

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

Поделиться

Ещё вопросы

Сообщество Overcoder
Наверх
Меню