Ada Conformity Assessment Authority      Home Conformity Assessment   Test Suite ARGAda Standard
 
Annotated Ada Reference Manual (Ada 202x Draft 25)Legal Information
Contents   Index   References   Search   Previous   Next 

A.18.33 Example of Container Use

Examples

1/3
{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.
2/3
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;
3/3
   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.
4/3
   package Adjacency_Lists is new Doubly_Linked_Lists (Edge);
   use Adjacency_Lists;
5/3
   package Graphs is new Vectors (Node, Adjacency_Lists.List);
6/3
   package Paths is new Doubly_Linked_Lists (Node);
7/3
   function Shortest_Path
     (G : Graphs.Vector; Source : Node; Target : Node) return Paths.List
      with Pre => G (Source) /= Adjacency_Lists.Empty_List;
8/3
end Shortest_Paths;
9/5
{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.
10/3
{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;
11/3
      while not Reached(Target) loop
         Nearest_Distance := Distance'Last;
12/3
         -- Find closest node not reached yet, by iterating over all nodes.
         -- A more efficient algorithm uses a priority queue for this step.
13/3
         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;
14/3
{AI05-0299-1}          if Nearest_Distance = Distance'Last then
            -- No next node found, graph is not connected
            return Paths.Empty_List;
15/3
         else
            Reached(Next) := True;
         end if;
16/3
         -- Update minimum distance to newly reachable nodes.
17/3
{AI05-0299-1}          for E of G (Next) loop
            if not Reached(E.To) then
               Nearest_Distance := E.Length + So_Far(Next);
18/3
               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;
19/3
      -- Rebuild path from target to source.
20/3
      declare
         N : Node := Target;
      begin
         while N /= Source loop
            N := Reached_From(N);
            Prepend (The_Path, N);
         end loop;
      end;
21/3
      return The_Path;
   end;
end Shortest_Paths;
22/3
{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
23/3
G (Next)
24/3
{AI05-0212-1} is a convenient short hand for
25/3
G.Constant_Reference (Next).Element.all
26/3
{AI05-0212-1} Similarly, the effect of the loop:
27/3
for E of G (Next) loop
   if not Reached(E.To) then
      ...
   end if;
end loop;
28/3
{AI05-0212-1} is the same as:
29/4
{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;
30/3
{AI05-0212-1} which is the same as:
31/4
{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

31.a/3
{AI05-0212-1} This example of container use is new. 

Contents   Index   References   Search   Previous   Next 
Ada-Europe Ada 2005 and 2012 Editions sponsored in part by Ada-Europe