1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118 | --
-- Copyright (C) 2021-2023, AdaCore
--
-- SPDX-License-Identifier: Apache-2.0 WITH LLVM-Exception
--
with Ada.Containers.Indefinite_Ordered_Maps;
with Ada.Containers.Ordered_Sets;
with Ada.Containers.Ordered_Maps;
with Ada.Strings.Unbounded;
with GPR2.View_Ids.Vector;
with GPR2.View_Ids.Set;
package GPR2.View_Ids.DAGs is
DAG_Error : exception;
type DAG is tagged limited private;
-- DAG instances
procedure Add_Vertex
(Self : in out DAG;
Vertex : View_Id;
Predecessors : View_Ids.Set.Set := View_Ids.Set.Empty_Set)
with Pre => not Self.Contains (Vertex),
Post => Self.Contains (Vertex);
-- Adds a node called Vertex to Self and set its predecessors to the
-- elements of Predecessors set.
procedure Update_Vertex
(Self : in out DAG;
Vertex : View_Id;
Predecessors : View_Ids.Set.Set := View_Ids.Set.Empty_Set)
with Post => Self.Contains (Vertex);
-- Updates or creates a node called Vertex to Self and add to its
-- predecessors the elements of Predecessors set.
procedure Update_Vertex
(Self : in out DAG;
Vertex : View_Id;
Predecessor : View_Id)
with Post => Self.Contains (Vertex);
-- Updates or creates a node called Vertex to Self and add a predecessor
function Contains (Self : DAG; Vertex : View_Id) return Boolean;
-- Returns True if Self contains a node called Vertex
procedure Update
(Self : in out DAG;
Circularity : out Boolean)
with Post => Self.Is_Up_To_Date;
-- Updates the internal structure of the DAG.
-- Circularity is set if a circularity is found during this update.
function Shortest_Circle (Self : DAG) return GPR2.View_Ids.Vector.Vector
with Pre => Self.Is_Up_To_Date;
-- Returns the smallest circle, if any, or the empty vector.
function Topological_Sort (Self : DAG) return View_Ids.Vector.Vector
with Pre => Self.Is_Up_To_Date;
-- Returns the list of nodes in a topological order
function Shortest_Path
(Self : DAG;
Source, Target : View_Id) return View_Ids.Vector.Vector
with Pre => Contains (Self, Source) and then Contains (Self, Target);
-- Computes the shortest path between two vertices of the DAG.
-- If target equals to Source then the algorithm tries to find the
-- shortest cycle including Source.
-- If there is no path between the two views, then the return value is
-- an empty vector.
procedure Clear (Self : in out DAG);
function As_Dot (Self : DAG) return Ada.Strings.Unbounded.Unbounded_String;
-- Returns the DAG representation in .dot format (graphviz)
function Is_Up_To_Date (Self : DAG) return Boolean;
-- Whether the topological information is up-to-date
private
type Node_Id is mod 2 ** 32;
Undefined : constant Node_Id := 0;
package Name_Node_Maps is new Ada.Containers.Indefinite_Ordered_Maps
(View_Id, Node_Id);
package Node_Name_Maps is new Ada.Containers.Indefinite_Ordered_Maps
(Node_Id, View_Id);
package Node_Node_Maps is new Ada.Containers.Indefinite_Ordered_Maps
(Node_Id, Node_Id);
package Node_Sets is new Ada.Containers.Ordered_Sets (Node_Id);
package Node_Node_Set_Maps is new Ada.Containers.Ordered_Maps
(Node_Id, Node_Sets.Set, "=" => Node_Sets."=");
type DAG is tagged limited record
Next_Free_Node : Node_Id := 1;
Predecessors : Node_Node_Set_Maps.Map;
Successors : Node_Node_Set_Maps.Map;
Vertex_Names : Name_Node_Maps.Map;
Vertex_Ids : Node_Name_Maps.Map;
Sort_Cache : View_Ids.Vector.Vector;
Has_Cycle : Boolean := False;
Cache_Valid : Boolean := True;
-- Whether the Sort_Cache is valid.
-- True by default with everything empty.
end record;
function Is_Up_To_Date (Self : DAG) return Boolean is
(Self.Cache_Valid);
-- Whether the topological information is up-to-date
end GPR2.View_Ids.DAGs;
|