------------------------------------------------------------------------------ | |

-- -- | |

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