use v6;
=begin comment
Implementation of the Dijkstra's algorithm. Based on the Go's implementation
by Jonatas B (https://deployeveryday.com/2019/10/16/dijkstra-algorithm-golang.html).
The Graph class makes the following methods available:
* add-edge
* add-node
* get-node-edges
* Dijkstra
Their documentation can be pulled by using `p6doc graph.p6` where graph.p6
is this file.
To instatiate either an edge or a node, use Graph::Edge or Graph::Node
respectively.
=end comment
class Graph {
class Node {
has Str $.name;
}
class Edge {
has Node $.parent;
has Node $.child;
has Int $.cost;
}
has Bool %!edges{Edge};
has Node @!nodes;
#| Add an edge to the graph.
method add-edge(Node:D $parent, Node:D $child, Int:D $cost --> Nil) {
my Edge $edge .= new: :$parent, :$child, :$cost;
%!edges{$edge} = True;
self.add-node: $parent;
self.add-node: $child;
}
#| Add a node to the graph list of nodes, if the the node wasn't already
#| added. Return True if added. Otherwise, False.
method add-node(Node:D $node --> Bool) {
my Bool $is-present = False;
for @!nodes -> $n {
$is-present = True if $n eqv $node;
}
unless $is-present {
@!nodes.append: $node;
return True;
}
return False;
}
#| Return all the edges that start with the specified node. In other terms,
#| all the edges connecting to the node's neighbors.
method get-node-edges(Node:D $node --> Array) {
my Edge @edges = %!edges
.grep({ $^edge.key.parent eqv $node}) # get pairs of Edge => Bool
.map( { $^edge.key }); # get pair's key (i.e., Edge)
return @edges
}
#| Implement Dijkstra algorithm. Return the shortest path from start node to
#| all the other nodes.
method Dijkstra(Node:D $start-node --> Hash) {
=begin comment
First, we instantiate a "cost table", which will hold the following
information: "From start node, what's is the cost to all the other nodes?".
When initialized, it looks like this:
NODE COST
A 0 # The start node has always the lowest cost to itself, in this case, 0
B Inf # the distance to all the other Nodes are unknown, so we mark as Infinity
C Inf
...
=end comment
my Hash $cost-table = self!new-cost-table($start-node);
# An empty list of "visited" nodes. Everytime the algorithm runs on a
# node, we add it here.
my Node @visited;
# A loop to visit all nodes.
while @visited.elems != @!nodes.elems {
# Get closest non visited node (lower cost) from the cost table.
my Node $node = self!get-closest-nonvisited-node($cost-table, @visited);
# Mark node as visited.
@visited.append($node);
# Get node's edges (i.e., its neighbors).
my Edge @node-edges = self.get-node-edges($node);
for @node-edges -> $edge {
my Int $distance-to-neighbor = $cost-table{$node} + $edge.cost;
# If the distance above is lesser than the distance currently
# in the cost table for that neighbor...
if $distance-to-neighbor < $cost-table{$edge.child} {
# ... Update the cost table for that neighbor.
$cost-table{ $edge.child } = $distance-to-neighbor;
}
}
}
return $cost-table;
}
# Return a string representation of the graph. It kicks in by invoking
# .Str on the graph or when outputing with the `say` routine.
method gist {
my Str $s;
$s ~= "Edges:\n";
for %!edges.keys -> $edge {
$s ~= "{$edge.parent.name} -> {$edge.child.name} = {$edge.cost}\n";
}
$s ~= "\n";
$s ~= "Nodes: ";
for @!nodes.kv -> $i, $node {
if $i == @!nodes.elems - 1 {
$s ~= $node.name
} else {
$s ~= $node.name ~ ", "
}
}
$s ~= "\n";
return $s
}
# Return an initialized cost table for the Dijkstra algorithm.
# By default, the lowest cost is assigned to the start node. Thus, the
# algorithm starts from the and the other nodes in the graph receives the
# Inf value.
method !new-cost-table(Node:D $start-node --> Hash) {
my %cost-table{Node};
%cost-table{ $start-node } = 0;
for @!nodes -> $node {
%cost-table{$node} = Inf if !($node eqv $start-node);
}
return %cost-table;
}
# Return the closest node (with the lower cost) from the cost table.
# That is if the node hasn't been visited yet.
method !get-closest-nonvisited-node(%cost-table, Node @visited --> Node) {
class CostTableToSort {
has Node $.node;
has $.cost;
}
my CostTableToSort @sorted;
# Check if the node has been visited already.
for %cost-table.kv -> $node, $cost {
my Bool $is-visited = False;
$is-visited = True if $node ∈ @visited;
# If not, add them to the sorted slice
unless $is-visited {
@sorted.append(CostTableToSort.new(:$node, :$cost));
}
}
# We need the node with the lower cost from the cost table. So,
# sort cost table by cost and retrieve it.
return @sorted.sort({ $^a.cost <=> $^b.cost }).first.node;
}
}
my Graph::Node $a .= new(name => "a");
my Graph::Node $b .= new(name => "b");
my Graph::Node $c .= new(name => "c");
my Graph::Node $d .= new(name => "d");
my Graph::Node $e .= new(name => "e");
my Graph::Node $f .= new(name => "f");
my Graph::Node $g .= new(name => "g");
my Graph $graph .= new;
$graph.add-edge($a, $c, 2);
$graph.add-edge($a, $b, 5);
$graph.add-edge($c, $b, 1);
$graph.add-edge($c, $d, 9);
$graph.add-edge($b, $d, 4);
$graph.add-edge($d, $e, 2);
$graph.add-edge($d, $g, 30);
$graph.add-edge($d, $f, 10);
$graph.add-edge($f, $g, 1);
say $graph;
my $cost-table = $graph.Dijkstra($a);
for $cost-table.kv -> $node, $cost {
"Distance from %s to %s = %d\n".printf($a.name, $node.name, $cost);
}
