Example of Container Use

{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;

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.

      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
      Reached(Source) := True;
      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;

if Next = Source 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.

         for E of G (Next) loop
            if not Reached(E.To) then
               Nearest_Distance :=
                 Distance'Min (So_Far(E.To) + So_Far(Next),
                               So_Far(E.To));

               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.

      declare
         N : Node := Target;
      begin
         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.Constant_Reference (Next).Element.all

for E of G (Next) loop
   if not Reached(E.To) then
      ...
   end if;
end loop;

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;

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;

A.18.32 Example of Container Use

Examples

Wording Changes from Ada 2005