gcc/ada/libgnat/g-graphs.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT RUN-TIME COMPONENTS                         --
   4 --                                                                          --
   5 --                           G N A T . G R A P H S                          --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --             Copyright (C) 2018-2019, Free Software Foundation, Inc.      --
  10 --                                                                          --
  11 -- GNAT is free software;  you can  redistribute it  and/or modify it under --
  12 -- terms of the  GNU General Public License as published  by the Free Soft- --
  13 -- ware  Foundation;  either version 3,  or (at your option) any later ver- --
  14 -- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
  15 -- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
  16 -- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
  17 --                                                                          --
  18 -- As a special exception under Section 7 of GPL version 3, you are granted --
  19 -- additional permissions described in the GCC Runtime Library Exception,   --
  20 -- version 3.1, as published by the Free Software Foundation.               --
  21 --                                                                          --
  22 -- You should have received a copy of the GNU General Public License and    --
  23 -- a copy of the GCC Runtime Library Exception along with this program;     --
  24 -- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
  25 -- <http://www.gnu.org/licenses/>.                                          --
  26 --                                                                          --
  27 -- GNAT was originally developed  by the GNAT team at  New York University. --
  28 -- Extensive contributions were provided by Ada Core Technologies Inc.      --
  29 --                                                                          --
  30 ------------------------------------------------------------------------------
  31
  32 pragma Compiler_Unit_Warning;
  33
  34 with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables;
  35 with GNAT.Lists;           use GNAT.Lists;
  36 with GNAT.Sets;            use GNAT.Sets;
  37
  38 package GNAT.Graphs is
  39
  40    ---------------
  41    -- Componant --
  42    ---------------
  43
  44    --  The following type denotes a strongly connected component handle
  45    --  (referred to as simply "component") in a graph.
  46
  47    type Component_Id is new Natural;
  48    No_Component : constant Component_Id;
  49
  50    function Hash_Component (Comp : Component_Id) return Bucket_Range_Type;
  51    --  Map component Comp into the range of buckets
  52
  53    function Present (Comp : Component_Id) return Boolean;
  54    --  Determine whether component Comp exists
  55
  56    --------------------
  57    -- Directed_Graph --
  58    --------------------
  59
  60    --  The following package offers a directed graph abstraction with the
  61    --  following characteristics:
  62    --
  63    --    * Dynamic resizing based on number of vertices and edges
  64    --    * Creation of multiple instances, of different sizes
  65    --    * Discovery of strongly connected components
  66    --    * Iterable attributes
  67    --
  68    --  The following use pattern must be employed when operating this graph:
  69    --
  70    --    Graph : Instance := Create (<some size>, <some size>);
  71    --
  72    --    <various operations>
  73    --
  74    --    Destroy (Graph);
  75    --
  76    --  The destruction of the graph reclaims all storage occupied by it.
  77
  78    generic
  79
  80       --------------
  81       -- Vertices --
  82       --------------
  83
  84       type Vertex_Id is private;
  85       --  The handle of a vertex
  86
  87       No_Vertex : Vertex_Id;
  88       --  An indicator for a nonexistent vertex
  89
  90       with function Hash_Vertex (V : Vertex_Id) return Bucket_Range_Type;
  91       --  Map vertex V into the range of buckets
  92
  93       with function Same_Vertex
  94              (Left  : Vertex_Id;
  95               Right : Vertex_Id) return Boolean;
  96       --  Compare vertex Left to vertex Right for identity
  97
  98       -----------
  99       -- Edges --
 100       -----------
 101
 102       type Edge_Id is private;
 103       --  The handle of an edge
 104
 105       No_Edge : Edge_Id;
 106       --  An indicator for a nonexistent edge
 107
 108       with function Hash_Edge (E : Edge_Id) return Bucket_Range_Type;
 109       --  Map edge E into the range of buckets
 110
 111       with function Same_Edge
 112              (Left  : Edge_Id;
 113               Right : Edge_Id) return Boolean;
 114       --  Compare edge Left to edge Right for identity
 115
 116    package Directed_Graph is
 117
 118       --  The following exceptions are raised when an attempt is made to add
 119       --  the same edge or vertex in a graph.
 120
 121       Duplicate_Edge   : exception;
 122       Duplicate_Vertex : exception;
 123
 124       --  The following exceptions are raised when an attempt is made to delete
 125       --  or reference a nonexistent component, edge, or vertex in a graph.
 126
 127       Missing_Component : exception;
 128       Missing_Edge      : exception;
 129       Missing_Vertex    : exception;
 130
 131       ----------------------
 132       -- Graph operations --
 133       ----------------------
 134
 135       --  The following type denotes a graph handle. Each instance must be
 136       --  created using routine Create.
 137
 138       type Instance is private;
 139       Nil : constant Instance;
 140
 141       procedure Add_Edge
 142         (G           : Instance;
 143          E           : Edge_Id;
 144          Source      : Vertex_Id;
 145          Destination : Vertex_Id);
 146       --  Add edge E to graph G which links vertex source Source and desination
 147       --  vertex Destination. The edge is "owned" by vertex Source. This action
 148       --  raises the following exceptions:
 149       --
 150       --    * Duplicate_Edge, when the edge is already present in the graph
 151       --
 152       --    * Iterated, when the graph has an outstanding edge iterator
 153       --
 154       --    * Missing_Vertex, when either the source or desination are not
 155       --      present in the graph.
 156
 157       procedure Add_Vertex
 158         (G : Instance;
 159          V : Vertex_Id);
 160       --  Add vertex V to graph G. This action raises the following exceptions:
 161       --
 162       --    * Duplicate_Vertex, when the vertex is already present in the graph
 163       --
 164       --    * Iterated, when the graph has an outstanding vertex iterator
 165
 166       function Component
 167         (G : Instance;
 168          V : Vertex_Id) return Component_Id;
 169       --  Obtain the component where vertex V of graph G resides. This action
 170       --  raises the following exceptions:
 171       --
 172       --    * Missing_Vertex, when the vertex is not present in the graph
 173
 174       function Contains_Component
 175         (G    : Instance;
 176          Comp : Component_Id) return Boolean;
 177       --  Determine whether graph G contains component Comp
 178
 179       function Contains_Edge
 180         (G : Instance;
 181          E : Edge_Id) return Boolean;
 182       --  Determine whether graph G contains edge E
 183
 184       function Contains_Vertex
 185         (G : Instance;
 186          V : Vertex_Id) return Boolean;
 187       --  Determine whether graph G contains vertex V
 188
 189       function Create
 190         (Initial_Vertices : Positive;
 191          Initial_Edges    : Positive) return Instance;
 192       --  Create a new graph with vertex capacity Initial_Vertices and edge
 193       --  capacity Initial_Edges. This routine must be called at the start of
 194       --  a graph's lifetime.
 195
 196       procedure Delete_Edge
 197         (G : Instance;
 198          E : Edge_Id);
 199       --  Delete edge E from graph G. This action raises these exceptions:
 200       --
 201       --    * Iterated, when the graph has an outstanding edge iterator
 202       --
 203       --    * Missing_Edge, when the edge is not present in the graph
 204       --
 205       --    * Missing_Vertex, when the source vertex that "owns" the edge is
 206       --      not present in the graph.
 207
 208       function Destination_Vertex
 209         (G : Instance;
 210          E : Edge_Id) return Vertex_Id;
 211       --  Obtain the destination vertex of edge E of graph G. This action
 212       --  raises the following exceptions:
 213       --
 214       --    * Missing_Edge, when the edge is not present in the graph
 215
 216       procedure Destroy (G : in out Instance);
 217       --  Destroy the contents of graph G, rendering it unusable. This routine
 218       --  must be called at the end of a graph's lifetime. This action raises
 219       --  the following exceptions:
 220       --
 221       --    * Iterated, if the graph has any outstanding iterator
 222
 223       procedure Find_Components (G : Instance);
 224       --  Find all components of graph G. This action raises the following
 225       --  exceptions:
 226       --
 227       --    * Iterated, when the components or vertices of the graph have an
 228       --      outstanding iterator.
 229
 230       function Is_Empty (G : Instance) return Boolean;
 231       --  Determine whether graph G is empty
 232
 233       function Number_Of_Components (G : Instance) return Natural;
 234       --  Obtain the total number of components of graph G
 235
 236       function Number_Of_Edges (G : Instance) return Natural;
 237       --  Obtain the total number of edges of graph G
 238
 239       function Number_Of_Vertices (G : Instance) return Natural;
 240       --  Obtain the total number of vertices of graph G
 241
 242       function Present (G : Instance) return Boolean;
 243       --  Determine whether graph G exists
 244
 245       function Source_Vertex
 246         (G : Instance;
 247          E : Edge_Id) return Vertex_Id;
 248       --  Obtain the source vertex that "owns" edge E of graph G. This action
 249       --  raises the following exceptions:
 250       --
 251       --    * Missing_Edge, when the edge is not present in the graph
 252
 253       -------------------------
 254       -- Iterator operations --
 255       -------------------------
 256
 257       --  The following types represent iterators over various attributes of a
 258       --  graph. Each iterator locks all mutation operations of its associated
 259       --  attribute, and unlocks them once it is exhausted. The iterators must
 260       --  be used with the following pattern:
 261       --
 262       --    Iter : Iterate_XXX (Graph);
 263       --    while Has_Next (Iter) loop
 264       --       Next (Iter, Element);
 265       --    end loop;
 266       --
 267       --  It is possible to advance the iterators by using Next only, however
 268       --  this risks raising Iterator_Exhausted.
 269
 270       --  The following type represents an iterator over all edges of a graph
 271
 272       type All_Edge_Iterator is private;
 273
 274       function Has_Next (Iter : All_Edge_Iterator) return Boolean;
 275       --  Determine whether iterator Iter has more edges to examine
 276
 277       function Iterate_All_Edges (G : Instance) return All_Edge_Iterator;
 278       --  Obtain an iterator over all edges of graph G
 279
 280       procedure Next
 281         (Iter : in out All_Edge_Iterator;
 282          E    : out Edge_Id);
 283       --  Return the current edge referenced by iterator Iter and advance to
 284       --  the next available edge. This action raises the following exceptions:
 285       --
 286       --    * Iterator_Exhausted, when the iterator has been exhausted and
 287       --      further attempts are made to advance it.
 288
 289       --  The following type represents an iterator over all vertices of a
 290       --  graph.
 291
 292       type All_Vertex_Iterator is private;
 293
 294       function Has_Next (Iter : All_Vertex_Iterator) return Boolean;
 295       --  Determine whether iterator Iter has more vertices to examine
 296
 297       function Iterate_All_Vertices (G : Instance) return All_Vertex_Iterator;
 298       --  Obtain an iterator over all vertices of graph G
 299
 300       procedure Next
 301         (Iter : in out All_Vertex_Iterator;
 302          V    : out Vertex_Id);
 303       --  Return the current vertex referenced by iterator Iter and advance
 304       --  to the next available vertex. This action raises the following
 305       --  exceptions:
 306       --
 307       --    * Iterator_Exhausted, when the iterator has been exhausted and
 308       --      further attempts are made to advance it.
 309
 310       --  The following type represents an iterator over all components of a
 311       --  graph.
 312
 313       type Component_Iterator is private;
 314
 315       function Has_Next (Iter : Component_Iterator) return Boolean;
 316       --  Determine whether iterator Iter has more components to examine
 317
 318       function Iterate_Components (G : Instance) return Component_Iterator;
 319       --  Obtain an iterator over all components of graph G
 320
 321       procedure Next
 322         (Iter : in out Component_Iterator;
 323          Comp : out Component_Id);
 324       --  Return the current component referenced by iterator Iter and advance
 325       --  to the next component. This action raises the following exceptions:
 326       --
 327       --    * Iterator_Exhausted, when the iterator has been exhausted and
 328       --      further attempts are made to advance it.
 329
 330       --  The following type represents an iterator over all outgoing edges of
 331       --  a vertex.
 332
 333       type Outgoing_Edge_Iterator is private;
 334
 335       function Has_Next (Iter : Outgoing_Edge_Iterator) return Boolean;
 336       --  Determine whether iterator Iter has more outgoing edges to examine
 337
 338       function Iterate_Outgoing_Edges
 339         (G : Instance;
 340          V : Vertex_Id) return Outgoing_Edge_Iterator;
 341       --  Obtain an iterator over all the outgoing edges "owned" by vertex V of
 342       --  graph G.
 343
 344       procedure Next
 345         (Iter : in out Outgoing_Edge_Iterator;
 346          E    : out Edge_Id);
 347       --  Return the current outgoing edge referenced by iterator Iter and
 348       --  advance to the next available outgoing edge. This action raises the
 349       --  following exceptions:
 350       --
 351       --    * Iterator_Exhausted, when the iterator has been exhausted and
 352       --      further attempts are made to advance it.
 353
 354       --  The following type prepresents an iterator over all vertices of a
 355       --  component.
 356
 357       type Vertex_Iterator is private;
 358
 359       function Has_Next (Iter : Vertex_Iterator) return Boolean;
 360       --  Determine whether iterator Iter has more vertices to examine
 361
 362       function Iterate_Vertices
 363         (G    : Instance;
 364          Comp : Component_Id) return Vertex_Iterator;
 365       --  Obtain an iterator over all vertices that comprise component Comp of
 366       --  graph G.
 367
 368       procedure Next
 369         (Iter : in out Vertex_Iterator;
 370          V    : out Vertex_Id);
 371       --  Return the current vertex referenced by iterator Iter and advance to
 372       --  the next vertex. This action raises the following exceptions:
 373       --
 374       --    * Iterator_Exhausted, when the iterator has been exhausted and
 375       --      further attempts are made to advance it.
 376
 377    private
 378       pragma Unreferenced (No_Edge);
 379
 380       --------------
 381       -- Edge_Map --
 382       --------------
 383
 384       type Edge_Attributes is record
 385          Destination : Vertex_Id := No_Vertex;
 386          --  The target of a directed edge
 387
 388          Source : Vertex_Id := No_Vertex;
 389          --  The origin of a directed edge. The source vertex "owns" the edge.
 390       end record;
 391
 392       No_Edge_Attributes : constant Edge_Attributes :=
 393         (Destination => No_Vertex,
 394          Source      => No_Vertex);
 395
 396       procedure Destroy_Edge_Attributes (Attrs : in out Edge_Attributes);
 397       --  Destroy the contents of attributes Attrs
 398
 399       package Edge_Map is new Dynamic_HTable
 400         (Key_Type              => Edge_Id,
 401          Value_Type            => Edge_Attributes,
 402          No_Value              => No_Edge_Attributes,
 403          Expansion_Threshold   => 1.5,
 404          Expansion_Factor      => 2,
 405          Compression_Threshold => 0.3,
 406          Compression_Factor    => 2,
 407          "="                   => Same_Edge,
 408          Destroy_Value         => Destroy_Edge_Attributes,
 409          Hash                  => Hash_Edge);
 410
 411       --------------
 412       -- Edge_Set --
 413       --------------
 414
 415       package Edge_Set is new Membership_Set
 416         (Element_Type => Edge_Id,
 417          "="          => "=",
 418          Hash         => Hash_Edge);
 419
 420       -----------------
 421       -- Vertex_List --
 422       -----------------
 423
 424       procedure Destroy_Vertex (V : in out Vertex_Id);
 425       --  Destroy the contents of a vertex
 426
 427       package Vertex_List is new Doubly_Linked_List
 428         (Element_Type    => Vertex_Id,
 429          "="             => Same_Vertex,
 430          Destroy_Element => Destroy_Vertex);
 431
 432       ----------------
 433       -- Vertex_Map --
 434       ----------------
 435
 436       type Vertex_Attributes is record
 437          Component : Component_Id := No_Component;
 438          --  The component where a vertex lives
 439
 440          Outgoing_Edges : Edge_Set.Instance := Edge_Set.Nil;
 441          --  The set of edges that extend out from a vertex
 442       end record;
 443
 444       No_Vertex_Attributes : constant Vertex_Attributes :=
 445         (Component      => No_Component,
 446          Outgoing_Edges => Edge_Set.Nil);
 447
 448       procedure Destroy_Vertex_Attributes (Attrs : in out Vertex_Attributes);
 449       --  Destroy the contents of attributes Attrs
 450
 451       package Vertex_Map is new Dynamic_HTable
 452         (Key_Type              => Vertex_Id,
 453          Value_Type            => Vertex_Attributes,
 454          No_Value              => No_Vertex_Attributes,
 455          Expansion_Threshold   => 1.5,
 456          Expansion_Factor      => 2,
 457          Compression_Threshold => 0.3,
 458          Compression_Factor    => 2,
 459          "="                   => Same_Vertex,
 460          Destroy_Value         => Destroy_Vertex_Attributes,
 461          Hash                  => Hash_Vertex);
 462
 463       -------------------
 464       -- Component_Map --
 465       -------------------
 466
 467       type Component_Attributes is record
 468          Vertices : Vertex_List.Instance := Vertex_List.Nil;
 469       end record;
 470
 471       No_Component_Attributes : constant Component_Attributes :=
 472         (Vertices => Vertex_List.Nil);
 473
 474       procedure Destroy_Component_Attributes
 475         (Attrs : in out Component_Attributes);
 476       --  Destroy the contents of attributes Attrs
 477
 478       package Component_Map is new Dynamic_HTable
 479         (Key_Type              => Component_Id,
 480          Value_Type            => Component_Attributes,
 481          No_Value              => No_Component_Attributes,
 482          Expansion_Threshold   => 1.5,
 483          Expansion_Factor      => 2,
 484          Compression_Threshold => 0.3,
 485          Compression_Factor    => 2,
 486          "="                   => "=",
 487          Destroy_Value         => Destroy_Component_Attributes,
 488          Hash                  => Hash_Component);
 489
 490       -----------
 491       -- Graph --
 492       -----------
 493
 494       type Graph is record
 495          All_Edges : Edge_Map.Instance := Edge_Map.Nil;
 496          --  The map of edge -> edge attributes for all edges in the graph
 497
 498          All_Vertices : Vertex_Map.Instance := Vertex_Map.Nil;
 499          --  The map of vertex -> vertex attributes for all vertices in the
 500          --  graph.
 501
 502          Components : Component_Map.Instance := Component_Map.Nil;
 503          --  The map of component -> component attributes for all components
 504          --  in the graph.
 505       end record;
 506
 507       --------------
 508       -- Instance --
 509       --------------
 510
 511       type Instance is access Graph;
 512       Nil : constant Instance := null;
 513
 514       ---------------
 515       -- Iterators --
 516       ---------------
 517
 518       type All_Edge_Iterator      is new Edge_Map.Iterator;
 519       type All_Vertex_Iterator    is new Vertex_Map.Iterator;
 520       type Component_Iterator     is new Component_Map.Iterator;
 521       type Outgoing_Edge_Iterator is new Edge_Set.Iterator;
 522       type Vertex_Iterator        is new Vertex_List.Iterator;
 523    end Directed_Graph;
 524
 525 private
 526    No_Component    : constant Component_Id := Component_Id'First;
 527    First_Component : constant Component_Id := No_Component + 1;
 528
 529 end GNAT.Graphs;