A.18.33 Example of Container Use
Examples
{
AI05-0212-1}
The following example is an implementation of Dijkstra's shortest path
algorithm in a directed graph with positive distances. The graph is represented
by a map from nodes to sets of edges.
with Ada.Containers.Vectors;
with Ada.Containers.Doubly_Linked_Lists;
use Ada.Containers;
generic
type Node is range <>;
package Shortest_Paths is
type Distance is new Float range 0.0 .. Float'Last;
type Edge is record
To, From : Node;
Length : Distance;
end record;
package Node_Maps is new Vectors (Node, Node);
-- The algorithm builds a map to indicate the node used to reach a given
-- node in the shortest distance.
package Adjacency_Lists is new Doubly_Linked_Lists (Edge);
use Adjacency_Lists;
package Graphs is new Vectors (Node, Adjacency_Lists.List);
package Paths is new Doubly_Linked_Lists (Node);
function Shortest_Path
(G : Graphs.Vector; Source : Node; Target : Node) return Paths.List
with Pre => G (Source) /= Adjacency_Lists.Empty_List;
end Shortest_Paths;
{
AI12-0178-1}
package body Shortest_Paths
is
function Shortest_Path
(G : Graphs.Vector; Source : Node; Target : Node)
return Paths.List
is
use Adjacency_Lists, Node_Maps, Paths, Graphs;
Reached :
array (Node)
of Boolean := (
others => False);
--
The set of nodes whose shortest distance to the source is known.
{
AI05-0299-1}
Reached_From :
array (Node)
of Node;
So_Far :
array (Node)
of Distance := (
others => Distance'Last);
The_Path : Paths.List := Paths.Empty_List;
Nearest_Distance : Distance;
Next : Node;
begin
So_Far(Source) := 0.0;
while not Reached(Target) loop
Nearest_Distance := Distance'Last;
-- Find closest node not reached yet, by iterating over all nodes.
-- A more efficient algorithm uses a priority queue for this step.
Next := Source;
for N in Node'First .. Node'Last loop
if not Reached(N)
and then So_Far(N) < Nearest_Distance then
Next := N;
Nearest_Distance := So_Far(N);
end if;
end loop;
{
AI05-0299-1}
if Nearest_Distance = Distance'Last
then
--
No next node found, graph is not connected
return Paths.Empty_List;
else
Reached(Next) := True;
end if;
-- Update minimum distance to newly reachable nodes.
{
AI05-0299-1}
for E
of G (Next)
loop
if not Reached(E.To)
then
Nearest_Distance := E.Length + So_Far(Next);
if Nearest_Distance < So_Far(E.To) then
Reached_From(E.To) := Next;
So_Far(E.To) := Nearest_Distance;
end if;
end if;
end loop;
end loop;
-- Rebuild path from target to source.
{
AI12-0386-1}
declare
N : Node := Target;
begin
Prepend (The_Path, N);
while N /= Source
loop
N := Reached_From(N);
Prepend (The_Path, N);
end loop;
end;
return The_Path;
end;
end Shortest_Paths;
{
AI05-0212-1}
Note that the effect of the Constant_Indexing aspect (on type Vector)
and the Implicit_Dereference aspect (on type Reference_Type) is that
G (Next)
G.Constant_Reference (Next).Element.all
for E of G (Next) loop
if not Reached(E.To) then
...
end if;
end loop;
{
AI12-0080-1}
for C
in G (Next).Iterate
loop
declare
E : Edge
renames G (Next)(C)
.all;
begin
if not Reached(E.To)
then
...
end if;
end;
end loop;
{
AI12-0080-1}
declare
L : Adjacency_Lists.List
renames G (Next);
C : Adjacency_Lists.Cursor := L.First;
begin
while Has_Element (C)
loop
declare
E : Edge
renames L(C)
.all;
begin
if not Reached(E.To)
then
...
end if;
end;
C := L.Next (C);
end loop;
end;
Wording Changes from Ada 2005
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe