| ------------------------------------------------------------------------------ |
| -- -- |
| -- GNAT RUN-TIME COMPONENTS -- |
| -- -- |
| -- G N A T . G R A P H S -- |
| -- -- |
| -- S p e c -- |
| -- -- |
| -- Copyright (C) 2018-2021, Free Software Foundation, Inc. -- |
| -- -- |
| -- GNAT is free software; you can redistribute it and/or modify it under -- |
| -- terms of the GNU General Public License as published by the Free Soft- -- |
| -- ware Foundation; either version 3, or (at your option) any later ver- -- |
| -- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- |
| -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- |
| -- or FITNESS FOR A PARTICULAR PURPOSE. -- |
| -- -- |
| -- As a special exception under Section 7 of GPL version 3, you are granted -- |
| -- additional permissions described in the GCC Runtime Library Exception, -- |
| -- version 3.1, as published by the Free Software Foundation. -- |
| -- -- |
| -- You should have received a copy of the GNU General Public License and -- |
| -- a copy of the GCC Runtime Library Exception along with this program; -- |
| -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -- |
| -- <http://www.gnu.org/licenses/>. -- |
| -- -- |
| -- GNAT was originally developed by the GNAT team at New York University. -- |
| -- Extensive contributions were provided by Ada Core Technologies Inc. -- |
| -- -- |
| ------------------------------------------------------------------------------ |
| |
| pragma Compiler_Unit_Warning; |
| |
| with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables; |
| with GNAT.Lists; use GNAT.Lists; |
| with GNAT.Sets; use GNAT.Sets; |
| |
| package GNAT.Graphs is |
| |
| --------------- |
| -- Component -- |
| --------------- |
| |
| -- The following type denotes a strongly connected component handle |
| -- (referred to as simply "component") in a graph. |
| |
| type Component_Id is new Natural; |
| No_Component : constant Component_Id := Component_Id'First; |
| |
| function Hash_Component (Comp : Component_Id) return Bucket_Range_Type; |
| -- Map component Comp into the range of buckets |
| |
| function Present (Comp : Component_Id) return Boolean; |
| -- Determine whether component Comp exists |
| |
| --------------------- |
| -- Directed_Graphs -- |
| --------------------- |
| |
| -- The following package offers a directed graph abstraction with the |
| -- following characteristics: |
| -- |
| -- * Dynamic resizing based on number of vertices and edges |
| -- * Creation of multiple instances, of different sizes |
| -- * Discovery of strongly connected components |
| -- * Iterable attributes |
| -- |
| -- The following use pattern must be employed when operating this graph: |
| -- |
| -- Graph : Directed_Graph := Create (<some size>, <some size>); |
| -- |
| -- <various operations> |
| -- |
| -- Destroy (Graph); |
| -- |
| -- The destruction of the graph reclaims all storage occupied by it. |
| |
| generic |
| |
| -------------- |
| -- Vertices -- |
| -------------- |
| |
| type Vertex_Id is private; |
| -- The handle of a vertex |
| |
| No_Vertex : Vertex_Id; |
| -- An indicator for a nonexistent vertex |
| |
| with function Hash_Vertex (V : Vertex_Id) return Bucket_Range_Type; |
| -- Map vertex V into the range of buckets |
| |
| with function Same_Vertex |
| (Left : Vertex_Id; |
| Right : Vertex_Id) return Boolean; |
| -- Compare vertex Left to vertex Right for identity |
| |
| ----------- |
| -- Edges -- |
| ----------- |
| |
| type Edge_Id is private; |
| -- The handle of an edge |
| |
| No_Edge : Edge_Id; |
| -- An indicator for a nonexistent edge |
| |
| with function Hash_Edge (E : Edge_Id) return Bucket_Range_Type; |
| -- Map edge E into the range of buckets |
| |
| with function Same_Edge |
| (Left : Edge_Id; |
| Right : Edge_Id) return Boolean; |
| -- Compare edge Left to edge Right for identity |
| |
| package Directed_Graphs is |
| |
| -- The following exceptions are raised when an attempt is made to add |
| -- the same edge or vertex in a graph. |
| |
| Duplicate_Edge : exception; |
| Duplicate_Vertex : exception; |
| |
| -- The following exceptions are raised when an attempt is made to delete |
| -- or reference a nonexistent component, edge, or vertex in a graph. |
| |
| Missing_Component : exception; |
| Missing_Edge : exception; |
| Missing_Vertex : exception; |
| |
| ---------------------- |
| -- Graph operations -- |
| ---------------------- |
| |
| -- The following type denotes a graph handle. Each instance must be |
| -- created using routine Create. |
| |
| type Directed_Graph is private; |
| Nil : constant Directed_Graph; |
| |
| procedure Add_Edge |
| (G : Directed_Graph; |
| E : Edge_Id; |
| Source : Vertex_Id; |
| Destination : Vertex_Id); |
| -- Add edge E to graph G which links vertex source Source and desination |
| -- vertex Destination. The edge is "owned" by vertex Source. This action |
| -- raises the following exceptions: |
| -- |
| -- * Duplicate_Edge, when the edge is already present in the graph |
| -- |
| -- * Iterated, when the graph has an outstanding edge iterator |
| -- |
| -- * Missing_Vertex, when either the source or desination are not |
| -- present in the graph. |
| |
| procedure Add_Vertex |
| (G : Directed_Graph; |
| V : Vertex_Id); |
| -- Add vertex V to graph G. This action raises the following exceptions: |
| -- |
| -- * Duplicate_Vertex, when the vertex is already present in the graph |
| -- |
| -- * Iterated, when the graph has an outstanding vertex iterator |
| |
| function Component |
| (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: |
| -- |
| -- * Missing_Vertex, when the vertex is not present in the graph |
| |
| function Contains_Component |
| (G : Directed_Graph; |
| Comp : Component_Id) return Boolean; |
| -- Determine whether graph G contains component Comp |
| |
| function Contains_Edge |
| (G : Directed_Graph; |
| E : Edge_Id) return Boolean; |
| -- Determine whether graph G contains edge E |
| |
| function Contains_Vertex |
| (G : Directed_Graph; |
| V : Vertex_Id) return Boolean; |
| -- Determine whether graph G contains vertex V |
| |
| function Create |
| (Initial_Vertices : Positive; |
| 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 : Directed_Graph; |
| E : Edge_Id); |
| -- Delete edge E from graph G. This action raises these exceptions: |
| -- |
| -- * Iterated, when the graph has an outstanding edge iterator |
| -- |
| -- * Missing_Edge, when the edge is not present in the graph |
| -- |
| -- * Missing_Vertex, when the source vertex that "owns" the edge is |
| -- not present in the graph. |
| |
| function Destination_Vertex |
| (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 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 : 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 : Directed_Graph) return Boolean; |
| -- Determine whether graph G is empty |
| |
| function Number_Of_Component_Vertices |
| (G : Directed_Graph; |
| Comp : Component_Id) return Natural; |
| -- Obtain the total number of vertices of component Comp of graph G |
| |
| function Number_Of_Components (G : Directed_Graph) return Natural; |
| -- Obtain the total number of components of graph G |
| |
| function Number_Of_Edges (G : Directed_Graph) return Natural; |
| -- Obtain the total number of edges of graph G |
| |
| function Number_Of_Outgoing_Edges |
| (G : Directed_Graph; |
| V : Vertex_Id) return Natural; |
| -- Obtain the total number of outgoing edges of vertex V of graph G |
| |
| function Number_Of_Vertices (G : Directed_Graph) return Natural; |
| -- Obtain the total number of vertices of graph G |
| |
| function Present (G : Directed_Graph) return Boolean; |
| -- Determine whether graph G exists |
| |
| function Source_Vertex |
| (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: |
| -- |
| -- * Missing_Edge, when the edge is not present in the graph |
| |
| ------------------------- |
| -- Iterator operations -- |
| ------------------------- |
| |
| -- The following types represent iterators over various attributes of a |
| -- graph. Each iterator locks all mutation operations of its associated |
| -- attribute, and unlocks them once it is exhausted. The iterators must |
| -- be used with the following pattern: |
| -- |
| -- Iter : Iterate_XXX (Graph); |
| -- while Has_Next (Iter) loop |
| -- Next (Iter, Element); |
| -- end loop; |
| -- |
| -- It is possible to advance the iterators by using Next only, however |
| -- this risks raising Iterator_Exhausted. |
| |
| -- The following type represents an iterator over all edges of a graph |
| |
| type All_Edge_Iterator is private; |
| |
| function Has_Next (Iter : All_Edge_Iterator) return Boolean; |
| -- Determine whether iterator Iter has more edges to examine |
| |
| function Iterate_All_Edges (G : Directed_Graph) return All_Edge_Iterator; |
| -- Obtain an iterator over all edges of graph G |
| |
| procedure Next |
| (Iter : in out All_Edge_Iterator; |
| E : out Edge_Id); |
| -- Return the current edge referenced by iterator Iter and advance to |
| -- the next available edge. This action raises the following exceptions: |
| -- |
| -- * Iterator_Exhausted, when the iterator has been exhausted and |
| -- further attempts are made to advance it. |
| |
| -- The following type represents an iterator over all vertices of a |
| -- graph. |
| |
| type All_Vertex_Iterator is private; |
| |
| function Has_Next (Iter : All_Vertex_Iterator) return Boolean; |
| -- Determine whether iterator Iter has more vertices to examine |
| |
| function Iterate_All_Vertices |
| (G : Directed_Graph) return All_Vertex_Iterator; |
| -- Obtain an iterator over all vertices of graph G |
| |
| procedure Next |
| (Iter : in out All_Vertex_Iterator; |
| V : out Vertex_Id); |
| -- Return the current vertex referenced by iterator Iter and advance |
| -- to the next available vertex. This action raises the following |
| -- exceptions: |
| -- |
| -- * Iterator_Exhausted, when the iterator has been exhausted and |
| -- further attempts are made to advance it. |
| |
| -- The following type represents an iterator over all components of a |
| -- graph. |
| |
| type Component_Iterator is private; |
| |
| function Has_Next (Iter : Component_Iterator) return Boolean; |
| -- Determine whether iterator Iter has more components to examine |
| |
| function Iterate_Components |
| (G : Directed_Graph) return Component_Iterator; |
| -- Obtain an iterator over all components of graph G |
| |
| procedure Next |
| (Iter : in out Component_Iterator; |
| Comp : out Component_Id); |
| -- Return the current component referenced by iterator Iter and advance |
| -- to the next component. This action raises the following exceptions: |
| -- |
| -- * Iterator_Exhausted, when the iterator has been exhausted and |
| -- further attempts are made to advance it. |
| |
| -- The following type prepresents an iterator over all vertices of a |
| -- component. |
| |
| type Component_Vertex_Iterator is private; |
| |
| function Has_Next (Iter : Component_Vertex_Iterator) return Boolean; |
| -- Determine whether iterator Iter has more vertices to examine |
| |
| function Iterate_Component_Vertices |
| (G : Directed_Graph; |
| Comp : Component_Id) return Component_Vertex_Iterator; |
| -- Obtain an iterator over all vertices that comprise component Comp of |
| -- graph G. |
| |
| procedure Next |
| (Iter : in out Component_Vertex_Iterator; |
| V : out Vertex_Id); |
| -- Return the current vertex referenced by iterator Iter and advance to |
| -- the next vertex. This action raises the following exceptions: |
| -- |
| -- * Iterator_Exhausted, when the iterator has been exhausted and |
| -- further attempts are made to advance it. |
| |
| -- The following type represents an iterator over all outgoing edges of |
| -- a vertex. |
| |
| type Outgoing_Edge_Iterator is private; |
| |
| function Has_Next (Iter : Outgoing_Edge_Iterator) return Boolean; |
| -- Determine whether iterator Iter has more outgoing edges to examine |
| |
| function Iterate_Outgoing_Edges |
| (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. |
| |
| procedure Next |
| (Iter : in out Outgoing_Edge_Iterator; |
| E : out Edge_Id); |
| -- Return the current outgoing edge referenced by iterator Iter and |
| -- advance to the next available outgoing edge. This action raises the |
| -- following exceptions: |
| -- |
| -- * Iterator_Exhausted, when the iterator has been exhausted and |
| -- further attempts are made to advance it. |
| |
| private |
| pragma Unreferenced (No_Edge); |
| |
| -------------- |
| -- Edge_Map -- |
| -------------- |
| |
| type Edge_Attributes is record |
| Destination : Vertex_Id := No_Vertex; |
| -- The target of a directed edge |
| |
| Source : Vertex_Id := No_Vertex; |
| -- The origin of a directed edge. The source vertex "owns" the edge. |
| end record; |
| |
| No_Edge_Attributes : constant Edge_Attributes := |
| (Destination => No_Vertex, |
| Source => No_Vertex); |
| |
| procedure Destroy_Edge_Attributes (Attrs : in out Edge_Attributes); |
| -- Destroy the contents of attributes Attrs |
| |
| package Edge_Map is new Dynamic_Hash_Tables |
| (Key_Type => Edge_Id, |
| Value_Type => Edge_Attributes, |
| No_Value => No_Edge_Attributes, |
| Expansion_Threshold => 1.5, |
| Expansion_Factor => 2, |
| Compression_Threshold => 0.3, |
| Compression_Factor => 2, |
| "=" => Same_Edge, |
| Destroy_Value => Destroy_Edge_Attributes, |
| Hash => Hash_Edge); |
| |
| -------------- |
| -- Edge_Set -- |
| -------------- |
| |
| package Edge_Set is new Membership_Sets |
| (Element_Type => Edge_Id, |
| "=" => "=", |
| Hash => Hash_Edge); |
| |
| ----------------- |
| -- Vertex_List -- |
| ----------------- |
| |
| procedure Destroy_Vertex (V : in out Vertex_Id); |
| -- Destroy the contents of a vertex |
| |
| package Vertex_List is new Doubly_Linked_Lists |
| (Element_Type => Vertex_Id, |
| "=" => Same_Vertex, |
| Destroy_Element => Destroy_Vertex); |
| |
| ---------------- |
| -- Vertex_Map -- |
| ---------------- |
| |
| type Vertex_Attributes is record |
| Component : Component_Id := No_Component; |
| -- The component where a vertex lives |
| |
| Outgoing_Edges : Edge_Set.Membership_Set := Edge_Set.Nil; |
| -- The set of edges that extend out from a vertex |
| end record; |
| |
| No_Vertex_Attributes : constant Vertex_Attributes := |
| (Component => No_Component, |
| Outgoing_Edges => Edge_Set.Nil); |
| |
| procedure Destroy_Vertex_Attributes (Attrs : in out Vertex_Attributes); |
| -- Destroy the contents of attributes Attrs |
| |
| package Vertex_Map is new Dynamic_Hash_Tables |
| (Key_Type => Vertex_Id, |
| Value_Type => Vertex_Attributes, |
| No_Value => No_Vertex_Attributes, |
| Expansion_Threshold => 1.5, |
| Expansion_Factor => 2, |
| Compression_Threshold => 0.3, |
| Compression_Factor => 2, |
| "=" => Same_Vertex, |
| Destroy_Value => Destroy_Vertex_Attributes, |
| Hash => Hash_Vertex); |
| |
| ------------------- |
| -- Component_Map -- |
| ------------------- |
| |
| type Component_Attributes is record |
| Vertices : Vertex_List.Doubly_Linked_List := Vertex_List.Nil; |
| end record; |
| |
| No_Component_Attributes : constant Component_Attributes := |
| (Vertices => Vertex_List.Nil); |
| |
| procedure Destroy_Component_Attributes |
| (Attrs : in out Component_Attributes); |
| -- Destroy the contents of attributes Attrs |
| |
| package Component_Map is new Dynamic_Hash_Tables |
| (Key_Type => Component_Id, |
| Value_Type => Component_Attributes, |
| No_Value => No_Component_Attributes, |
| Expansion_Threshold => 1.5, |
| Expansion_Factor => 2, |
| Compression_Threshold => 0.3, |
| Compression_Factor => 2, |
| "=" => "=", |
| Destroy_Value => Destroy_Component_Attributes, |
| Hash => Hash_Component); |
| |
| ----------- |
| -- Graph -- |
| ----------- |
| |
| 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.Dynamic_Hash_Table := Vertex_Map.Nil; |
| -- The map of vertex -> vertex attributes for all vertices in the |
| -- graph. |
| |
| Components : Component_Map.Dynamic_Hash_Table := Component_Map.Nil; |
| -- The map of component -> component attributes for all components |
| -- in the graph. |
| end record; |
| |
| type Directed_Graph is access Directed_Graph_Attributes; |
| Nil : constant Directed_Graph := null; |
| |
| --------------- |
| -- Iterators -- |
| --------------- |
| |
| type All_Edge_Iterator is new Edge_Map.Iterator; |
| type All_Vertex_Iterator is new Vertex_Map.Iterator; |
| type Component_Iterator is new Component_Map.Iterator; |
| type Component_Vertex_Iterator is new Vertex_List.Iterator; |
| type Outgoing_Edge_Iterator is new Edge_Set.Iterator; |
| end Directed_Graphs; |
| |
| private |
| First_Component : constant Component_Id := No_Component + 1; |
| |
| end GNAT.Graphs; |
