Mercurial > hg > CbC > CbC_gcc
comparison gcc/ada/libgnat/g-graphs.ads @ 145:1830386684a0
gcc-9.2.0
| author | anatofuz |
|---|---|
| date | Thu, 13 Feb 2020 11:34:05 +0900 |
| parents | |
| children |
comparison
equal
deleted
inserted
replaced
| 131:84e7813d76e9 | 145:1830386684a0 |
|---|---|
| 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 -- Component -- | |
| 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 := Component_Id'First; | |
| 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_Graphs -- | |
| 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 : Directed_Graph := 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_Graphs 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 Directed_Graph is private; | |
| 139 Nil : constant Directed_Graph; | |
| 140 | |
| 141 procedure Add_Edge | |
| 142 (G : Directed_Graph; | |
| 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 : Directed_Graph; | |
| 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 : Directed_Graph; | |
| 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 : Directed_Graph; | |
| 176 Comp : Component_Id) return Boolean; | |
| 177 -- Determine whether graph G contains component Comp | |
| 178 | |
| 179 function Contains_Edge | |
| 180 (G : Directed_Graph; | |
| 181 E : Edge_Id) return Boolean; | |
| 182 -- Determine whether graph G contains edge E | |
| 183 | |
| 184 function Contains_Vertex | |
| 185 (G : Directed_Graph; | |
| 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 Directed_Graph; | |
| 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 : Directed_Graph; | |
| 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 : Directed_Graph; | |
| 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 Directed_Graph); | |
| 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 : Directed_Graph); | |
| 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 : Directed_Graph) return Boolean; | |
| 231 -- Determine whether graph G is empty | |
| 232 | |
| 233 function Number_Of_Component_Vertices | |
| 234 (G : Directed_Graph; | |
| 235 Comp : Component_Id) return Natural; | |
| 236 -- Obtain the total number of vertices of component Comp of graph G | |
| 237 | |
| 238 function Number_Of_Components (G : Directed_Graph) return Natural; | |
| 239 -- Obtain the total number of components of graph G | |
| 240 | |
| 241 function Number_Of_Edges (G : Directed_Graph) return Natural; | |
| 242 -- Obtain the total number of edges of graph G | |
| 243 | |
| 244 function Number_Of_Outgoing_Edges | |
| 245 (G : Directed_Graph; | |
| 246 V : Vertex_Id) return Natural; | |
| 247 -- Obtain the total number of outgoing edges of vertex V of graph G | |
| 248 | |
| 249 function Number_Of_Vertices (G : Directed_Graph) return Natural; | |
| 250 -- Obtain the total number of vertices of graph G | |
| 251 | |
| 252 function Present (G : Directed_Graph) return Boolean; | |
| 253 -- Determine whether graph G exists | |
| 254 | |
| 255 function Source_Vertex | |
| 256 (G : Directed_Graph; | |
| 257 E : Edge_Id) return Vertex_Id; | |
| 258 -- Obtain the source vertex that "owns" edge E of graph G. This action | |
| 259 -- raises the following exceptions: | |
| 260 -- | |
| 261 -- * Missing_Edge, when the edge is not present in the graph | |
| 262 | |
| 263 ------------------------- | |
| 264 -- Iterator operations -- | |
| 265 ------------------------- | |
| 266 | |
| 267 -- The following types represent iterators over various attributes of a | |
| 268 -- graph. Each iterator locks all mutation operations of its associated | |
| 269 -- attribute, and unlocks them once it is exhausted. The iterators must | |
| 270 -- be used with the following pattern: | |
| 271 -- | |
| 272 -- Iter : Iterate_XXX (Graph); | |
| 273 -- while Has_Next (Iter) loop | |
| 274 -- Next (Iter, Element); | |
| 275 -- end loop; | |
| 276 -- | |
| 277 -- It is possible to advance the iterators by using Next only, however | |
| 278 -- this risks raising Iterator_Exhausted. | |
| 279 | |
| 280 -- The following type represents an iterator over all edges of a graph | |
| 281 | |
| 282 type All_Edge_Iterator is private; | |
| 283 | |
| 284 function Has_Next (Iter : All_Edge_Iterator) return Boolean; | |
| 285 -- Determine whether iterator Iter has more edges to examine | |
| 286 | |
| 287 function Iterate_All_Edges (G : Directed_Graph) return All_Edge_Iterator; | |
| 288 -- Obtain an iterator over all edges of graph G | |
| 289 | |
| 290 procedure Next | |
| 291 (Iter : in out All_Edge_Iterator; | |
| 292 E : out Edge_Id); | |
| 293 -- Return the current edge referenced by iterator Iter and advance to | |
| 294 -- the next available edge. This action raises the following exceptions: | |
| 295 -- | |
| 296 -- * Iterator_Exhausted, when the iterator has been exhausted and | |
| 297 -- further attempts are made to advance it. | |
| 298 | |
| 299 -- The following type represents an iterator over all vertices of a | |
| 300 -- graph. | |
| 301 | |
| 302 type All_Vertex_Iterator is private; | |
| 303 | |
| 304 function Has_Next (Iter : All_Vertex_Iterator) return Boolean; | |
| 305 -- Determine whether iterator Iter has more vertices to examine | |
| 306 | |
| 307 function Iterate_All_Vertices | |
| 308 (G : Directed_Graph) return All_Vertex_Iterator; | |
| 309 -- Obtain an iterator over all vertices of graph G | |
| 310 | |
| 311 procedure Next | |
| 312 (Iter : in out All_Vertex_Iterator; | |
| 313 V : out Vertex_Id); | |
| 314 -- Return the current vertex referenced by iterator Iter and advance | |
| 315 -- to the next available vertex. This action raises the following | |
| 316 -- exceptions: | |
| 317 -- | |
| 318 -- * Iterator_Exhausted, when the iterator has been exhausted and | |
| 319 -- further attempts are made to advance it. | |
| 320 | |
| 321 -- The following type represents an iterator over all components of a | |
| 322 -- graph. | |
| 323 | |
| 324 type Component_Iterator is private; | |
| 325 | |
| 326 function Has_Next (Iter : Component_Iterator) return Boolean; | |
| 327 -- Determine whether iterator Iter has more components to examine | |
| 328 | |
| 329 function Iterate_Components | |
| 330 (G : Directed_Graph) return Component_Iterator; | |
| 331 -- Obtain an iterator over all components of graph G | |
| 332 | |
| 333 procedure Next | |
| 334 (Iter : in out Component_Iterator; | |
| 335 Comp : out Component_Id); | |
| 336 -- Return the current component referenced by iterator Iter and advance | |
| 337 -- to the next component. This action raises the following exceptions: | |
| 338 -- | |
| 339 -- * Iterator_Exhausted, when the iterator has been exhausted and | |
| 340 -- further attempts are made to advance it. | |
| 341 | |
| 342 -- The following type prepresents an iterator over all vertices of a | |
| 343 -- component. | |
| 344 | |
| 345 type Component_Vertex_Iterator is private; | |
| 346 | |
| 347 function Has_Next (Iter : Component_Vertex_Iterator) return Boolean; | |
| 348 -- Determine whether iterator Iter has more vertices to examine | |
| 349 | |
| 350 function Iterate_Component_Vertices | |
| 351 (G : Directed_Graph; | |
| 352 Comp : Component_Id) return Component_Vertex_Iterator; | |
| 353 -- Obtain an iterator over all vertices that comprise component Comp of | |
| 354 -- graph G. | |
| 355 | |
| 356 procedure Next | |
| 357 (Iter : in out Component_Vertex_Iterator; | |
| 358 V : out Vertex_Id); | |
| 359 -- Return the current vertex referenced by iterator Iter and advance to | |
| 360 -- the next vertex. This action raises the following exceptions: | |
| 361 -- | |
| 362 -- * Iterator_Exhausted, when the iterator has been exhausted and | |
| 363 -- further attempts are made to advance it. | |
| 364 | |
| 365 -- The following type represents an iterator over all outgoing edges of | |
| 366 -- a vertex. | |
| 367 | |
| 368 type Outgoing_Edge_Iterator is private; | |
| 369 | |
| 370 function Has_Next (Iter : Outgoing_Edge_Iterator) return Boolean; | |
| 371 -- Determine whether iterator Iter has more outgoing edges to examine | |
| 372 | |
| 373 function Iterate_Outgoing_Edges | |
| 374 (G : Directed_Graph; | |
| 375 V : Vertex_Id) return Outgoing_Edge_Iterator; | |
| 376 -- Obtain an iterator over all the outgoing edges "owned" by vertex V of | |
| 377 -- graph G. | |
| 378 | |
| 379 procedure Next | |
| 380 (Iter : in out Outgoing_Edge_Iterator; | |
| 381 E : out Edge_Id); | |
| 382 -- Return the current outgoing edge referenced by iterator Iter and | |
| 383 -- advance to the next available outgoing edge. This action raises the | |
| 384 -- following exceptions: | |
| 385 -- | |
| 386 -- * Iterator_Exhausted, when the iterator has been exhausted and | |
| 387 -- further attempts are made to advance it. | |
| 388 | |
| 389 private | |
| 390 pragma Unreferenced (No_Edge); | |
| 391 | |
| 392 -------------- | |
| 393 -- Edge_Map -- | |
| 394 -------------- | |
| 395 | |
| 396 type Edge_Attributes is record | |
| 397 Destination : Vertex_Id := No_Vertex; | |
| 398 -- The target of a directed edge | |
| 399 | |
| 400 Source : Vertex_Id := No_Vertex; | |
| 401 -- The origin of a directed edge. The source vertex "owns" the edge. | |
| 402 end record; | |
| 403 | |
| 404 No_Edge_Attributes : constant Edge_Attributes := | |
| 405 (Destination => No_Vertex, | |
| 406 Source => No_Vertex); | |
| 407 | |
| 408 procedure Destroy_Edge_Attributes (Attrs : in out Edge_Attributes); | |
| 409 -- Destroy the contents of attributes Attrs | |
| 410 | |
| 411 package Edge_Map is new Dynamic_Hash_Tables | |
| 412 (Key_Type => Edge_Id, | |
| 413 Value_Type => Edge_Attributes, | |
| 414 No_Value => No_Edge_Attributes, | |
| 415 Expansion_Threshold => 1.5, | |
| 416 Expansion_Factor => 2, | |
| 417 Compression_Threshold => 0.3, | |
| 418 Compression_Factor => 2, | |
| 419 "=" => Same_Edge, | |
| 420 Destroy_Value => Destroy_Edge_Attributes, | |
| 421 Hash => Hash_Edge); | |
| 422 | |
| 423 -------------- | |
| 424 -- Edge_Set -- | |
| 425 -------------- | |
| 426 | |
| 427 package Edge_Set is new Membership_Sets | |
| 428 (Element_Type => Edge_Id, | |
| 429 "=" => "=", | |
| 430 Hash => Hash_Edge); | |
| 431 | |
| 432 ----------------- | |
| 433 -- Vertex_List -- | |
| 434 ----------------- | |
| 435 | |
| 436 procedure Destroy_Vertex (V : in out Vertex_Id); | |
| 437 -- Destroy the contents of a vertex | |
| 438 | |
| 439 package Vertex_List is new Doubly_Linked_Lists | |
| 440 (Element_Type => Vertex_Id, | |
| 441 "=" => Same_Vertex, | |
| 442 Destroy_Element => Destroy_Vertex); | |
| 443 | |
| 444 ---------------- | |
| 445 -- Vertex_Map -- | |
| 446 ---------------- | |
| 447 | |
| 448 type Vertex_Attributes is record | |
| 449 Component : Component_Id := No_Component; | |
| 450 -- The component where a vertex lives | |
| 451 | |
| 452 Outgoing_Edges : Edge_Set.Membership_Set := Edge_Set.Nil; | |
| 453 -- The set of edges that extend out from a vertex | |
| 454 end record; | |
| 455 | |
| 456 No_Vertex_Attributes : constant Vertex_Attributes := | |
| 457 (Component => No_Component, | |
| 458 Outgoing_Edges => Edge_Set.Nil); | |
| 459 | |
| 460 procedure Destroy_Vertex_Attributes (Attrs : in out Vertex_Attributes); | |
| 461 -- Destroy the contents of attributes Attrs | |
| 462 | |
| 463 package Vertex_Map is new Dynamic_Hash_Tables | |
| 464 (Key_Type => Vertex_Id, | |
| 465 Value_Type => Vertex_Attributes, | |
| 466 No_Value => No_Vertex_Attributes, | |
| 467 Expansion_Threshold => 1.5, | |
| 468 Expansion_Factor => 2, | |
| 469 Compression_Threshold => 0.3, | |
| 470 Compression_Factor => 2, | |
| 471 "=" => Same_Vertex, | |
| 472 Destroy_Value => Destroy_Vertex_Attributes, | |
| 473 Hash => Hash_Vertex); | |
| 474 | |
| 475 ------------------- | |
| 476 -- Component_Map -- | |
| 477 ------------------- | |
| 478 | |
| 479 type Component_Attributes is record | |
| 480 Vertices : Vertex_List.Doubly_Linked_List := Vertex_List.Nil; | |
| 481 end record; | |
| 482 | |
| 483 No_Component_Attributes : constant Component_Attributes := | |
| 484 (Vertices => Vertex_List.Nil); | |
| 485 | |
| 486 procedure Destroy_Component_Attributes | |
| 487 (Attrs : in out Component_Attributes); | |
| 488 -- Destroy the contents of attributes Attrs | |
| 489 | |
| 490 package Component_Map is new Dynamic_Hash_Tables | |
| 491 (Key_Type => Component_Id, | |
| 492 Value_Type => Component_Attributes, | |
| 493 No_Value => No_Component_Attributes, | |
| 494 Expansion_Threshold => 1.5, | |
| 495 Expansion_Factor => 2, | |
| 496 Compression_Threshold => 0.3, | |
| 497 Compression_Factor => 2, | |
| 498 "=" => "=", | |
| 499 Destroy_Value => Destroy_Component_Attributes, | |
| 500 Hash => Hash_Component); | |
| 501 | |
| 502 ----------- | |
| 503 -- Graph -- | |
| 504 ----------- | |
| 505 | |
| 506 type Directed_Graph_Attributes is record | |
| 507 All_Edges : Edge_Map.Dynamic_Hash_Table := Edge_Map.Nil; | |
| 508 -- The map of edge -> edge attributes for all edges in the graph | |
| 509 | |
| 510 All_Vertices : Vertex_Map.Dynamic_Hash_Table := Vertex_Map.Nil; | |
| 511 -- The map of vertex -> vertex attributes for all vertices in the | |
| 512 -- graph. | |
| 513 | |
| 514 Components : Component_Map.Dynamic_Hash_Table := Component_Map.Nil; | |
| 515 -- The map of component -> component attributes for all components | |
| 516 -- in the graph. | |
| 517 end record; | |
| 518 | |
| 519 type Directed_Graph is access Directed_Graph_Attributes; | |
| 520 Nil : constant Directed_Graph := null; | |
| 521 | |
| 522 --------------- | |
| 523 -- Iterators -- | |
| 524 --------------- | |
| 525 | |
| 526 type All_Edge_Iterator is new Edge_Map.Iterator; | |
| 527 type All_Vertex_Iterator is new Vertex_Map.Iterator; | |
| 528 type Component_Iterator is new Component_Map.Iterator; | |
| 529 type Component_Vertex_Iterator is new Vertex_List.Iterator; | |
| 530 type Outgoing_Edge_Iterator is new Edge_Set.Iterator; | |
| 531 end Directed_Graphs; | |
| 532 | |
| 533 private | |
| 534 First_Component : constant Component_Id := No_Component + 1; | |
| 535 | |
| 536 end GNAT.Graphs; |