5
\$\begingroup\$

I have this Perl module project.

My implementation of the Dijkstra's algorithm follows:

package BidirectionalDijkstra::AlgorithmSelector;

use BidirectionalDijkstra::SourceVertexSelector;
use BidirectionalDijkstra::TargetVertexSelector;
use BidirectionalDijkstra::Graph;

sub new {
    my $class = shift;
    my $data = shift;
    bless($data, $class);
    return $data;
}

sub tracebackPathUnidirectional {
    my $parent_map = shift;
    my $target_vertex = shift;
    my $path = [];
    my $current_vertex = $target_vertex;
    
    while (defined($current_vertex)) {
        push(@{$path}, $current_vertex);
        $current_vertex = $parent_map->{$current_vertex};
    }

    return [ reverse @{$path} ];
}

sub slow {
    my $data = shift;
    my $graph = $data->{graph};
    my $source = $data->{source_vertex_id};
    my $target = $data->{target_vertex_id};
    my $search_frontier = BidirectionalDijkstra::DaryHeap->new(4);
    my $settled_vertices = {};
    my $distance_map = {};
    my $parent_map = {};

    $search_frontier->add($source, 0.0);
    $distance_map->{$source} = 0.0;
    $parent_map->{$source} = undef;

    while ($search_frontier->size() > 0) {
        my $current_vertex = $search_frontier->extractMinimum();

        if ($current_vertex eq $target) {
            return tracebackPathUnidirectional($parent_map, $current_vertex);
        }

        if (exists $settled_vertices->{$current_vertex}) {
            next;
        }

        $settled_vertices->{$current_vertex} = undef;
    
        foreach my $child_vertex_id (keys %{$graph->getChildren($current_vertex)}) {
            if (exists $settled_vertices->{$child_vertex_id}) {
                next;
            }

            my $tentative_distance = $distance_map->{$current_vertex} + 
                         $graph->getEdgeWeight($current_vertex, 
                                       $child_vertex_id);

            my $do_update = 0;

            if (not exists $distance_map->{$child_vertex_id}) {
                $search_frontier->add($child_vertex_id, $tentative_distance);
                $do_update = 1;
            } elsif ($distance_map->{$child_vertex_id} > $tentative_distance) {
                $search_frontier->decreasePriority($child_vertex_id, 
                                   $tentative_distance);
                $do_update = 1;
            }

            if ($do_update) {
                $distance_map->{$child_vertex_id} = $tentative_distance;
                $parent_map->{$child_vertex_id} = $current_vertex;
            }
        }
    }

    return undef;
}

1;

Critique request

Please, tell me anything that comes to mind, thanks!

Running instruction

Clone the repository linked at the top of the post to, say, directory BDG. From BDG, cd to BidirectionalDijkstra-Graph, and there, run the following commands:

perl Makefile.PL
make
make test

You should see the line at the bottom of output Result: PASS

Then, from BDG, simply run ./benchmark.pl to see the Dijkstra's algorithm in action. You may see something like this:

Graph built in 3246 seconds.
Source vertex: 27843
Target vertex: 18511
Slow: 100000, 27843 -> 18511
Dijkstra's algorithm in 9354 milliseconds.
Shortest path:
1: 27843
2: 64486
3: 10789
4: 17371
5: 74480
6: 29409
7: 2443
8: 97395
9: 47888
10: 14520
11: 67169
12: 18511
\$\endgroup\$
2
  • \$\begingroup\$ (@200_success: What has induced removing tag dijkstra?) \$\endgroup\$
    – greybeard
    Commented Apr 15, 2022 at 15:07
  • \$\begingroup\$ @greybeard Deprecated tag; see the edit log. \$\endgroup\$ Commented Apr 15, 2022 at 15:13

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.