107 lines
3.4 KiB
Ada
107 lines
3.4 KiB
Ada
package body Digraphs is
|
|
|
|
function Node_Count(Graph: Graph_Type) return Node_Idx_With_Null is
|
|
begin
|
|
return Node_Idx_With_Null(Graph.Length);
|
|
end Node_Count;
|
|
|
|
procedure Add_Node(Graph: in out Graph_Type'Class; Node: Node_Index) is
|
|
begin
|
|
for I in Node_Index range Graph.Node_Count+1 .. Node loop
|
|
Graph.Append(Node_Vec.Empty_Vector);
|
|
end loop;
|
|
end Add_Node;
|
|
|
|
procedure Add_Connection
|
|
(Graph: in out Graph_Type'Class; From, To: Node_Index) is
|
|
begin
|
|
Graph.Add_Node(Node_Index'Max(From, To));
|
|
declare
|
|
Connection_List: Node_Vec.Vector := Graph.Element(From);
|
|
begin
|
|
for I in Connection_List.First_Index .. Connection_List.Last_Index loop
|
|
if Connection_List.Element(I) >= To then
|
|
if Connection_List.Element(I) = To then
|
|
return; -- if To is already there, don't add it a second time
|
|
else -- I is the first index with Element(I)>To, insert To here
|
|
Connection_List.Insert(Before => I, New_Item => To);
|
|
Graph.Replace_Element(From, Connection_List);
|
|
return;
|
|
end if;
|
|
end if;
|
|
end loop;
|
|
-- there was no I with no Element(I) > To, so insert To at the end
|
|
Connection_List.Append(To);
|
|
Graph.Replace_Element(From, Connection_List);
|
|
return;
|
|
end;
|
|
end Add_Connection;
|
|
|
|
procedure Del_Connection
|
|
(Graph: in out Graph_Type'Class; From, To: Node_Index) is
|
|
Connection_List: Node_Vec.Vector := Graph.Element(From);
|
|
begin
|
|
for I in Connection_List.First_Index .. Connection_List.Last_Index loop
|
|
if Connection_List.Element(I) = To then
|
|
Connection_List.Delete(I);
|
|
Graph.Replace_Element(From, Connection_List);
|
|
return; -- we are done
|
|
end if;
|
|
end loop;
|
|
end Del_Connection;
|
|
|
|
function Connected
|
|
(Graph: Graph_Type; From, To: Node_Index) return Boolean is
|
|
Connection_List: Node_Vec.Vector renames Graph.Element(From);
|
|
begin
|
|
for I in Connection_List.First_Index .. Connection_List.Last_Index loop
|
|
if Connection_List.Element(I) = To then
|
|
return True;
|
|
end if;
|
|
end loop;
|
|
return False;
|
|
end Connected;
|
|
|
|
function All_Connections
|
|
(Graph: Graph_Type; From: Node_Index) return Node_Vec.Vector is
|
|
begin
|
|
return Graph.Element(From);
|
|
end All_Connections;
|
|
|
|
function Top_Sort
|
|
(Graph: Graph_Type) return Node_Vec.Vector is
|
|
|
|
Result: Node_Vec.Vector;
|
|
Visited: array(1 .. Graph.Node_Count) of Boolean := (others => False);
|
|
Active: array(1 .. Graph.Node_Count) of Boolean := (others => False);
|
|
|
|
procedure Visit(Node: Node_Index) is
|
|
begin
|
|
if not Visited(Node) then
|
|
Visited(Node) := True;
|
|
Active(Node) := True;
|
|
declare
|
|
Cons: Node_Vec.Vector := All_Connections(Graph, Node);
|
|
begin
|
|
for Idx in Cons.First_Index .. Cons.Last_Index loop
|
|
Visit(Cons.Element(Idx));
|
|
end loop;
|
|
end;
|
|
Active(Node) := False;
|
|
Result.Append(Node);
|
|
else
|
|
if Active(Node) then
|
|
raise Constraint_Error with "Graph is Cyclic";
|
|
end if;
|
|
end if;
|
|
end Visit;
|
|
|
|
begin
|
|
for Some_Node in Visited'Range loop
|
|
Visit(Some_Node);
|
|
end loop;
|
|
return Result;
|
|
end Top_Sort;
|
|
|
|
end Digraphs;
|