[Ada] Clean up of GNAT.Graphs

------------
-- Source --
------------

--  operations.adb

with Ada.Text_IO; use Ada.Text_IO;
with GNAT;        use GNAT;
with GNAT.Graphs; use GNAT.Graphs;
with GNAT.Sets;   use GNAT.Sets;

procedure Operations is
   type Vertex_Id is
     (No_V, VA, VB, VC, VD, VE, VF, VG, VH, VX, VY, VZ);
   No_Vertex_Id : constant Vertex_Id := No_V;

   function Hash_Vertex (V : Vertex_Id) return Bucket_Range_Type;

   type Edge_Id is
    (No_E, E1, E2, E3, E4, E5, E6, E7, E8, E9, E10, E97, E98, E99);
   No_Edge_Id : constant Edge_Id := No_E;

   function Hash_Edge (E : Edge_Id) return Bucket_Range_Type;

   package ES is new Membership_Sets
     (Element_Type => Edge_Id,
      "="          => "=",
      Hash         => Hash_Edge);

   package DG is new Directed_Graphs
     (Vertex_Id   => Vertex_Id,
      No_Vertex   => No_Vertex_Id,
      Hash_Vertex => Hash_Vertex,
      Same_Vertex => "=",
      Edge_Id     => Edge_Id,
      No_Edge     => No_Edge_Id,
      Hash_Edge   => Hash_Edge,
      Same_Edge   => "=");
   use DG;

   package VS is new Membership_Sets
     (Element_Type => Vertex_Id,
      "="          => "=",
      Hash         => Hash_Vertex);

   -----------------------
   -- Local subprograms --
   -----------------------

   procedure Check_Belongs_To_Component
     (R        : String;
      G        : Directed_Graph;
      V        : Vertex_Id;
      Exp_Comp : Component_Id);
   --  Verify that vertex V of graph G belongs to component Exp_Comp. R is the
   --  calling routine.

   procedure Check_Belongs_To_Some_Component
     (R : String;
      G : Directed_Graph;
      V : Vertex_Id);
   --  Verify that vertex V of graph G belongs to some component. R is the
   --  calling routine.

   procedure Check_Destination_Vertex
     (R     : String;
      G     : Directed_Graph;
      E     : Edge_Id;
      Exp_V : Vertex_Id);
   --  Vertify that the destination vertex of edge E of grah G is Exp_V. R is
   --  the calling routine.

   procedure Check_Distinct_Components
     (R      : String;
      Comp_1 : Component_Id;
      Comp_2 : Component_Id);
   --  Verify that components Comp_1 and Comp_2 are distinct (not the same)

   procedure Check_Has_Component
     (R      : String;
      G      : Directed_Graph;
      G_Name : String;
      Comp   : Component_Id);
   --  Verify that graph G with name G_Name contains component Comp. R is the
   --  calling routine.

   procedure Check_Has_Edge
     (R : String;
      G : Directed_Graph;
      E : Edge_Id);
   --  Verify that graph G contains edge E. R is the calling routine.

   procedure Check_Has_Vertex
     (R : String;
      G : Directed_Graph;
      V : Vertex_Id);
   --  Verify that graph G contains vertex V. R is the calling routine.

   procedure Check_No_Component
     (R : String;
      G : Directed_Graph;
      V : Vertex_Id);
   --  Verify that vertex V does not belong to some component. R is the calling
   --  routine.

   procedure Check_No_Component
     (R      : String;
      G      : Directed_Graph;
      G_Name : String;
      Comp   : Component_Id);
   --  Verify that graph G with name G_Name does not contain component Comp. R
   --  is the calling routine.

   procedure Check_No_Edge
     (R : String;
      G : Directed_Graph;
      E : Edge_Id);
   --  Verify that graph G does not contain edge E. R is the calling routine.

   procedure Check_No_Vertex
     (R : String;
      G : Directed_Graph;
      V : Vertex_Id);
   --  Verify that graph G does not contain vertex V. R is the calling routine.

   procedure Check_Number_Of_Components
     (R       : String;
      G       : Directed_Graph;
      Exp_Num : Natural);
   --  Verify that graph G has exactly Exp_Num components. R is the calling
   --  routine.

   procedure Check_Number_Of_Edges
     (R       : String;
      G       : Directed_Graph;
      Exp_Num : Natural);
   --  Verify that graph G has exactly Exp_Num edges. R is the calling routine.

   procedure Check_Number_Of_Vertices
     (R       : String;
      G       : Directed_Graph;
      Exp_Num : Natural);
   --  Verify that graph G has exactly Exp_Num vertices. R is the calling
   --  routine.

   procedure Check_Outgoing_Edge_Iterator
     (R   : String;
      G   : Directed_Graph;
      V   : Vertex_Id;
      Set : ES.Membership_Set);
   --  Verify that all outgoing edges of vertex V of graph G can be iterated
   --  and appear in set Set. R is the calling routine.

   procedure Check_Source_Vertex
     (R     : String;
      G     : Directed_Graph;
      E     : Edge_Id;
      Exp_V : Vertex_Id);
   --  Vertify that the source vertex of edge E of grah G is Exp_V. R is the
   --  calling routine.

   procedure Check_Vertex_Iterator
     (R    : String;
      G    : Directed_Graph;
      Comp : Component_Id;
      Set  : VS.Membership_Set);
   --  Verify that all vertices of component Comp of graph G can be iterated
   --  and appear in set Set. R is the calling routine.

   function Create_And_Populate return Directed_Graph;
   --  Create a brand new graph (see body for the shape of the graph)

   procedure Error (R : String; Msg : String);
   --  Output an error message with text Msg within the context of routine R

   procedure Test_Add_Edge;
   --  Verify the semantics of routine Add_Edge

   procedure Test_Add_Vertex;
   --  Verify the semantics of routine Add_Vertex

   procedure Test_All_Edge_Iterator;
   --  Verify the semantics of All_Edge_Iterator

   procedure Test_All_Vertex_Iterator;
   --  Verify the semantics of All_Vertex_Iterator

   procedure Test_Component;
   --  Verify the semantics of routine Component

   procedure Test_Component_Iterator;
   --  Verify the semantics of Component_Iterator

   procedure Test_Contains_Component;
   --  Verify the semantics of routine Contains_Component

   procedure Test_Contains_Edge;
   --  Verify the semantics of routine Contains_Edge

   procedure Test_Contains_Vertex;
   --  Verify the semantics of routine Contains_Vertex

   procedure Test_Delete_Edge;
   --  Verify the semantics of routine Delete_Edge

   procedure Test_Destination_Vertex;
   --  Verify the semantics of routine Destination_Vertex

   procedure Test_Find_Components;
   --  Verify the semantics of routine Find_Components

   procedure Test_Is_Empty;
   --  Verify the semantics of routine Is_Empty

   procedure Test_Number_Of_Components;
   --  Verify the semantics of routine Number_Of_Components

   procedure Test_Number_Of_Edges;
   --  Verify the semantics of routine Number_Of_Edges

   procedure Test_Number_Of_Vertices;
   --  Verify the semantics of routine Number_Of_Vertices

   procedure Test_Outgoing_Edge_Iterator;
   --  Verify the semantics of Outgoing_Edge_Iterator

   procedure Test_Present;
   --  Verify the semantics of routine Present

   procedure Test_Source_Vertex;
   --  Verify the semantics of routine Source_Vertex

   procedure Test_Vertex_Iterator;
   --  Verify the semantics of Vertex_Iterator;

   procedure Unexpected_Exception (R : String);
   --  Output an error message concerning an unexpected exception within
   --  routine R.

   --------------------------------
   -- Check_Belongs_To_Component --
   --------------------------------

   procedure Check_Belongs_To_Component
     (R        : String;
      G        : Directed_Graph;
      V        : Vertex_Id;
      Exp_Comp : Component_Id)
   is
      Act_Comp : constant Component_Id := Component (G, V);

   begin
      if Act_Comp /= Exp_Comp then
         Error (R, "inconsistent component for vertex " & V'Img);
         Error (R, "  expected: " & Exp_Comp'Img);
         Error (R, "  got     : " & Act_Comp'Img);
      end if;
   end Check_Belongs_To_Component;

   -------------------------------------
   -- Check_Belongs_To_Some_Component --
   -------------------------------------

   procedure Check_Belongs_To_Some_Component
     (R : String;
      G : Directed_Graph;
      V : Vertex_Id)
   is
   begin
      if not Present (Component (G, V)) then
         Error (R, "vertex " & V'Img & " does not belong to a component");
      end if;
   end Check_Belongs_To_Some_Component;

   ------------------------------
   -- Check_Destination_Vertex --
   ------------------------------

   procedure Check_Destination_Vertex
     (R     : String;
      G     : Directed_Graph;
      E     : Edge_Id;
      Exp_V : Vertex_Id)
   is
      Act_V : constant Vertex_Id := Destination_Vertex (G, E);

   begin
      if Act_V /= Exp_V then
         Error (R, "inconsistent destination vertex for edge " & E'Img);
         Error (R, "  expected: " & Exp_V'Img);
         Error (R, "  got     : " & Act_V'Img);
      end if;
   end Check_Destination_Vertex;

   -------------------------------
   -- Check_Distinct_Components --
   -------------------------------

   procedure Check_Distinct_Components
     (R      : String;
      Comp_1 : Component_Id;
      Comp_2 : Component_Id)
   is
   begin
      if Comp_1 = Comp_2 then
         Error (R, "components are not distinct");
      end if;
   end Check_Distinct_Components;

   -------------------------
   -- Check_Has_Component --
   -------------------------

   procedure Check_Has_Component
     (R      : String;
      G      : Directed_Graph;
      G_Name : String;
      Comp   : Component_Id)
   is
   begin
      if not Contains_Component (G, Comp) then
         Error (R, "graph " & G_Name & " lacks component");
      end if;
   end Check_Has_Component;

   --------------------
   -- Check_Has_Edge --
   --------------------

   procedure Check_Has_Edge
     (R : String;
      G : Directed_Graph;
      E : Edge_Id)
   is
   begin
      if not Contains_Edge (G, E) then
         Error (R, "graph lacks edge " & E'Img);
      end if;
   end Check_Has_Edge;

   ----------------------
   -- Check_Has_Vertex --
   ----------------------

   procedure Check_Has_Vertex
     (R : String;
      G : Directed_Graph;
      V : Vertex_Id)
   is
   begin
      if not Contains_Vertex (G, V) then
         Error (R, "graph lacks vertex " & V'Img);
      end if;
   end Check_Has_Vertex;

   ------------------------
   -- Check_No_Component --
   ------------------------

   procedure Check_No_Component
     (R : String;
      G : Directed_Graph;
      V : Vertex_Id)
   is
   begin
      if Present (Component (G, V)) then
         Error (R, "vertex " & V'Img & " belongs to a component");
      end if;
   end Check_No_Component;

   procedure Check_No_Component
     (R      : String;
      G      : Directed_Graph;
      G_Name : String;
      Comp   : Component_Id)
   is
   begin
      if Contains_Component (G, Comp) then
         Error (R, "graph " & G_Name & " contains component");
      end if;
   end Check_No_Component;

   -------------------
   -- Check_No_Edge --
   -------------------

   procedure Check_No_Edge
     (R : String;
      G : Directed_Graph;
      E : Edge_Id)
   is
   begin
      if Contains_Edge (G, E) then
         Error (R, "graph contains edge " & E'Img);
      end if;
   end Check_No_Edge;

   ---------------------
   -- Check_No_Vertex --
   ---------------------

   procedure Check_No_Vertex
     (R : String;
      G : Directed_Graph;
      V : Vertex_Id)
   is
   begin
      if Contains_Vertex (G, V) then
         Error (R, "graph contains vertex " & V'Img);
      end if;
   end Check_No_Vertex;

   --------------------------------
   -- Check_Number_Of_Components --
   --------------------------------

   procedure Check_Number_Of_Components
     (R       : String;
      G       : Directed_Graph;
      Exp_Num : Natural)
   is
      Act_Num : constant Natural := Number_Of_Components (G);

   begin
      if Act_Num /= Exp_Num then
         Error (R, "inconsistent number of components");
         Error (R, "  expected: " & Exp_Num'Img);
         Error (R, "  got     : " & Act_Num'Img);
      end if;
   end Check_Number_Of_Components;

   ---------------------------
   -- Check_Number_Of_Edges --
   ---------------------------

   procedure Check_Number_Of_Edges
     (R       : String;
      G       : Directed_Graph;
      Exp_Num : Natural)
   is
      Act_Num : constant Natural := Number_Of_Edges (G);

   begin
      if Act_Num /= Exp_Num then
         Error (R, "inconsistent number of edges");
         Error (R, "  expected: " & Exp_Num'Img);
         Error (R, "  got     : " & Act_Num'Img);
      end if;
   end Check_Number_Of_Edges;

   ------------------------------
   -- Check_Number_Of_Vertices --
   ------------------------------

   procedure Check_Number_Of_Vertices
     (R       : String;
      G       : Directed_Graph;
      Exp_Num : Natural)
   is
      Act_Num : constant Natural := Number_Of_Vertices (G);

   begin
      if Act_Num /= Exp_Num then
         Error (R, "inconsistent number of vertices");
         Error (R, "  expected: " & Exp_Num'Img);
         Error (R, "  got     : " & Act_Num'Img);
      end if;
   end Check_Number_Of_Vertices;

   ----------------------------------
   -- Check_Outgoing_Edge_Iterator --
   ----------------------------------

   procedure Check_Outgoing_Edge_Iterator
     (R   : String;
      G   : Directed_Graph;
      V   : Vertex_Id;
      Set : ES.Membership_Set)
   is
      E : Edge_Id;

      Out_E_Iter : Outgoing_Edge_Iterator;

   begin
      --  Iterate over all outgoing edges of vertex V while removing edges seen
      --  from the set.

      Out_E_Iter := Iterate_Outgoing_Edges (G, V);
      while Has_Next (Out_E_Iter) loop
         Next (Out_E_Iter, E);

         if ES.Contains (Set, E) then
            ES.Delete (Set, E);
         else
            Error (R, "outgoing edge " & E'Img & " is not iterated");
         end if;
      end loop;

      --  At this point the set of edges should be empty

      if not ES.Is_Empty (Set) then
         Error (R, "not all outgoing edges were iterated");
      end if;
   end Check_Outgoing_Edge_Iterator;

   -------------------------
   -- Check_Source_Vertex --
   -------------------------

   procedure Check_Source_Vertex
     (R     : String;
      G     : Directed_Graph;
      E     : Edge_Id;
      Exp_V : Vertex_Id)
   is
      Act_V : constant Vertex_Id := Source_Vertex (G, E);

   begin
      if Act_V /= Exp_V then
         Error (R, "inconsistent source vertex");
         Error (R, "  expected: " & Exp_V'Img);
         Error (R, "  got     : " & Act_V'Img);
      end if;
   end Check_Source_Vertex;

   ---------------------------
   -- Check_Vertex_Iterator --
   ---------------------------

   procedure Check_Vertex_Iterator
     (R    : String;
      G    : Directed_Graph;
      Comp : Component_Id;
      Set  : VS.Membership_Set)
   is
      V : Vertex_Id;

      V_Iter : Vertex_Iterator;

   begin
      --  Iterate over all vertices of component Comp while removing vertices
      --  seen from the set.

      V_Iter := Iterate_Vertices (G, Comp);
      while Has_Next (V_Iter) loop
         Next (V_Iter, V);

         if VS.Contains (Set, V) then
            VS.Delete (Set, V);
         else
            Error (R, "vertex " & V'Img & " is not iterated");
         end if;
      end loop;

      --  At this point the set of vertices should be empty

      if not VS.Is_Empty (Set) then
         Error (R, "not all vertices were iterated");
      end if;
   end Check_Vertex_Iterator;

   -------------------------
   -- Create_And_Populate --
   -------------------------

   function Create_And_Populate return Directed_Graph is
      G : constant Directed_Graph :=
            Create (Initial_Vertices => Vertex_Id'Size,
                    Initial_Edges    => Edge_Id'Size);

   begin
      --       9         8           1        2
      --  G <------ F <------  A  ------> B -------> C
      --  |                  ^ | |        ^          ^
      --  +------------------+ | +-------------------+
      --       10              |          |   3
      --                    4  |        5 |
      --                       v          |
      --            H          D ---------+
      --                      | ^
      --                      | |
      --                    6 | | 7
      --                      | |
      --                      v |
      --                       E
      --
      --  Components:
      --
      --    [A, F, G]
      --    [B]
      --    [C]
      --    [D, E]
      --    [H]

      Add_Vertex (G, VA);
      Add_Vertex (G, VB);
      Add_Vertex (G, VC);
      Add_Vertex (G, VD);
      Add_Vertex (G, VE);
      Add_Vertex (G, VF);
      Add_Vertex (G, VG);
      Add_Vertex (G, VH);

      Add_Edge (G, E1,  Source => VA, Destination => VB);
      Add_Edge (G, E2,  Source => VB, Destination => VC);
      Add_Edge (G, E3,  Source => VA, Destination => VC);
      Add_Edge (G, E4,  Source => VA, Destination => VD);
      Add_Edge (G, E5,  Source => VD, Destination => VB);
      Add_Edge (G, E6,  Source => VD, Destination => VE);
      Add_Edge (G, E7,  Source => VE, Destination => VD);
      Add_Edge (G, E8,  Source => VA, Destination => VF);
      Add_Edge (G, E9,  Source => VF, Destination => VG);
      Add_Edge (G, E10, Source => VG, Destination => VA);

      return G;
   end Create_And_Populate;

   -----------
   -- Error --
   -----------

   procedure Error (R : String; Msg : String) is
   begin
      Put_Line ("ERROR: " & R & ": " & Msg);
   end Error;

   ---------------
   -- Hash_Edge --
   ---------------

   function Hash_Edge (E : Edge_Id) return Bucket_Range_Type is
   begin
      return Bucket_Range_Type (Edge_Id'Pos (E));
   end Hash_Edge;

   -----------------
   -- Hash_Vertex --
   -----------------

   function Hash_Vertex (V : Vertex_Id) return Bucket_Range_Type is
   begin
      return Bucket_Range_Type (Vertex_Id'Pos (V));
   end Hash_Vertex;

   -------------------
   -- Test_Add_Edge --
   -------------------

   procedure Test_Add_Edge is
      R : constant String := "Test_Add_Edge";

      E : Edge_Id;
      G : Directed_Graph := Create_And_Populate;

      All_E_Iter : All_Edge_Iterator;
      Out_E_Iter : Outgoing_Edge_Iterator;

   begin
      --  Try to add the same edge twice

      begin
         Add_Edge (G, E1, VB, VH);
         Error (R, "duplicate edge not detected");
      exception
         when Duplicate_Edge => null;
         when others         => Unexpected_Exception (R);
      end;

      --  Try to add an edge with a bogus source

      begin
         Add_Edge (G, E97, Source => VX, Destination => VC);
         Error (R, "missing vertex not detected");
      exception
         when Missing_Vertex => null;
         when others         => Unexpected_Exception (R);
      end;

      --  Try to add an edge with a bogus destination

      begin
         Add_Edge (G, E97, Source => VF, Destination => VY);
         Error (R, "missing vertex not detected");
      exception
         when Missing_Vertex => null;
         when others         => Unexpected_Exception (R);
      end;

      --  Delete edge E1 between vertices VA and VB

      begin
         Delete_Edge (G, E1);
      exception
         when others => Unexpected_Exception (R);
      end;

      --  Try to re-add edge E1

      begin
         Add_Edge (G, E1, Source => VA, Destination => VB);
      exception
         when others => Unexpected_Exception (R);
      end;

      --  Lock all edges in the graph

      All_E_Iter := Iterate_All_Edges (G);

      --  Try to add an edge given that all edges are locked

      begin
         Add_Edge (G, E97, Source => VG, Destination => VH);
         Error (R, "all edges not locked");
      exception
         when Iterated => null;
         when others   => Unexpected_Exception (R);
      end;

      --  Unlock all edges by iterating over them

      while Has_Next (All_E_Iter) loop Next (All_E_Iter, E); end loop;

      --  Lock all outgoing edges of vertex VD

      Out_E_Iter := Iterate_Outgoing_Edges (G, VD);

      --  Try to add an edge with source VD given that all edges of VD are
      --  locked.

      begin
         Add_Edge (G, E97, Source => VD, Destination => VG);
         Error (R, "outgoing edges of VD not locked");
      exception
         when Iterated => null;
         when others   => Unexpected_Exception (R);
      end;

      --  Unlock the edges of vertex VD by iterating over them

      while Has_Next (Out_E_Iter) loop Next (Out_E_Iter, E); end loop;

      Destroy (G);
   end Test_Add_Edge;

   ---------------------
   -- Test_Add_Vertex --
   ---------------------

   procedure Test_Add_Vertex is
      R : constant String := "Test_Add_Vertex";

      G : Directed_Graph := Create_And_Populate;
      V : Vertex_Id;

      All_V_Iter : All_Vertex_Iterator;

   begin
      --  Try to add the same vertex twice

      begin
         Add_Vertex (G, VD);
         Error (R, "duplicate vertex not detected");
      exception
         when Duplicate_Vertex => null;
         when others           => Unexpected_Exception (R);
      end;

      --  Lock all vertices in the graph

      All_V_Iter := Iterate_All_Vertices (G);

      --  Try to add a vertex given that all vertices are locked

      begin
         Add_Vertex (G, VZ);
         Error (R, "all vertices not locked");
      exception
         when Iterated => null;
         when others   => Unexpected_Exception (R);
      end;

      --  Unlock all vertices by iterating over them

      while Has_Next (All_V_Iter) loop Next (All_V_Iter, V); end loop;

      Destroy (G);
   end Test_Add_Vertex;

   ----------------------------
   -- Test_All_Edge_Iterator --
   ----------------------------

   procedure Test_All_Edge_Iterator is
      R : constant String := "Test_All_Edge_Iterator";

      E : Edge_Id;
      G : Directed_Graph := Create_And_Populate;

      All_E_Iter : All_Edge_Iterator;
      All_Edges  : ES.Membership_Set;

   begin
      --  Collect all expected edges in a set

      All_Edges := ES.Create (Number_Of_Edges (G));

      for Curr_E in E1 .. E10 loop
         ES.Insert (All_Edges, Curr_E);
      end loop;

      --  Iterate over all edges while removing encountered edges from the set

      All_E_Iter := Iterate_All_Edges (G);
      while Has_Next (All_E_Iter) loop
         Next (All_E_Iter, E);

         if ES.Contains (All_Edges, E) then
            ES.Delete (All_Edges, E);
         else
            Error (R, "edge " & E'Img & " is not iterated");
         end if;
      end loop;

      --  At this point the set of edges should be empty

      if not ES.Is_Empty (All_Edges) then
         Error (R, "not all edges were iterated");
      end if;

      ES.Destroy (All_Edges);
      Destroy (G);
   end Test_All_Edge_Iterator;

   ------------------------------
   -- Test_All_Vertex_Iterator --
   ------------------------------

   procedure Test_All_Vertex_Iterator is
      R : constant String := "Test_All_Vertex_Iterator";

      G : Directed_Graph := Create_And_Populate;
      V : Vertex_Id;

      All_V_Iter   : All_Vertex_Iterator;
      All_Vertices : VS.Membership_Set;

   begin
      --  Collect all expected vertices in a set

      All_Vertices := VS.Create (Number_Of_Vertices (G));

      for Curr_V in VA .. VH loop
         VS.Insert (All_Vertices, Curr_V);
      end loop;

      --  Iterate over all vertices while removing encountered vertices from
      --  the set.

      All_V_Iter := Iterate_All_Vertices (G);
      while Has_Next (All_V_Iter) loop
         Next (All_V_Iter, V);

         if VS.Contains (All_Vertices, V) then
            VS.Delete (All_Vertices, V);
         else
            Error (R, "vertex " & V'Img & " is not iterated");
         end if;
      end loop;

      --  At this point the set of vertices should be empty

      if not VS.Is_Empty (All_Vertices) then
         Error (R, "not all vertices were iterated");
      end if;

      VS.Destroy (All_Vertices);
      Destroy (G);
   end Test_All_Vertex_Iterator;

   --------------------
   -- Test_Component --
   --------------------

   procedure Test_Component is
      R : constant String := "Test_Component";

      G : Directed_Graph := Create (Initial_Vertices => 3, Initial_Edges => 2);

   begin
      --      E1
      --    ----->
      --  VA       VB     VC
      --    <-----
      --      E2
      --
      --  Components:
      --
      --    [VA, VB]
      --    [VC]

      Add_Vertex (G, VA);
      Add_Vertex (G, VB);
      Add_Vertex (G, VC);

      Add_Edge (G, E1, Source => VA, Destination => VB);
      Add_Edge (G, E2, Source => VB, Destination => VA);

      --  None of the vertices should belong to a component

      Check_No_Component (R, G, VA);
      Check_No_Component (R, G, VB);
      Check_No_Component (R, G, VC);

      --  Find the strongly connected components in the graph

      Find_Components (G);

      --  Vertices should belong to a component

      Check_Belongs_To_Some_Component (R, G, VA);
      Check_Belongs_To_Some_Component (R, G, VB);
      Check_Belongs_To_Some_Component (R, G, VC);

      Destroy (G);
   end Test_Component;

   -----------------------------
   -- Test_Component_Iterator --
   -----------------------------

   procedure Test_Component_Iterator is
      R : constant String := "Test_Component_Iterator";

      G : Directed_Graph := Create_And_Populate;

      Comp       : Component_Id;
      Comp_Count : Natural;
      Comp_Iter  : Component_Iterator;

   begin
      Find_Components (G);
      Check_Number_Of_Components (R, G, 5);

      Comp_Count := Number_Of_Components (G);

      --  Iterate over all components while decrementing their number

      Comp_Iter := Iterate_Components (G);
      while Has_Next (Comp_Iter) loop
         Next (Comp_Iter, Comp);

         Comp_Count := Comp_Count - 1;
      end loop;

      --  At this point all components should have been accounted for

      if Comp_Count /= 0 then
         Error (R, "not all components were iterated");
      end if;

      Destroy (G);
   end Test_Component_Iterator;

   -----------------------------
   -- Test_Contains_Component --
   -----------------------------

   procedure Test_Contains_Component is
      R : constant String := "Test_Contains_Component";

      G1 : Directed_Graph :=
             Create (Initial_Vertices => 2, Initial_Edges => 2);
      G2 : Directed_Graph :=
             Create (Initial_Vertices => 2, Initial_Edges => 2);

   begin
      --      E1
      --    ----->
      --  VA       VB
      --    <-----
      --      E2
      --
      --  Components:
      --
      --    [VA, VB]

      Add_Vertex (G1, VA);
      Add_Vertex (G1, VB);

      Add_Edge (G1, E1, Source => VA, Destination => VB);
      Add_Edge (G1, E2, Source => VB, Destination => VA);

      --      E97
      --    ----->
      --  VX       VY
      --    <-----
      --      E98
      --
      --  Components:
      --
      --    [VX, VY]

      Add_Vertex (G2, VX);
      Add_Vertex (G2, VY);

      Add_Edge (G2, E97, Source => VX, Destination => VY);
      Add_Edge (G2, E98, Source => VY, Destination => VX);

      --  Find the strongly connected components in both graphs

      Find_Components (G1);
      Find_Components (G2);

      --  Vertices should belong to a component

      Check_Belongs_To_Some_Component (R, G1, VA);
      Check_Belongs_To_Some_Component (R, G1, VB);
      Check_Belongs_To_Some_Component (R, G2, VX);
      Check_Belongs_To_Some_Component (R, G2, VY);

      --  Verify that each graph contains the correct component

      Check_Has_Component (R, G1, "G1", Component (G1, VA));
      Check_Has_Component (R, G1, "G1", Component (G1, VB));
      Check_Has_Component (R, G2, "G2", Component (G2, VX));
      Check_Has_Component (R, G2, "G2", Component (G2, VY));

      --  Verify that each graph does not contain components from the other
      --  graph.

      Check_No_Component (R, G1, "G1", Component (G2, VX));
      Check_No_Component (R, G1, "G1", Component (G2, VY));
      Check_No_Component (R, G2, "G2", Component (G1, VA));
      Check_No_Component (R, G2, "G2", Component (G1, VB));

      Destroy (G1);
      Destroy (G2);
   end Test_Contains_Component;

   ------------------------
   -- Test_Contains_Edge --
   ------------------------

   procedure Test_Contains_Edge is
      R : constant String := "Test_Contains_Edge";

      G : Directed_Graph := Create_And_Populate;

   begin
      --  Verify that all edges in the range E1 .. E10 exist

      for Curr_E in E1 .. E10 loop
         Check_Has_Edge (R, G, Curr_E);
      end loop;

      --  Verify that no extra edges are present

      for Curr_E in E97 .. E99 loop
         Check_No_Edge (R, G, Curr_E);
      end loop;

      --  Add new edges E97, E98, and E99

      Add_Edge (G, E97, Source => VG, Destination => VF);
      Add_Edge (G, E98, Source => VH, Destination => VE);
      Add_Edge (G, E99, Source => VD, Destination => VC);

      --  Verify that all edges in the range E1 .. E99 exist

      for Curr_E in E1 .. E99 loop
         Check_Has_Edge (R, G, Curr_E);
      end loop;

      --  Delete each edge that corresponds to an even position in Edge_Id

      for Curr_E in E1 .. E99 loop
         if Edge_Id'Pos (Curr_E) mod 2 = 0 then
            Delete_Edge (G, Curr_E);
         end if;
      end loop;

      --  Verify that all "even" edges are missing, and all "odd" edges are
      --  present.

      for Curr_E in E1 .. E99 loop
         if Edge_Id'Pos (Curr_E) mod 2 = 0 then
            Check_No_Edge (R, G, Curr_E);
         else
            Check_Has_Edge (R, G, Curr_E);
         end if;
      end loop;

      Destroy (G);
   end Test_Contains_Edge;

   --------------------------
   -- Test_Contains_Vertex --
   --------------------------

   procedure Test_Contains_Vertex is
      R : constant String := "Test_Contains_Vertex";

      G : Directed_Graph := Create_And_Populate;

   begin
      --  Verify that all vertices in the range VA .. VH exist

      for Curr_V in VA .. VH loop
         Check_Has_Vertex (R, G, Curr_V);
      end loop;

      --  Verify that no extra vertices are present

      for Curr_V in VX .. VZ loop
         Check_No_Vertex (R, G, Curr_V);
      end loop;

      --  Add new vertices VX, VY, and VZ

      Add_Vertex (G, VX);
      Add_Vertex (G, VY);
      Add_Vertex (G, VZ);

      --  Verify that all vertices in the range VA .. VZ exist

      for Curr_V in VA .. VZ loop
         Check_Has_Vertex (R, G, Curr_V);
      end loop;

      Destroy (G);
   end Test_Contains_Vertex;

   ----------------------
   -- Test_Delete_Edge --
   ----------------------

   procedure Test_Delete_Edge is
      R : constant String := "Test_Delete_Edge";

      E : Edge_Id;
      G : Directed_Graph := Create_And_Populate;
      V : Vertex_Id;

      All_E_Iter : All_Edge_Iterator;
      All_V_Iter : All_Vertex_Iterator;
      Out_E_Iter : Outgoing_Edge_Iterator;

   begin
      --  Try to delete a bogus edge

      begin
         Delete_Edge (G, E97);
         Error (R, "missing vertex deleted");
      exception
         when Missing_Edge => null;
         when others       => Unexpected_Exception (R);
      end;

      --  Delete edge E1 between vertices VA and VB

      begin
         Delete_Edge (G, E1);
      exception
         when others => Unexpected_Exception (R);
      end;

      --  Verify that edge E1 is gone from all edges in the graph

      All_E_Iter := Iterate_All_Edges (G);
      while Has_Next (All_E_Iter) loop
         Next (All_E_Iter, E);

         if E = E1 then
            Error (R, "edge " & E'Img & " not removed from all edges");
         end if;
      end loop;

      --  Verify that edge E1 is gone from the outgoing edges of vertex VA

      Out_E_Iter := Iterate_Outgoing_Edges (G, VA);
      while Has_Next (Out_E_Iter) loop
         Next (Out_E_Iter, E);

         if E = E1 then
            Error
              (R, "edge " & E'Img & "not removed from outgoing edges of VA");
         end if;
      end loop;

      --  Delete all edges in the range E2 .. E10

      for Curr_E in E2 .. E10 loop
         Delete_Edge (G, Curr_E);
      end loop;

      --  Verify that all edges are gone from the graph

      All_E_Iter := Iterate_All_Edges (G);
      while Has_Next (All_E_Iter) loop
         Next (All_E_Iter, E);

         Error (R, "edge " & E'Img & " not removed from all edges");
      end loop;

      --  Verify that all edges are gone from the respective source vertices

      All_V_Iter := Iterate_All_Vertices (G);
      while Has_Next (All_V_Iter) loop
         Next (All_V_Iter, V);

         Out_E_Iter := Iterate_Outgoing_Edges (G, V);
         while Has_Next (Out_E_Iter) loop
            Next (Out_E_Iter, E);

            Error (R, "edge " & E'Img & " not removed from vertex " & V'Img);
         end loop;
      end loop;

      Destroy (G);
   end Test_Delete_Edge;

   -----------------------------
   -- Test_Destination_Vertex --
   -----------------------------

   procedure Test_Destination_Vertex is
      R : constant String := "Test_Destination_Vertex";

      G : Directed_Graph := Create_And_Populate;

   begin
      --  Verify the destination vertices of all edges in the graph

      Check_Destination_Vertex (R, G, E1,  VB);
      Check_Destination_Vertex (R, G, E2,  VC);
      Check_Destination_Vertex (R, G, E3,  VC);
      Check_Destination_Vertex (R, G, E4,  VD);
      Check_Destination_Vertex (R, G, E5,  VB);
      Check_Destination_Vertex (R, G, E6,  VE);
      Check_Destination_Vertex (R, G, E7,  VD);
      Check_Destination_Vertex (R, G, E8,  VF);
      Check_Destination_Vertex (R, G, E9,  VG);
      Check_Destination_Vertex (R, G, E10, VA);

      Destroy (G);
   end Test_Destination_Vertex;

   --------------------------
   -- Test_Find_Components --
   --------------------------

   procedure Test_Find_Components is
      R : constant String := "Test_Find_Components";

      G : Directed_Graph := Create_And_Populate;

      Comp_1 : Component_Id;  --  [A, F, G]
      Comp_2 : Component_Id;  --  [B]
      Comp_3 : Component_Id;  --  [C]
      Comp_4 : Component_Id;  --  [D, E]
      Comp_5 : Component_Id;  --  [H]

   begin
      Find_Components (G);

      --  Vertices should belong to a component

      Check_Belongs_To_Some_Component (R, G, VA);
      Check_Belongs_To_Some_Component (R, G, VB);
      Check_Belongs_To_Some_Component (R, G, VC);
      Check_Belongs_To_Some_Component (R, G, VD);
      Check_Belongs_To_Some_Component (R, G, VH);

      --  Extract the ids of the components from the first vertices in each
      --  component.

      Comp_1 := Component (G, VA);
      Comp_2 := Component (G, VB);
      Comp_3 := Component (G, VC);
      Comp_4 := Component (G, VD);
      Comp_5 := Component (G, VH);

      --  Verify that the components are distinct

      Check_Distinct_Components (R, Comp_1, Comp_2);
      Check_Distinct_Components (R, Comp_1, Comp_3);
      Check_Distinct_Components (R, Comp_1, Comp_4);
      Check_Distinct_Components (R, Comp_1, Comp_5);

      Check_Distinct_Components (R, Comp_2, Comp_3);
      Check_Distinct_Components (R, Comp_2, Comp_4);
      Check_Distinct_Components (R, Comp_2, Comp_5);

      Check_Distinct_Components (R, Comp_3, Comp_4);
      Check_Distinct_Components (R, Comp_3, Comp_5);

      Check_Distinct_Components (R, Comp_4, Comp_5);

      --  Verify that the remaining nodes belong to the proper component

      Check_Belongs_To_Component (R, G, VF, Comp_1);
      Check_Belongs_To_Component (R, G, VG, Comp_1);
      Check_Belongs_To_Component (R, G, VE, Comp_4);

      Destroy (G);
   end Test_Find_Components;

   -------------------
   -- Test_Is_Empty --
   -------------------

   procedure Test_Is_Empty is
      R : constant String := "Test_Is_Empty";

      G : Directed_Graph := Create (Initial_Vertices => 3, Initial_Edges => 2);

   begin
      --  Verify that a graph without vertices and edges is empty

      if not Is_Empty (G) then
         Error (R, "graph is empty");
      end if;

      --  Add vertices

      Add_Vertex (G, VA);
      Add_Vertex (G, VB);

      --  Verify that a graph with vertices and no edges is not empty

      if Is_Empty (G) then
         Error (R, "graph is not empty");
      end if;

      --  Add edges

      Add_Edge (G, E1, Source => VA, Destination => VB);

      --  Verify that a graph with vertices and edges is not empty

      if Is_Empty (G) then
         Error (R, "graph is not empty");
      end if;

      Destroy (G);
   end Test_Is_Empty;

   -------------------------------
   -- Test_Number_Of_Components --
   -------------------------------

   procedure Test_Number_Of_Components is
      R : constant String := "Test_Number_Of_Components";

      G : Directed_Graph := Create (Initial_Vertices => 3, Initial_Edges => 2);

   begin
      --  Verify that an empty graph has exactly 0 components

      Check_Number_Of_Components (R, G, 0);

      --      E1
      --    ----->
      --  VA       VB     VC
      --    <-----
      --      E2
      --
      --  Components:
      --
      --    [VA, VB]
      --    [VC]

      Add_Vertex (G, VA);
      Add_Vertex (G, VB);
      Add_Vertex (G, VC);

      Add_Edge (G, E1, Source => VA, Destination => VB);
      Add_Edge (G, E2, Source => VB, Destination => VA);

      --  Verify that the graph has exact 0 components even though it contains
      --  vertices and edges.

      Check_Number_Of_Components (R, G, 0);

      Find_Components (G);

      --  Verify that the graph has exactly 2 components

      Check_Number_Of_Components (R, G, 2);

      Destroy (G);
   end Test_Number_Of_Components;

   --------------------------
   -- Test_Number_Of_Edges --
   --------------------------

   procedure Test_Number_Of_Edges is
      R : constant String := "Test_Number_Of_Edges";

      G : Directed_Graph := Create_And_Populate;

   begin
      --  Verify that the graph has exactly 10 edges

      Check_Number_Of_Edges (R, G, 10);

      --  Delete two edges

      Delete_Edge (G, E1);
      Delete_Edge (G, E2);

      --  Verify that the graph has exactly 8 edges

      Check_Number_Of_Edges (R, G, 8);

      --  Delete the remaining edge

      for Curr_E in E3 .. E10 loop
         Delete_Edge (G, Curr_E);
      end loop;

      --  Verify that the graph has exactly 0 edges

      Check_Number_Of_Edges (R, G, 0);

      --  Add two edges

      Add_Edge (G, E1, Source => VF, Destination => VA);
      Add_Edge (G, E2, Source => VC, Destination => VH);

      --  Verify that the graph has exactly 2 edges

      Check_Number_Of_Edges (R, G, 2);

      Destroy (G);
   end Test_Number_Of_Edges;

   -----------------------------
   -- Test_Number_Of_Vertices --
   -----------------------------

   procedure Test_Number_Of_Vertices is
      R : constant String := "Test_Number_Of_Vertices";

      G : Directed_Graph :=
            Create (Initial_Vertices => 4, Initial_Edges => 12);

   begin
      --  Verify that an empty graph has exactly 0 vertices

      Check_Number_Of_Vertices (R, G, 0);

      --  Add three vertices

      Add_Vertex (G, VC);
      Add_Vertex (G, VG);
      Add_Vertex (G, VX);

      --  Verify that the graph has exactly 3 vertices

      Check_Number_Of_Vertices (R, G, 3);

      --  Add one edge

      Add_Edge (G, E8, Source => VX, Destination => VG);

      --  Verify that the graph has exactly 3 vertices

      Check_Number_Of_Vertices (R, G, 3);

      Destroy (G);
   end Test_Number_Of_Vertices;

   ---------------------------------
   -- Test_Outgoing_Edge_Iterator --
   ---------------------------------

   procedure Test_Outgoing_Edge_Iterator is
      R : constant String := "Test_Outgoing_Edge_Iterator";

      G   : Directed_Graph := Create_And_Populate;
      Set : ES.Membership_Set;

   begin
      Set := ES.Create (4);

      ES.Insert (Set, E1);
      ES.Insert (Set, E3);
      ES.Insert (Set, E4);
      ES.Insert (Set, E8);
      Check_Outgoing_Edge_Iterator (R, G, VA, Set);

      ES.Insert (Set, E2);
      Check_Outgoing_Edge_Iterator (R, G, VB, Set);

      Check_Outgoing_Edge_Iterator (R, G, VC, Set);

      ES.Insert (Set, E5);
      ES.Insert (Set, E6);
      Check_Outgoing_Edge_Iterator (R, G, VD, Set);

      ES.Insert (Set, E7);
      Check_Outgoing_Edge_Iterator (R, G, VE, Set);

      ES.Insert (Set, E9);
      Check_Outgoing_Edge_Iterator (R, G, VF, Set);

      ES.Insert (Set, E10);
      Check_Outgoing_Edge_Iterator (R, G, VG, Set);

      Check_Outgoing_Edge_Iterator (R, G, VH, Set);

      ES.Destroy (Set);
      Destroy (G);
   end Test_Outgoing_Edge_Iterator;

   ------------------
   -- Test_Present --
   ------------------

   procedure Test_Present is
      R : constant String := "Test_Present";

      G : Directed_Graph := Nil;

   begin
      --  Verify that a non-existent graph is not present

      if Present (G) then
         Error (R, "graph is not present");
      end if;

      G := Create_And_Populate;

      --  Verify that an existing graph is present

      if not Present (G) then
         Error (R, "graph is present");
      end if;

      Destroy (G);

      --  Verify that a destroyed graph is not present

      if Present (G) then
         Error (R, "graph is not present");
      end if;
   end Test_Present;

   ------------------------
   -- Test_Source_Vertex --
   ------------------------

   procedure Test_Source_Vertex is
      R : constant String := "Test_Source_Vertex";

      G : Directed_Graph := Create_And_Populate;

   begin
      --  Verify the source vertices of all edges in the graph

      Check_Source_Vertex (R, G, E1,  VA);
      Check_Source_Vertex (R, G, E2,  VB);
      Check_Source_Vertex (R, G, E3,  VA);
      Check_Source_Vertex (R, G, E4,  VA);
      Check_Source_Vertex (R, G, E5,  VD);
      Check_Source_Vertex (R, G, E6,  VD);
      Check_Source_Vertex (R, G, E7,  VE);
      Check_Source_Vertex (R, G, E8,  VA);
      Check_Source_Vertex (R, G, E9,  VF);
      Check_Source_Vertex (R, G, E10, VG);

      Destroy (G);
   end Test_Source_Vertex;

   --------------------------
   -- Test_Vertex_Iterator --
   --------------------------

   procedure Test_Vertex_Iterator is
      R : constant String := "Test_Vertex_Iterator";

      G   : Directed_Graph := Create_And_Populate;
      Set : VS.Membership_Set;

   begin
      Find_Components (G);

      Set := VS.Create (3);

      VS.Insert (Set, VA);
      VS.Insert (Set, VF);
      VS.Insert (Set, VG);
      Check_Vertex_Iterator (R, G, Component (G, VA), Set);

      VS.Insert (Set, VB);
      Check_Vertex_Iterator (R, G, Component (G, VB), Set);

      VS.Insert (Set, VC);
      Check_Vertex_Iterator (R, G, Component (G, VC), Set);

      VS.Insert (Set, VD);
      VS.Insert (Set, VE);
      Check_Vertex_Iterator (R, G, Component (G, VD), Set);

      VS.Insert (Set, VH);
      Check_Vertex_Iterator (R, G, Component (G, VH), Set);

      VS.Destroy (Set);
      Destroy (G);
   end Test_Vertex_Iterator;

   --------------------------
   -- Unexpected_Exception --
   --------------------------

   procedure Unexpected_Exception (R : String) is
   begin
      Error (R, "unexpected exception");
   end Unexpected_Exception;

--  Start of processing for Operations

begin
   Test_Add_Edge;
   Test_Add_Vertex;
   Test_All_Edge_Iterator;
   Test_All_Vertex_Iterator;
   Test_Component;
   Test_Component_Iterator;
   Test_Contains_Component;
   Test_Contains_Edge;
   Test_Contains_Vertex;
   Test_Delete_Edge;
   Test_Destination_Vertex;
   Test_Find_Components;
   Test_Is_Empty;
   Test_Number_Of_Components;
   Test_Number_Of_Edges;
   Test_Number_Of_Vertices;
   Test_Outgoing_Edge_Iterator;
   Test_Present;
   Test_Source_Vertex;
   Test_Vertex_Iterator;

end Operations;

----------------------------
-- Compilation and output --
----------------------------

$ gnatmake -q operations.adb -largs -lgmem
$ ./operations
$ gnatmem operations > leaks.txt
$ grep -c "non freed allocations" leaks.txt
0

2019-07-01  Hristian Kirtchev  <kirtchev@adacore.com>

gcc/ada/

	* libgnat/g-graphs.adb: Use type Directed_Graph rather than
	Instance in various routines.
	* libgnat/g-graphs.ads: Change type Instance to Directed_Graph.
	Update various routines that mention the type.

From-SVN: r272863

3 files changed, 127 insertions, 116 deletions

diff --git a/gcc/ada/ChangeLog b/gcc/ada/ChangeLog
index 05aaf23..f11697b2 100644
--- a/gcc/ada/ChangeLog
+++ b/gcc/ada/ChangeLog
@@ -1,5 +1,12 @@
 2019-07-01  Hristian Kirtchev  <kirtchev@adacore.com>
 
+	* libgnat/g-graphs.adb: Use type Directed_Graph rather than
+	Instance in various routines.
+	* libgnat/g-graphs.ads: Change type Instance to Directed_Graph.
+	Update various routines that mention the type.
+
+2019-07-01  Hristian Kirtchev  <kirtchev@adacore.com>
+
 	* libgnat/g-sets.adb: Use type Membership_Set rathern than
 	Instance in various routines.
 	* libgnat/g-sets.ads: Change type Instance to Membership_Set.
diff --git a/gcc/ada/libgnat/g-graphs.adb b/gcc/ada/libgnat/g-graphs.adb
index a763efb..210e083 100644
--- a/gcc/ada/libgnat/g-graphs.adb
+++ b/gcc/ada/libgnat/g-graphs.adb
@@ -45,107 +45,109 @@ package body GNAT.Graphs is
    -- Directed_Graph --
    --------------------
 
-   package body Directed_Graph is
+   package body Directed_Graphs is
 
       -----------------------
       -- Local subprograms --
       -----------------------
 
       procedure Add_Component
-        (G        : Instance;
+        (G        : Directed_Graph;
          Comp     : Component_Id;
-         Vertices : Vertex_List.Instance);
+         Vertices : Vertex_List.Doubly_Linked_List);
       pragma Inline (Add_Component);
       --  Add component Comp which houses vertices Vertices to graph G
 
-      procedure Ensure_Created (G : Instance);
+      procedure Ensure_Created (G : Directed_Graph);
       pragma Inline (Ensure_Created);
       --  Verify that graph G is created. Raise Not_Created if this is not the
       --  case.
 
       procedure Ensure_Not_Present
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id);
       pragma Inline (Ensure_Not_Present);
       --  Verify that graph G lacks edge E. Raise Duplicate_Edge if this is not
       --  the case.
 
       procedure Ensure_Not_Present
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id);
       pragma Inline (Ensure_Not_Present);
       --  Verify that graph G lacks vertex V. Raise Duplicate_Vertex if this is
       --  not the case.
 
       procedure Ensure_Present
-        (G    : Instance;
+        (G    : Directed_Graph;
          Comp : Component_Id);
       pragma Inline (Ensure_Present);
       --  Verify that component Comp exists in graph G. Raise Missing_Component
       --  if this is not the case.
 
       procedure Ensure_Present
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id);
       pragma Inline (Ensure_Present);
       --  Verify that edge E is present in graph G. Raise Missing_Edge if this
       --  is not the case.
 
       procedure Ensure_Present
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id);
       pragma Inline (Ensure_Present);
       --  Verify that vertex V is present in graph G. Raise Missing_Vertex if
       --  this is not the case.
 
-      procedure Free is new Ada.Unchecked_Deallocation (Graph, Instance);
+      procedure Free is
+        new Ada.Unchecked_Deallocation
+              (Directed_Graph_Attributes, Directed_Graph);
 
       function Get_Component_Attributes
-        (G    : Instance;
+        (G    : Directed_Graph;
          Comp : Component_Id) return Component_Attributes;
       pragma Inline (Get_Component_Attributes);
       --  Obtain the attributes of component Comp of graph G
 
       function Get_Edge_Attributes
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id) return Edge_Attributes;
       pragma Inline (Get_Edge_Attributes);
       --  Obtain the attributes of edge E of graph G
 
       function Get_Vertex_Attributes
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id) return Vertex_Attributes;
       pragma Inline (Get_Vertex_Attributes);
       --  Obtain the attributes of vertex V of graph G
 
       function Get_Outgoing_Edges
-        (G : Instance;
-         V : Vertex_Id) return Edge_Set.Instance;
+        (G : Directed_Graph;
+         V : Vertex_Id) return Edge_Set.Membership_Set;
       pragma Inline (Get_Outgoing_Edges);
       --  Obtain the Outgoing_Edges attribute of vertex V of graph G
 
       function Get_Vertices
-        (G    : Instance;
-         Comp : Component_Id) return Vertex_List.Instance;
+        (G    : Directed_Graph;
+         Comp : Component_Id) return Vertex_List.Doubly_Linked_List;
       pragma Inline (Get_Vertices);
       --  Obtain the Vertices attribute of component Comp of graph G
 
       procedure Set_Component
-        (G   : Instance;
+        (G   : Directed_Graph;
          V   : Vertex_Id;
          Val : Component_Id);
       pragma Inline (Set_Component);
       --  Set attribute Component of vertex V of graph G to value Val
 
       procedure Set_Outgoing_Edges
-        (G   : Instance;
+        (G   : Directed_Graph;
          V   : Vertex_Id;
-         Val : Edge_Set.Instance);
+         Val : Edge_Set.Membership_Set);
       pragma Inline (Set_Outgoing_Edges);
       --  Set attribute Outgoing_Edges of vertex V of graph G to value Val
 
       procedure Set_Vertex_Attributes
-        (G   : Instance;
+        (G   : Directed_Graph;
          V   : Vertex_Id;
          Val : Vertex_Attributes);
       pragma Inline (Set_Vertex_Attributes);
@@ -156,9 +158,9 @@ package body GNAT.Graphs is
       -------------------
 
       procedure Add_Component
-        (G        : Instance;
+        (G        : Directed_Graph;
          Comp     : Component_Id;
-         Vertices : Vertex_List.Instance)
+         Vertices : Vertex_List.Doubly_Linked_List)
       is
       begin
          pragma Assert (Present (G));
@@ -176,7 +178,7 @@ package body GNAT.Graphs is
       --------------
 
       procedure Add_Edge
-        (G           : Instance;
+        (G           : Directed_Graph;
          E           : Edge_Id;
          Source      : Vertex_Id;
          Destination : Vertex_Id)
@@ -209,7 +211,7 @@ package body GNAT.Graphs is
       ----------------
 
       procedure Add_Vertex
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id)
       is
       begin
@@ -239,7 +241,7 @@ package body GNAT.Graphs is
       ---------------
 
       function Component
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id) return Component_Id
       is
       begin
@@ -254,7 +256,7 @@ package body GNAT.Graphs is
       ------------------------
 
       function Contains_Component
-        (G    : Instance;
+        (G    : Directed_Graph;
          Comp : Component_Id) return Boolean
       is
       begin
@@ -268,7 +270,7 @@ package body GNAT.Graphs is
       -------------------
 
       function Contains_Edge
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id) return Boolean
       is
       begin
@@ -282,7 +284,7 @@ package body GNAT.Graphs is
       ---------------------
 
       function Contains_Vertex
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id) return Boolean
       is
       begin
@@ -297,9 +299,9 @@ package body GNAT.Graphs is
 
       function Create
         (Initial_Vertices : Positive;
-         Initial_Edges    : Positive) return Instance
+         Initial_Edges    : Positive) return Directed_Graph
       is
-         G : constant Instance := new Graph;
+         G : constant Directed_Graph := new Directed_Graph_Attributes;
 
       begin
          G.All_Edges    := Edge_Map.Create      (Initial_Edges);
@@ -314,7 +316,7 @@ package body GNAT.Graphs is
       -----------------
 
       procedure Delete_Edge
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id)
       is
          Source : Vertex_Id;
@@ -341,7 +343,7 @@ package body GNAT.Graphs is
       ------------------------
 
       function Destination_Vertex
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id) return Vertex_Id
       is
       begin
@@ -355,7 +357,7 @@ package body GNAT.Graphs is
       -- Destroy --
       -------------
 
-      procedure Destroy (G : in out Instance) is
+      procedure Destroy (G : in out Directed_Graph) is
       begin
          Ensure_Created (G);
 
@@ -410,7 +412,7 @@ package body GNAT.Graphs is
       -- Ensure_Created --
       --------------------
 
-      procedure Ensure_Created (G : Instance) is
+      procedure Ensure_Created (G : Directed_Graph) is
       begin
          if not Present (G) then
             raise Not_Created;
@@ -422,7 +424,7 @@ package body GNAT.Graphs is
       ------------------------
 
       procedure Ensure_Not_Present
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id)
       is
       begin
@@ -436,7 +438,7 @@ package body GNAT.Graphs is
       ------------------------
 
       procedure Ensure_Not_Present
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id)
       is
       begin
@@ -450,7 +452,7 @@ package body GNAT.Graphs is
       --------------------
 
       procedure Ensure_Present
-        (G    : Instance;
+        (G    : Directed_Graph;
          Comp : Component_Id)
       is
       begin
@@ -464,7 +466,7 @@ package body GNAT.Graphs is
       --------------------
 
       procedure Ensure_Present
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id)
       is
       begin
@@ -478,7 +480,7 @@ package body GNAT.Graphs is
       --------------------
 
       procedure Ensure_Present
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id)
       is
       begin
@@ -491,7 +493,7 @@ package body GNAT.Graphs is
       -- Find_Components --
       ---------------------
 
-      procedure Find_Components (G : Instance) is
+      procedure Find_Components (G : Directed_Graph) is
 
          --  The components of graph G are discovered using Tarjan's strongly
          --  connected component algorithm. Do not modify this code unless you
@@ -527,7 +529,7 @@ package body GNAT.Graphs is
            (Attrs : in out Tarjan_Attributes);
          --  Destroy the contents of attributes Attrs
 
-         package Tarjan_Map is new Dynamic_HTable
+         package Tarjan_Map is new Dynamic_Hash_Tables
            (Key_Type              => Vertex_Id,
             Value_Type            => Tarjan_Attributes,
             No_Value              => No_Tarjan_Attributes,
@@ -543,7 +545,7 @@ package body GNAT.Graphs is
          -- Tarjan_Stack --
          ------------------
 
-         package Tarjan_Stack is new Doubly_Linked_List
+         package Tarjan_Stack is new Doubly_Linked_Lists
            (Element_Type    => Vertex_Id,
             "="             => Same_Vertex,
             Destroy_Element => Destroy_Vertex);
@@ -552,8 +554,8 @@ package body GNAT.Graphs is
          -- Global data --
          -----------------
 
-         Attrs : Tarjan_Map.Instance   := Tarjan_Map.Nil;
-         Stack : Tarjan_Stack.Instance := Tarjan_Stack.Nil;
+         Attrs : Tarjan_Map.Dynamic_Hash_Table   := Tarjan_Map.Nil;
+         Stack : Tarjan_Stack.Doubly_Linked_List := Tarjan_Stack.Nil;
 
          -----------------------
          -- Local subprograms --
@@ -689,7 +691,7 @@ package body GNAT.Graphs is
 
          procedure Create_Component (V : Vertex_Id) is
             Curr_V   : Vertex_Id;
-            Vertices : Vertex_List.Instance;
+            Vertices : Vertex_List.Doubly_Linked_List;
 
          begin
             Vertices := Vertex_List.Create;
@@ -1047,7 +1049,7 @@ package body GNAT.Graphs is
       ------------------------------
 
       function Get_Component_Attributes
-        (G    : Instance;
+        (G    : Directed_Graph;
          Comp : Component_Id) return Component_Attributes
       is
       begin
@@ -1062,7 +1064,7 @@ package body GNAT.Graphs is
       -------------------------
 
       function Get_Edge_Attributes
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id) return Edge_Attributes
       is
       begin
@@ -1077,7 +1079,7 @@ package body GNAT.Graphs is
       ---------------------------
 
       function Get_Vertex_Attributes
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id) return Vertex_Attributes
       is
       begin
@@ -1092,8 +1094,8 @@ package body GNAT.Graphs is
       ------------------------
 
       function Get_Outgoing_Edges
-        (G : Instance;
-         V : Vertex_Id) return Edge_Set.Instance
+        (G : Directed_Graph;
+         V : Vertex_Id) return Edge_Set.Membership_Set
       is
       begin
          pragma Assert (Present (G));
@@ -1107,8 +1109,8 @@ package body GNAT.Graphs is
       ------------------
 
       function Get_Vertices
-        (G    : Instance;
-         Comp : Component_Id) return Vertex_List.Instance
+        (G    : Directed_Graph;
+         Comp : Component_Id) return Vertex_List.Doubly_Linked_List
       is
       begin
          pragma Assert (Present (G));
@@ -1166,7 +1168,7 @@ package body GNAT.Graphs is
       -- Is_Empty --
       --------------
 
-      function Is_Empty (G : Instance) return Boolean is
+      function Is_Empty (G : Directed_Graph) return Boolean is
       begin
          Ensure_Created (G);
 
@@ -1179,7 +1181,9 @@ package body GNAT.Graphs is
       -- Iterate_All_Edges --
       -----------------------
 
-      function Iterate_All_Edges (G : Instance) return All_Edge_Iterator is
+      function Iterate_All_Edges
+        (G : Directed_Graph) return All_Edge_Iterator
+      is
       begin
          Ensure_Created (G);
 
@@ -1191,7 +1195,7 @@ package body GNAT.Graphs is
       --------------------------
 
       function Iterate_All_Vertices
-        (G : Instance) return All_Vertex_Iterator
+        (G : Directed_Graph) return All_Vertex_Iterator
       is
       begin
          Ensure_Created (G);
@@ -1203,7 +1207,9 @@ package body GNAT.Graphs is
       -- Iterate_Components --
       ------------------------
 
-      function Iterate_Components (G : Instance) return Component_Iterator is
+      function Iterate_Components
+        (G : Directed_Graph) return Component_Iterator
+      is
       begin
          Ensure_Created (G);
 
@@ -1215,7 +1221,7 @@ package body GNAT.Graphs is
       ----------------------------
 
       function Iterate_Outgoing_Edges
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id) return Outgoing_Edge_Iterator
       is
       begin
@@ -1232,7 +1238,7 @@ package body GNAT.Graphs is
       ----------------------
 
       function Iterate_Vertices
-        (G    : Instance;
+        (G    : Directed_Graph;
          Comp : Component_Id) return Vertex_Iterator
       is
       begin
@@ -1306,7 +1312,7 @@ package body GNAT.Graphs is
       -- Number_Of_Components --
       --------------------------
 
-      function Number_Of_Components (G : Instance) return Natural is
+      function Number_Of_Components (G : Directed_Graph) return Natural is
       begin
          Ensure_Created (G);
 
@@ -1317,7 +1323,7 @@ package body GNAT.Graphs is
       -- Number_Of_Edges --
       ---------------------
 
-      function Number_Of_Edges (G : Instance) return Natural is
+      function Number_Of_Edges (G : Directed_Graph) return Natural is
       begin
          Ensure_Created (G);
 
@@ -1328,7 +1334,7 @@ package body GNAT.Graphs is
       -- Number_Of_Vertices --
       ------------------------
 
-      function Number_Of_Vertices (G : Instance) return Natural is
+      function Number_Of_Vertices (G : Directed_Graph) return Natural is
       begin
          Ensure_Created (G);
 
@@ -1339,7 +1345,7 @@ package body GNAT.Graphs is
       -- Present --
       -------------
 
-      function Present (G : Instance) return Boolean is
+      function Present (G : Directed_Graph) return Boolean is
       begin
          return G /= Nil;
       end Present;
@@ -1349,7 +1355,7 @@ package body GNAT.Graphs is
       -------------------
 
       procedure Set_Component
-        (G   : Instance;
+        (G   : Directed_Graph;
          V   : Vertex_Id;
          Val : Component_Id)
       is
@@ -1369,9 +1375,9 @@ package body GNAT.Graphs is
       ------------------------
 
       procedure Set_Outgoing_Edges
-        (G   : Instance;
+        (G   : Directed_Graph;
          V   : Vertex_Id;
-         Val : Edge_Set.Instance)
+         Val : Edge_Set.Membership_Set)
       is
          VA : Vertex_Attributes;
 
@@ -1389,7 +1395,7 @@ package body GNAT.Graphs is
       ---------------------------
 
       procedure Set_Vertex_Attributes
-        (G   : Instance;
+        (G   : Directed_Graph;
          V   : Vertex_Id;
          Val : Vertex_Attributes)
       is
@@ -1405,7 +1411,7 @@ package body GNAT.Graphs is
       -------------------
 
       function Source_Vertex
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id) return Vertex_Id
       is
       begin
@@ -1414,7 +1420,7 @@ package body GNAT.Graphs is
 
          return Get_Edge_Attributes (G, E).Source;
       end Source_Vertex;
-   end Directed_Graph;
+   end Directed_Graphs;
 
    --------------------
    -- Hash_Component --
diff --git a/gcc/ada/libgnat/g-graphs.ads b/gcc/ada/libgnat/g-graphs.ads
index 7926a1b..c4bf17d 100644
--- a/gcc/ada/libgnat/g-graphs.ads
+++ b/gcc/ada/libgnat/g-graphs.ads
@@ -53,9 +53,9 @@ package GNAT.Graphs is
    function Present (Comp : Component_Id) return Boolean;
    --  Determine whether component Comp exists
 
-   --------------------
-   -- Directed_Graph --
-   --------------------
+   ---------------------
+   -- Directed_Graphs --
+   ---------------------
 
    --  The following package offers a directed graph abstraction with the
    --  following characteristics:
@@ -67,7 +67,7 @@ package GNAT.Graphs is
    --
    --  The following use pattern must be employed when operating this graph:
    --
-   --    Graph : Instance := Create (<some size>, <some size>);
+   --    Graph : Directed_Graph := Create (<some size>, <some size>);
    --
    --    <various operations>
    --
@@ -113,7 +113,7 @@ package GNAT.Graphs is
               Right : Edge_Id) return Boolean;
       --  Compare edge Left to edge Right for identity
 
-   package Directed_Graph is
+   package Directed_Graphs is
 
       --  The following exceptions are raised when an attempt is made to add
       --  the same edge or vertex in a graph.
@@ -135,11 +135,11 @@ package GNAT.Graphs is
       --  The following type denotes a graph handle. Each instance must be
       --  created using routine Create.
 
-      type Instance is private;
-      Nil : constant Instance;
+      type Directed_Graph is private;
+      Nil : constant Directed_Graph;
 
       procedure Add_Edge
-        (G           : Instance;
+        (G           : Directed_Graph;
          E           : Edge_Id;
          Source      : Vertex_Id;
          Destination : Vertex_Id);
@@ -155,7 +155,7 @@ package GNAT.Graphs is
       --      present in the graph.
 
       procedure Add_Vertex
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id);
       --  Add vertex V to graph G. This action raises the following exceptions:
       --
@@ -164,7 +164,7 @@ package GNAT.Graphs is
       --    * Iterated, when the graph has an outstanding vertex iterator
 
       function Component
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id) return Component_Id;
       --  Obtain the component where vertex V of graph G resides. This action
       --  raises the following exceptions:
@@ -172,29 +172,29 @@ package GNAT.Graphs is
       --    * Missing_Vertex, when the vertex is not present in the graph
 
       function Contains_Component
-        (G    : Instance;
+        (G    : Directed_Graph;
          Comp : Component_Id) return Boolean;
       --  Determine whether graph G contains component Comp
 
       function Contains_Edge
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id) return Boolean;
       --  Determine whether graph G contains edge E
 
       function Contains_Vertex
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id) return Boolean;
       --  Determine whether graph G contains vertex V
 
       function Create
         (Initial_Vertices : Positive;
-         Initial_Edges    : Positive) return Instance;
+         Initial_Edges    : Positive) return Directed_Graph;
       --  Create a new graph with vertex capacity Initial_Vertices and edge
       --  capacity Initial_Edges. This routine must be called at the start of
       --  a graph's lifetime.
 
       procedure Delete_Edge
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id);
       --  Delete edge E from graph G. This action raises these exceptions:
       --
@@ -206,44 +206,44 @@ package GNAT.Graphs is
       --      not present in the graph.
 
       function Destination_Vertex
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id) return Vertex_Id;
       --  Obtain the destination vertex of edge E of graph G. This action
       --  raises the following exceptions:
       --
       --    * Missing_Edge, when the edge is not present in the graph
 
-      procedure Destroy (G : in out Instance);
+      procedure Destroy (G : in out Directed_Graph);
       --  Destroy the contents of graph G, rendering it unusable. This routine
       --  must be called at the end of a graph's lifetime. This action raises
       --  the following exceptions:
       --
       --    * Iterated, if the graph has any outstanding iterator
 
-      procedure Find_Components (G : Instance);
+      procedure Find_Components (G : Directed_Graph);
       --  Find all components of graph G. This action raises the following
       --  exceptions:
       --
       --    * Iterated, when the components or vertices of the graph have an
       --      outstanding iterator.
 
-      function Is_Empty (G : Instance) return Boolean;
+      function Is_Empty (G : Directed_Graph) return Boolean;
       --  Determine whether graph G is empty
 
-      function Number_Of_Components (G : Instance) return Natural;
+      function Number_Of_Components (G : Directed_Graph) return Natural;
       --  Obtain the total number of components of graph G
 
-      function Number_Of_Edges (G : Instance) return Natural;
+      function Number_Of_Edges (G : Directed_Graph) return Natural;
       --  Obtain the total number of edges of graph G
 
-      function Number_Of_Vertices (G : Instance) return Natural;
+      function Number_Of_Vertices (G : Directed_Graph) return Natural;
       --  Obtain the total number of vertices of graph G
 
-      function Present (G : Instance) return Boolean;
+      function Present (G : Directed_Graph) return Boolean;
       --  Determine whether graph G exists
 
       function Source_Vertex
-        (G : Instance;
+        (G : Directed_Graph;
          E : Edge_Id) return Vertex_Id;
       --  Obtain the source vertex that "owns" edge E of graph G. This action
       --  raises the following exceptions:
@@ -274,7 +274,7 @@ package GNAT.Graphs is
       function Has_Next (Iter : All_Edge_Iterator) return Boolean;
       --  Determine whether iterator Iter has more edges to examine
 
-      function Iterate_All_Edges (G : Instance) return All_Edge_Iterator;
+      function Iterate_All_Edges (G : Directed_Graph) return All_Edge_Iterator;
       --  Obtain an iterator over all edges of graph G
 
       procedure Next
@@ -294,7 +294,8 @@ package GNAT.Graphs is
       function Has_Next (Iter : All_Vertex_Iterator) return Boolean;
       --  Determine whether iterator Iter has more vertices to examine
 
-      function Iterate_All_Vertices (G : Instance) return All_Vertex_Iterator;
+      function Iterate_All_Vertices
+        (G : Directed_Graph) return All_Vertex_Iterator;
       --  Obtain an iterator over all vertices of graph G
 
       procedure Next
@@ -315,7 +316,8 @@ package GNAT.Graphs is
       function Has_Next (Iter : Component_Iterator) return Boolean;
       --  Determine whether iterator Iter has more components to examine
 
-      function Iterate_Components (G : Instance) return Component_Iterator;
+      function Iterate_Components
+        (G : Directed_Graph) return Component_Iterator;
       --  Obtain an iterator over all components of graph G
 
       procedure Next
@@ -336,7 +338,7 @@ package GNAT.Graphs is
       --  Determine whether iterator Iter has more outgoing edges to examine
 
       function Iterate_Outgoing_Edges
-        (G : Instance;
+        (G : Directed_Graph;
          V : Vertex_Id) return Outgoing_Edge_Iterator;
       --  Obtain an iterator over all the outgoing edges "owned" by vertex V of
       --  graph G.
@@ -360,7 +362,7 @@ package GNAT.Graphs is
       --  Determine whether iterator Iter has more vertices to examine
 
       function Iterate_Vertices
-        (G    : Instance;
+        (G    : Directed_Graph;
          Comp : Component_Id) return Vertex_Iterator;
       --  Obtain an iterator over all vertices that comprise component Comp of
       --  graph G.
@@ -396,7 +398,7 @@ package GNAT.Graphs is
       procedure Destroy_Edge_Attributes (Attrs : in out Edge_Attributes);
       --  Destroy the contents of attributes Attrs
 
-      package Edge_Map is new Dynamic_HTable
+      package Edge_Map is new Dynamic_Hash_Tables
         (Key_Type              => Edge_Id,
          Value_Type            => Edge_Attributes,
          No_Value              => No_Edge_Attributes,
@@ -412,7 +414,7 @@ package GNAT.Graphs is
       -- Edge_Set --
       --------------
 
-      package Edge_Set is new Membership_Set
+      package Edge_Set is new Membership_Sets
         (Element_Type => Edge_Id,
          "="          => "=",
          Hash         => Hash_Edge);
@@ -424,7 +426,7 @@ package GNAT.Graphs is
       procedure Destroy_Vertex (V : in out Vertex_Id);
       --  Destroy the contents of a vertex
 
-      package Vertex_List is new Doubly_Linked_List
+      package Vertex_List is new Doubly_Linked_Lists
         (Element_Type    => Vertex_Id,
          "="             => Same_Vertex,
          Destroy_Element => Destroy_Vertex);
@@ -437,7 +439,7 @@ package GNAT.Graphs is
          Component : Component_Id := No_Component;
          --  The component where a vertex lives
 
-         Outgoing_Edges : Edge_Set.Instance := Edge_Set.Nil;
+         Outgoing_Edges : Edge_Set.Membership_Set := Edge_Set.Nil;
          --  The set of edges that extend out from a vertex
       end record;
 
@@ -448,7 +450,7 @@ package GNAT.Graphs is
       procedure Destroy_Vertex_Attributes (Attrs : in out Vertex_Attributes);
       --  Destroy the contents of attributes Attrs
 
-      package Vertex_Map is new Dynamic_HTable
+      package Vertex_Map is new Dynamic_Hash_Tables
         (Key_Type              => Vertex_Id,
          Value_Type            => Vertex_Attributes,
          No_Value              => No_Vertex_Attributes,
@@ -465,7 +467,7 @@ package GNAT.Graphs is
       -------------------
 
       type Component_Attributes is record
-         Vertices : Vertex_List.Instance := Vertex_List.Nil;
+         Vertices : Vertex_List.Doubly_Linked_List := Vertex_List.Nil;
       end record;
 
       No_Component_Attributes : constant Component_Attributes :=
@@ -475,7 +477,7 @@ package GNAT.Graphs is
         (Attrs : in out Component_Attributes);
       --  Destroy the contents of attributes Attrs
 
-      package Component_Map is new Dynamic_HTable
+      package Component_Map is new Dynamic_Hash_Tables
         (Key_Type              => Component_Id,
          Value_Type            => Component_Attributes,
          No_Value              => No_Component_Attributes,
@@ -491,25 +493,21 @@ package GNAT.Graphs is
       -- Graph --
       -----------
 
-      type Graph is record
-         All_Edges : Edge_Map.Instance := Edge_Map.Nil;
+      type Directed_Graph_Attributes is record
+         All_Edges : Edge_Map.Dynamic_Hash_Table := Edge_Map.Nil;
          --  The map of edge -> edge attributes for all edges in the graph
 
-         All_Vertices : Vertex_Map.Instance := Vertex_Map.Nil;
+         All_Vertices : Vertex_Map.Dynamic_Hash_Table := Vertex_Map.Nil;
          --  The map of vertex -> vertex attributes for all vertices in the
          --  graph.
 
-         Components : Component_Map.Instance := Component_Map.Nil;
+         Components : Component_Map.Dynamic_Hash_Table := Component_Map.Nil;
          --  The map of component -> component attributes for all components
          --  in the graph.
       end record;
 
-      --------------
-      -- Instance --
-      --------------
-
-      type Instance is access Graph;
-      Nil : constant Instance := null;
+      type Directed_Graph is access Directed_Graph_Attributes;
+      Nil : constant Directed_Graph := null;
 
       ---------------
       -- Iterators --
@@ -520,7 +518,7 @@ package GNAT.Graphs is
       type Component_Iterator     is new Component_Map.Iterator;
       type Outgoing_Edge_Iterator is new Edge_Set.Iterator;
       type Vertex_Iterator        is new Vertex_List.Iterator;
-   end Directed_Graph;
+   end Directed_Graphs;
 
 private
    No_Component    : constant Component_Id := Component_Id'First;