python - 在 Perl 中寻找欧拉路径

Question

我有一个代码试图找到 Eulerian path像这样。但不知何故它不起作用。 代码有什么问题？

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_

Answer 1

在 Perl 中，delete 不会重新索引。来自 Perl documentation :

delete() may also be used on arrays and array slices, but its behavior is less straightforward. Although exists() will return false for deleted entries, deleting array elements never changes indices of existing values; use shift() or splice() for that.

如文档中所述，您可以使用 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 调试的基础知识(因为 someone already did 作为 Perl 文档的一部分，而 laziness 可能是一件好事)，但一个简短的概述似乎是必要的。调试的本质是在程序运行时检查程序中的数据(也称为“程序状态”)。您可以使用脚手架在程序的各个点打印出数据(Dumper 对此很有用)，或者使用交互式调试器逐步执行程序。交互式调试器是首选，因为它们为您提供更多控制并且通常更快(如果您没有在脚手架代码中打印出关键数据，则需要重新启动程序；使用调试器，则无需重新启动) .

使用任一技术，检查 eulerPath 子例程中的变量:@graph、@stack、$v，$u。对您的原始程序、将 delete 替换为 splice 的中间程序以及进行我建议的所有更改的程序都执行此操作。看看您是否可以从数据中找出问题所在和产生错误的原因，以及导致我建议的更改的原因。