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