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