CVS difference for ai05s/ai05-0212-1.txt

Differences between 1.7 and version 1.8
Log of other versions for file ai05s/ai05-0212-1.txt

--- ai05s/ai05-0212-1.txt	2011/03/10 03:26:30	1.7
+++ ai05s/ai05-0212-1.txt	2011/03/17 02:58:31	1.8
@@ -371,127 +371,117 @@
 A.18.33 Example of container use
 
 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.Hashed_Sets; 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_Sets is new Vectors (Node, Boolean);
-   --  A set of nodes is a boolean vector.
-
-   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);
-
-   package Distances is new Vectors (Node, Distance);
-   --  The algorithm keeps a map from node to the shortest distance found so
-   --  far to that node.
-
-   function Shortest_Path
-     (G : Graphs.Vector; Source : Node; Target : Node) return Paths.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_Sets, Node_Maps, Paths, Distances, Graphs;
-
-      Reached  : Node_Sets.Vector;
-      --  The set of nodes whose shortest distance to the source is known.
-
-      Reached_From : Node_Maps.Vector;
-      So_Far   : Distances.Vector;
-      The_Path : Paths.List := Paths.Empty_List;
-      Nearest  : Node;
-      Nearest_Distance : Distance;
-      Next     : Node;
-   begin
-      Reserve_Capacity (So_Far, Length (G));
-      Reserve_Capacity (Reached, Length (G));
-
-      --  Initially all nodes are unreachable. The set of nodes is given by
-      --  the domain of the graph G.
-
-      for N in G.Iterate loop
-        So_Far (N) :=  Distance'Last;
-        Reached (N) := False;
-      end loop;
-
-      Reached (Source) := True;
-
-      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.
-
-         for N in G.Iterate loop
-            if not Reached (N)
-              and then So_Far (N) < Nearest_Distance then
-                 Next := N;
-                 Nearest_Distance := So_Far (N);
-            end if;
-         end loop;
-
-         Reached (Next) := True;
-
-         --  Update minimum distance to other nodes, by iterating over the
-         --  adjacency list of the newly reached node.
-
-         for E of G (Next) loop
-            if not Reached (E.To) then
-               Nearest_Distance :=
-                 Distance'Min (So_Far (E.To) + So_Far (Nearest), 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;
+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.ELement (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. Element (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;
+
+
 Note that the effect of the Variable_Indexing aspect (on type Vector) and the
 Implicit_Dereference aspect (on type Reference_Type) is that
 
-   So_Far (N) := Distance'Last;
+   G (Next)
 
 is a convenient short hand for
 
-   So_Far.Reference (N).Element.all := Distance'Last;
+   G.Reference (Next).Element.all
 
 Similarly, the effect of the loop:
 
@@ -1496,3 +1486,18 @@
 
 ****************************************************************
 
+From: Ed Schonberg
+Sent: Tuesday, March 15, 2011  2:00 PM
+
+Here is a revised version of Dijkstra's shortest path algorithm.  It is simpler
+than the previous version, (it even uses anonymous array types where
+appropriate) and only makes use once of the new iterator form. It compiles
+properly with the partial implementation of iterators in GNAT, and the code
+incorporates the suggestions made at last meeting, including the precondition
+that the source node is connected to the given graph.  a proper postcondition
+seems out of reach: describing the set of possible paths would be longer than
+the algorithm itself!
+
+[Editor's note: This is version /07 of the AI.]
+
+****************************************************************

Questions? Ask the ACAA Technical Agent