diff options
| -rw-r--r-- | src/directed_graphs.adb | 761 | ||||
| -rw-r--r-- | src/directed_graphs.ads | 234 |
2 files changed, 577 insertions, 418 deletions
diff --git a/src/directed_graphs.adb b/src/directed_graphs.adb index 4acf0fa..8b59051 100644 --- a/src/directed_graphs.adb +++ b/src/directed_graphs.adb @@ -25,7 +25,11 @@ package body Directed_Graphs is return Boolean is begin if Left.From = Right.From then - return Left.To < Right.To; + if Left.To = Right.To then + return Left.ID < Right.ID; + else + return Left.To < Right.To; + end if; else return Left.From < Right.From; end if; @@ -75,52 +79,13 @@ package body Directed_Graphs is - ------------ - -- Append -- - ------------ - - procedure Append - (Container : in out Graph; - Position : out Cursor) - is - Node : Node_Type := Node_Type'First; - Insert_Success : Boolean; - begin - while Container.Connections.Contains (Node) loop - if Impl.Checks and then Node = Node_Type'Last then - raise Constraint_Error with "Graph has no unused nodes"; - end if; - Node := Node_Type'Succ (Node); - end loop; - Impl.TC_Check (Container.Tamper_Info); - Container.Connections.Insert - (Node, Node_Vectors.Empty_Vector, Position.Place, Insert_Success); - if Impl.Checks and then not Insert_Success then - raise Program_Error with "Graph Insert failed"; - end if; - Position.Container := Container'Unrestricted_Access; - Position.Sub_Index := Node_Vectors.Extended_Index'First; - end Append; - - procedure Append - (Container : in out Graph; - Label : in Node_Label_Type; - Position : out Cursor) is - begin - Container.Append (Position); - Container.Node_Labels.Insert (Element (Position), Label); - end Append; - - - - ------------------ -- Append_Label -- ------------------ procedure Append_Label (Container : in out Graph; - Node : in Node_Type; + Node : in Node_ID_Type; Label : in Node_Label_Type) is begin if Impl.Checks then @@ -134,8 +99,8 @@ package body Directed_Graphs is end Append_Label; procedure Append_Label - (Position : in out Cursor; - Label : in Node_Label_Type) is + (Position : in Cursor; + Label : in Node_Label_Type) is begin if Impl.Checks then if Position.Container = null then @@ -164,28 +129,14 @@ package body Directed_Graphs is end Append_Label; procedure Append_Label - (Parent, Child : in out Cursor; - Label : in Edge_Label_Type) is + (Container : in Cursor; + Edge : in Edge_Type; + Label : in Edge_Label_Type) is begin - if Impl.Checks then - if Parent.Container = null then - raise Constraint_Error with "Graph for parent cursor does not exist"; - end if; - if Child.Container = null then - raise Constraint_Error with "Graph for child cursor does not exist"; - end if; - if Parent.Container /= Child.Container then - raise Constraint_Error with "Cursors are for different graphs"; - end if; - if not Has_Edge (Parent, Child) then - raise Constraint_Error with "Graph does not contain edge"; - end if; - if Has_Label (Parent, Child) then - raise Constraint_Error with "Edge already has label"; - end if; + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; end if; - Parent.Container.Edge_Labels.Insert - ((From => Element (Parent), To => Element (Child)), Label); + Container.Container.Append_Label (Edge, Label); end Append_Label; @@ -211,22 +162,73 @@ package body Directed_Graphs is + ------------- + -- Between -- + ------------- + + function Between + (Container : in Graph; + Parent, Child : in Node_ID_Type) + return Edge_Array + is + function V2A is new Vector_To_Array (Edge_Type, Edge_Array, Edge_Vectors); + Result : Edge_Vectors.Vector; + begin + for E of Container.Outbound (Parent) loop + if E.To = Child then + Result.Append (E); + end if; + end loop; + return V2A (Result); + end Between; + + function Between + (Parent, Child : in Cursor) + return Edge_Array is + begin + if Impl.Checks then + if Parent.Container = null then + raise Constraint_Error with "Graph for parent cursor does not exist"; + end if; + if Child.Container = null then + raise Constraint_Error with "Graph for child cursor does not exist"; + end if; + if Parent.Container /= Child.Container then + raise Constraint_Error with "Parent and child cursors refer to different graphs"; + end if; + if not Has_Element (Parent) then + raise Constraint_Error with "Parent cursor points to nothing"; + end if; + if not Has_Element (Child) then + raise Constraint_Error with "Child cursor points to nothing"; + end if; + end if; + return Parent.Container.Between (Element (Parent), Element (Child)); + end Between; + + + + -------------- -- Children -- -------------- function Children (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Node_Array is + function V2A is new Vector_To_Array (Node_ID_Type, Node_Array, Node_Vectors); Lock : Impl.With_Lock (Container.Tamper_Info'Unrestricted_Access); - function V2A is new Vector_To_Array (Node_Type, Node_Array, Node_Vectors); + Result : Node_Vectors.Vector; begin if Impl.Checks and then not Container.Contains (Node) then raise Constraint_Error with "Graph does not contain node"; end if; - return V2A (Container.Connections.Constant_Reference (Node)); + for A of Container.Connections.Element (Node) loop + Result.Append (A.Node_ID); + end loop; + return V2A (Result); end Children; function Children @@ -283,7 +285,7 @@ package body Directed_Graphs is function Constant_Label_Reference (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Node_Label_Constant_Reference is begin if Impl.Checks then @@ -347,38 +349,14 @@ package body Directed_Graphs is end Constant_Label_Reference; function Constant_Label_Reference - (Parent, Child : in Cursor) + (Container : in Cursor; + Edge : in Edge_Type) return Edge_Label_Constant_Reference is begin - if Impl.Checks then - if Parent.Container = null then - raise Constraint_Error with "Graph for parent cursor does not exist"; - end if; - if Child.Container = null then - raise Constraint_Error with "Graph for child cursor does not exist"; - end if; - if Parent.Container /= Child.Container then - raise Constraint_Error with "Cursors are for different graphs"; - end if; - if not Has_Edge (Parent, Child) then - raise Constraint_Error with "Graph does not contain edge"; - end if; - if not Has_Label (Parent, Child) then - raise Constraint_Error with "Edge does not have a label"; - end if; + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; end if; - declare - Tamper : constant Help.Tamper_Counts_Access := - Parent.Container.Tamper_Info'Unrestricted_Access; - Edge : Edge_Type := ((From => Element (Parent), To => Element (Child))); - begin - return Ref : constant Edge_Label_Constant_Reference := - (Element => Parent.Container.Edge_Labels.Constant_Reference (Edge).Element, - Control => (Ada.Finalization.Controlled with Tamper)) - do - Impl.Lock (Tamper.all); - end return; - end; + return Container.Container.Constant_Label_Reference (Edge); end Constant_Label_Reference; @@ -390,7 +368,7 @@ package body Directed_Graphs is function Contains (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Boolean is begin return Container.Connections.Contains (Node); @@ -398,7 +376,7 @@ package body Directed_Graphs is function Contains (Container : in Graph; - Node : in Node_Type; + Node : in Node_ID_Type; Label : in Node_Label_Type) return Boolean is begin @@ -409,11 +387,27 @@ package body Directed_Graphs is function Contains (Container : in Graph; + Edge_ID : in Edge_ID_Type) + return Boolean is + begin + for N of Container.Connections loop + for A of N loop + if A.Edge_ID = Edge_ID then + return True; + end if; + end loop; + end loop; + return False; + end Contains; + + function Contains + (Container : in Graph; Edge : in Edge_Type) return Boolean is begin return Container.Connections.Contains (Edge.From) and then - Container.Connections.Constant_Reference (Edge.From).Contains (Edge.To); + Container.Connections.Constant_Reference (Edge.From).Contains + ((Edge_ID => Edge.ID, Node_ID => Edge.To)); end Contains; function Contains @@ -436,7 +430,7 @@ package body Directed_Graphs is function Contains_In_Subgraph (Position : in Cursor; - Node : in Node_Type) + Node : in Node_ID_Type) return Boolean is begin if Position.Container = null then @@ -452,7 +446,7 @@ package body Directed_Graphs is function Contains_In_Subgraph (Position : in Cursor; - Node : in Node_Type; + Node : in Node_ID_Type; Label : in Node_Label_Type) return Boolean is begin @@ -465,24 +459,36 @@ package body Directed_Graphs is function Contains_In_Subgraph (Position : in Cursor; + Edge_ID : in Edge_ID_Type) + return Boolean is + begin + if Position.Container = null then + return False; + end if; + for C in Position.Container.Iterate_Subgraph (Position) loop + for E of Position.Container.Outbound (Element (C)) loop + if E.ID = Edge_ID then + return True; + end if; + end loop; + end loop; + return False; + end Contains_In_Subgraph; + + function Contains_In_Subgraph + (Position : in Cursor; Edge : in Edge_Type) - return Boolean - is - Parent_Check, Child_Check : Boolean := False; + return Boolean is begin if Position.Container = null then return False; end if; for C in Position.Container.Iterate_Subgraph (Position) loop - if Element (C) = Edge.From then - Parent_Check := True; - end if; - if Element (C) = Edge.To then - Child_Check := True; - end if; - if Parent_Check and Child_Check then - return Position.Container.Contains (Edge); - end if; + for E of Position.Container.Outbound (Element (C)) loop + if E = Edge then + return True; + end if; + end loop; end loop; return False; end Contains_In_Subgraph; @@ -615,7 +621,7 @@ package body Directed_Graphs is function Cursor_To (Position : in Cursor; - Node : in Node_Type) + Node : in Node_ID_Type) return Cursor is begin if Impl.Checks then @@ -638,7 +644,7 @@ package body Directed_Graphs is function Degree (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Ada.Containers.Count_Type is begin return Container.Indegree (Node) + Container.Outdegree (Node); @@ -668,14 +674,14 @@ package body Directed_Graphs is procedure Delete (Container : in out Graph; - Node : in Node_Type) is + Node : in Node_ID_Type) is begin if Impl.Checks and then not Container.Contains (Node) then raise Constraint_Error with "Graph does not contain node"; end if; Impl.TC_Check (Container.Tamper_Info); for N of Container.Connections.Constant_Reference (Node) loop - Container.Edge_Labels.Exclude ((From => Node, To => N)); + Container.Edge_Labels.Exclude ((ID => N.Edge_ID, From => Node, To => N.Node_ID)); end loop; Container.Connections.Delete (Node); Container.Node_Labels.Exclude (Node); @@ -685,9 +691,9 @@ package body Directed_Graphs is Container.Connections.Reference (C); begin for I in reverse 1 .. Ref.Last_Index loop - if Ref (I) = Node then + if Ref (I).Node_ID = Node then Container.Edge_Labels.Exclude - ((From => Node_Maps.Key (C), To => Node)); + ((ID => Ref (I).Edge_ID, From => Node_Maps.Key (C), To => Node)); Ref.Delete (I); end if; end loop; @@ -707,6 +713,7 @@ package body Directed_Graphs is end if; end if; Position.Container.Delete (Element (Position)); + Position := No_Element; end Delete; procedure Delete @@ -730,29 +737,18 @@ package body Directed_Graphs is Ref : Node_Maps.Reference_Type := Container.Connections.Reference (Edge.From); begin - Ref.Delete (Ref.Find_Index (Edge.To)); + Ref.Delete (Ref.Find_Index ((Edge_ID => Edge.ID, Node_ID => Edge.To))); end; end Delete; procedure Delete - (Parent, Child : in out Cursor) is + (Container : in Cursor; + Edge : in Edge_Type) is begin - if Impl.Checks then - if Parent.Container = null then - raise Constraint_Error with "Graph for parent cursor does not exist"; - end if; - if Child.Container = null then - raise Constraint_Error with "Graph for child cursor does not exist"; - end if; - if Parent.Container /= Child.Container then - raise Constraint_Error with "Cursors are for different graphs"; - end if; + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; end if; - declare - Edge : Edge_Type := (From => Element (Parent), To => Element (Child)); - begin - Parent.Container.Delete (Edge); - end; + Container.Container.Delete (Edge); end Delete; procedure Delete @@ -773,7 +769,7 @@ package body Directed_Graphs is procedure Delete_Label (Container : in out Graph; - Node : in Node_Type) is + Node : in Node_ID_Type) is begin if Impl.Checks and then not Container.Node_Labels.Contains (Node) then raise Constraint_Error with "Node does not have label"; @@ -782,7 +778,7 @@ package body Directed_Graphs is end Delete_Label; procedure Delete_Label - (Position : in out Cursor) is + (Position : in Cursor) is begin if Impl.Checks then if Position.Container = null then @@ -806,24 +802,13 @@ package body Directed_Graphs is end Delete_Label; procedure Delete_Label - (Parent, Child : in out Cursor) is + (Container : in Cursor; + Edge : in Edge_Type) is begin - if Impl.Checks then - if Parent.Container = null then - raise Constraint_Error with "Graph for parent cursor does not exist"; - end if; - if Child.Container = null then - raise Constraint_Error with "Graph for child cursor does not exist"; - end if; - if Parent.Container /= Child.Container then - raise Constraint_Error with "Cursors are for different graphs"; - end if; - if not Has_Edge (Parent, Child) then - raise Constraint_Error with "Graph does not contain edge"; - end if; + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; end if; - Parent.Container.Delete_Label - ((From => Element (Parent), To => Element (Child))); + Container.Container.Delete_Label (Edge); end Delete_Label; @@ -875,6 +860,23 @@ package body Directed_Graphs is end Edge_Count; function Edge_Count + (Container : in Cursor) + return Ada.Containers.Count_Type is + begin + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + return Container.Container.Edge_Count; + end Edge_Count; + + + + + ---------------------------- + -- Edge_Count_In_Subgraph -- + ---------------------------- + + function Edge_Count_In_Subgraph (Position : in Cursor) return Ada.Containers.Count_Type is @@ -892,7 +894,7 @@ package body Directed_Graphs is Result := Result + Outdegree (Position); end loop; return Result; - end Edge_Count; + end Edge_Count_In_Subgraph; @@ -911,14 +913,32 @@ package body Directed_Graphs is for C in Container.Connections.Iterate loop for N of Container.Connections.Constant_Reference (C) loop Tos.Append - ((From => Node_Maps.Key (C), - To => N)); + ((ID => N.Edge_ID, + From => Node_Maps.Key (C), + To => N.Node_ID)); end loop; end loop; return V2A (Tos); end Edges; function Edges + (Container : in Cursor) + return Edge_Array is + begin + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + return Container.Container.Edges; + end Edges; + + + + + ----------------------- + -- Edges_In_Subgraph -- + ----------------------- + + function Edges_In_Subgraph (Position : in Cursor) return Edge_Array is @@ -939,7 +959,7 @@ package body Directed_Graphs is end loop; end loop; return V2A (Tos); - end Edges; + end Edges_In_Subgraph; @@ -950,17 +970,20 @@ package body Directed_Graphs is function Element (Position : in Cursor) - return Node_Type is + return Extended_Node_ID_Type + is + use type Node_Maps.Cursor; begin - if Impl.Checks then - if Position.Container = null then - raise Constraint_Error with "Graph does not exist"; - end if; - if not Has_Element (Position) then - raise Constraint_Error with "Cursor points to nothing"; - end if; + if Impl.Checks and then Position.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + if Position.Place = Node_Maps.No_Element or else + not Position.Container.Contains (Node_Maps.Key (Position.Place)) + then + return No_Node; + else + return Node_Maps.Key (Position.Place); end if; - return Node_Maps.Key (Position.Place); end Element; @@ -1001,7 +1024,7 @@ package body Directed_Graphs is return Node_Array is Result : Node_Vectors.Vector; - function V2A is new Vector_To_Array (Node_Type, Node_Array, Node_Vectors); + function V2A is new Vector_To_Array (Node_ID_Type, Node_Array, Node_Vectors); begin for C in Container.Node_Labels.Iterate loop if Container.Node_Labels.Constant_Reference (C) = Label then @@ -1040,7 +1063,7 @@ package body Directed_Graphs is return Node_Array is Result : Node_Vectors.Vector; - function V2A is new Vector_To_Array (Node_Type, Node_Array, Node_Vectors); + function V2A is new Vector_To_Array (Node_ID_Type, Node_Array, Node_Vectors); begin if Impl.Checks then if Position.Container = null then @@ -1165,7 +1188,7 @@ package body Directed_Graphs is function Has_Edge (Container : in Graph; - Parent, Child : in Node_Type) + Parent, Child : in Node_ID_Type) return Boolean is begin if Impl.Checks then @@ -1175,7 +1198,12 @@ package body Directed_Graphs is raise Constraint_Error with "Graph does not contain child node"; end if; end if; - return Container.Contains ((From => Parent, To => Child)); + for N of Container.Connections.Constant_Reference (Parent) loop + if N.Node_ID = Child then + return True; + end if; + end loop; + return False; end Has_Edge; function Has_Edge @@ -1192,11 +1220,11 @@ package body Directed_Graphs is if Parent.Container /= Child.Container then raise Constraint_Error with "Parent and Child Graph mismatch"; end if; - if not Parent.Container.Contains (Element (Parent)) then - raise Constraint_Error with "Graph does not contain parent node"; + if not Has_Element (Parent) then + raise Constraint_Error with "Parent cursor points to nothing"; end if; - if not Child.Container.Contains (Element (Child)) then - raise Constraint_Error with "Graph does not contain child node"; + if not Has_Element (Child) then + raise Constraint_Error with "Child cursor points to nothing"; end if; end if; return Parent.Container.Has_Edge (Element (Parent), Element (Child)); @@ -1226,7 +1254,7 @@ package body Directed_Graphs is function Has_Label (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Boolean is begin return Container.Node_Labels.Contains (Node); @@ -1256,28 +1284,14 @@ package body Directed_Graphs is end Has_Label; function Has_Label - (Parent, Child : in Cursor) + (Container : in Cursor; + Edge : in Edge_Type) return Boolean is begin - if Impl.Checks then - if Parent.Container = null then - raise Constraint_Error with "Graph for parent cursor does not exist"; - end if; - if Child.Container = null then - raise Constraint_Error with "Graph for child cursor does not exist"; - end if; - if Parent.Container /= Child.Container then - raise Constraint_Error with "Cursors are for different graphs"; - end if; - if not Has_Element (Parent) then - raise Constraint_Error with "Parent cursor points to nothing"; - end if; - if not Has_Element (Child) then - raise Constraint_Error with "Child cursor points to nothing"; - end if; + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; end if; - return Parent.Container.Edge_Labels.Contains - ((From => Element (Parent), To => Element (Child))); + return Container.Container.Edge_Labels.Contains (Edge); end Has_Label; @@ -1289,11 +1303,19 @@ package body Directed_Graphs is function Has_Labeled_Edge (Container : in Graph; - Parent, Child : Node_Type) + Parent, Child : Node_ID_Type) return Boolean is begin - return Container.Has_Edge (Parent, Child) and - Container.Has_Label ((From => Parent, To => Child)); + if Container.Has_Edge (Parent, Child) then + for C in Container.Edge_Labels.Iterate loop + if Edge_Label_Maps.Key (C).From = Parent and + Edge_Label_Maps.Key (C).To = Child + then + return True; + end if; + end loop; + end if; + return False; end Has_Labeled_Edge; function Has_Labeled_Edge @@ -1310,6 +1332,12 @@ package body Directed_Graphs is if Parent.Container /= Child.Container then raise Constraint_Error with "Parent and Child Graph mismatch"; end if; + if not Has_Element (Parent) then + raise Constraint_Error with "Parent cursor points to nothing"; + end if; + if not Has_Element (Child) then + raise Constraint_Error with "Child cursor points to nothing"; + end if; if not Parent.Container.Contains (Element (Parent)) then raise Constraint_Error with "Graph does not contain parent node"; end if; @@ -1329,7 +1357,7 @@ package body Directed_Graphs is function Has_Neighbor (Container : in Graph; - Left, Right : in Node_Type) + Left, Right : in Node_ID_Type) return Boolean is begin return Container.Has_Edge (Left, Right) and @@ -1369,7 +1397,7 @@ package body Directed_Graphs is function Inbound (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Edge_Array is Lock : Impl.With_Lock (Container.Tamper_Info'Unrestricted_Access); @@ -1378,10 +1406,11 @@ package body Directed_Graphs is begin for C in Container.Connections.Iterate loop for N of Container.Connections.Constant_Reference (C) loop - if N = Node then + if N.Node_ID = Node then Edges.Append - ((From => Node_Maps.Key (C), - To => N)); + ((ID => N.Edge_ID, + From => Node_Maps.Key (C), + To => N.Node_ID)); end if; end loop; end loop; @@ -1412,7 +1441,7 @@ package body Directed_Graphs is function Indegree (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Ada.Containers.Count_Type is Lock : Impl.With_Lock (Container.Tamper_Info'Unrestricted_Access); @@ -1420,7 +1449,7 @@ package body Directed_Graphs is begin for C of Container.Connections loop for N of C loop - if N = Node then + if N.Node_ID = Node then Count := Count + 1; end if; end loop; @@ -1452,18 +1481,18 @@ package body Directed_Graphs is procedure Insert (Container : in out Graph; - Node : in Node_Type) is + Node : in Node_ID_Type) is begin if Impl.Checks and then Container.Contains (Node) then raise Constraint_Error with "Graph already contains node"; end if; Impl.TC_Check (Container.Tamper_Info); - Container.Connections.Insert (Node, Node_Vectors.Empty_Vector); + Container.Connections.Insert (Node, Adj_Vectors.Empty_Vector); end Insert; procedure Insert (Container : in out Graph; - Node : in Node_Type; + Node : in Node_ID_Type; Label : in Node_Label_Type) is begin Container.Insert (Node); @@ -1471,6 +1500,27 @@ package body Directed_Graphs is end Insert; procedure Insert + (Container : in Cursor; + Node : in Node_ID_Type) is + begin + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + Container.Container.Insert (Node); + end Insert; + + procedure Insert + (Container : in Cursor; + Node : in Node_ID_Type; + Label : in Node_Label_Type) is + begin + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + Container.Container.Insert (Node, Label); + end Insert; + + procedure Insert (Container : in out Graph; Nodes : in Node_Array) is begin @@ -1491,7 +1541,8 @@ package body Directed_Graphs is raise Constraint_Error with "Graph does not contain head node of edge"; end if; end if; - Container.Connections.Reference (Edge.From).Append (Edge.To); + Container.Connections.Reference (Edge.From).Append + ((Edge_ID => Edge.ID, Node_ID => Edge.To)); end Insert; procedure Insert @@ -1504,35 +1555,24 @@ package body Directed_Graphs is end Insert; procedure Insert - (Parent, Child : in out Cursor) is + (Container : in Cursor; + Edge : in Edge_Type) is begin - if Impl.Checks then - if Parent.Container = null then - raise Constraint_Error with "Graph for parent cursor does not exist"; - end if; - if Child.Container = null then - raise Constraint_Error with "Graph for child cursor does not exist"; - end if; - if Parent.Container /= Child.Container then - raise Constraint_Error with "Cursors are for different graphs"; - end if; - if not Has_Element (Parent) then - raise Constraint_Error with "Parent cursor points to nothing"; - end if; - if not Has_Element (Child) then - raise Constraint_Error with "Child cursor points to nothing"; - end if; + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; end if; - Parent.Container.Connections.Reference (Element (Parent)).Append (Element (Child)); + Container.Container.Insert (Edge); end Insert; procedure Insert - (Parent, Child : in out Cursor; - Label : in Edge_Label_Type) is + (Container : in Cursor; + Edge : in Edge_Type; + Label : in Edge_Label_Type) is begin - Insert (Parent, Child); - Parent.Container.Edge_Labels.Insert - ((From => Element (Parent), To => Element (Child)), Label); + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + Container.Container.Insert (Edge, Label); end Insert; procedure Insert @@ -1587,7 +1627,7 @@ package body Directed_Graphs is Position : in Cursor) return Graph_Iterator_Interfaces.Reversible_Iterator'Class is - Root_Node, Current_Node : Node_Type; + Root_Node, Current_Node : Node_ID_Type; Path_Up : Node_Vectors.Vector; Visited : Node_Vectors.Vector; begin @@ -1631,7 +1671,7 @@ package body Directed_Graphs is function Label (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Node_Label_Type is begin if Impl.Checks then @@ -1675,25 +1715,14 @@ package body Directed_Graphs is end Label; function Label - (Parent, Child : in Cursor) + (Container : in Cursor; + Edge : in Edge_Type) return Edge_Label_Type is begin - if Impl.Checks then - if Parent.Container = null then - raise Constraint_Error with "Graph for parent cursor does not exist"; - end if; - if Child.Container = null then - raise Constraint_Error with "Graph for child cursor does not exist"; - end if; - if Parent.Container /= Child.Container then - raise Constraint_Error with "Cursors are for different graphs"; - end if; - if not Has_Edge (Parent, Child) then - raise Constraint_Error with "Graph does not contain edge"; - end if; + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; end if; - return Parent.Container.Edge_Labels.Element - ((From => Element (Parent), To => Element (Child))); + return Container.Container.Label (Edge); end Label; @@ -1705,7 +1734,7 @@ package body Directed_Graphs is function Label_Reference (Container : aliased in out Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Node_Label_Reference is begin if Impl.Checks then @@ -1769,38 +1798,14 @@ package body Directed_Graphs is end Label_Reference; function Label_Reference - (Parent, Child : in Cursor) + (Container : in Cursor; + Edge : in Edge_Type) return Edge_Label_Reference is begin - if Impl.Checks then - if Parent.Container = null then - raise Constraint_Error with "Graph for parent cursor does not exist"; - end if; - if Child.Container = null then - raise Constraint_Error with "Graph for child cursor does not exist"; - end if; - if Parent.Container /= Child.Container then - raise Constraint_Error with "Cursors are for different graphs"; - end if; - if not Has_Edge (Parent, Child) then - raise Constraint_Error with "Graph does not contain edge"; - end if; - if not Has_Label (Parent, Child) then - raise Constraint_Error with "Edge does not have a label"; - end if; + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; end if; - declare - Tamper : constant Help.Tamper_Counts_Access := - Parent.Container.Tamper_Info'Unrestricted_Access; - Edge : Edge_Type := ((From => Element (Parent), To => Element (Child))); - begin - return Ref : constant Edge_Label_Reference := - (Element => Parent.Container.Edge_Labels.Reference (Edge).Element, - Control => (Ada.Finalization.Controlled with Tamper)) - do - Impl.Lock (Tamper.all); - end return; - end; + return Container.Container.Label_Reference (Edge); end Label_Reference; @@ -1876,23 +1881,31 @@ package body Directed_Graphs is function Neighbors (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Node_Array is - Nodes : Node_Vectors.Vector; - Ref : Node_Maps.Constant_Reference_Type := - Container.Connections.Constant_Reference (Node); - function V2A is new Vector_To_Array (Node_Type, Node_Array, Node_Vectors); + Result : Node_Vectors.Vector; + To_Del : Boolean; + function V2A is new Vector_To_Array (Node_ID_Type, Node_Array, Node_Vectors); begin - for C in Container.Connections.Iterate loop - for N of Container.Connections.Constant_Reference (C) loop - if N = Node and Ref.Contains (Node_Maps.Key (C)) then - Nodes.Append (N); + for N of Container.Connections.Constant_Reference (Node) loop + if not Result.Contains (N.Node_ID) then + Result.Append (N.Node_ID); + end if; + end loop; + for I in reverse 1 .. Result.Last_Index loop + To_Del := True; + for N of Container.Connections.Constant_Reference (Result (I)) loop + if N.Node_ID = Node then + To_Del := False; exit; end if; end loop; + if To_Del then + Result.Delete (I); + end if; end loop; - return V2A (Nodes); + return V2A (Result); end Neighbors; function Neighbors @@ -1997,6 +2010,23 @@ package body Directed_Graphs is end Node_Count; function Node_Count + (Container : in Cursor) + return Ada.Containers.Count_Type is + begin + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + return Container.Container.Connections.Length; + end Node_Count; + + + + + ---------------------------- + -- Node_Count_In_Subgraph -- + ---------------------------- + + function Node_Count_In_Subgraph (Position : in Cursor) return Ada.Containers.Count_Type is begin @@ -2014,7 +2044,7 @@ package body Directed_Graphs is begin return Subgraph_Iterator (It).Nodes.Length; end; - end Node_Count; + end Node_Count_In_Subgraph; @@ -2025,14 +2055,14 @@ package body Directed_Graphs is procedure Node_Range (Container : in Graph; - Minimum : out Node_Type; - Maximum : out Node_Type) is + Minimum : out Node_ID_Type; + Maximum : out Node_ID_Type) is begin if Impl.Checks and then Container.Is_Empty then raise Constraint_Error with "Graph is empty"; end if; - Minimum := Node_Type'Last; - Maximum := Node_Type'First; + Minimum := Node_ID_Type'Last; + Maximum := Node_ID_Type'First; for C in Container.Connections.Iterate loop if Node_Maps.Key (C) < Minimum then Minimum := Node_Maps.Key (C); @@ -2054,7 +2084,7 @@ package body Directed_Graphs is (Container : in Graph) return Node_Array is - function V2A is new Vector_To_Array (Node_Type, Node_Array, Node_Vectors); + function V2A is new Vector_To_Array (Node_ID_Type, Node_Array, Node_Vectors); Result : Node_Vectors.Vector; begin for C in Container.Connections.Iterate loop @@ -2064,11 +2094,28 @@ package body Directed_Graphs is end Nodes; function Nodes + (Container : in Cursor) + return Node_Array is + begin + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + return Container.Container.Nodes; + end Nodes; + + + + + ----------------------- + -- Nodes_In_Subgraph -- + ----------------------- + + function Nodes_In_Subgraph (Position : in Cursor) return Node_Array is Result : Node_Vectors.Vector; - function V2A is new Vector_To_Array (Node_Type, Node_Array, Node_Vectors); + function V2A is new Vector_To_Array (Node_ID_Type, Node_Array, Node_Vectors); begin if Impl.Checks then if Position.Container = null then @@ -2082,7 +2129,7 @@ package body Directed_Graphs is Result.Append (Element (C)); end loop; return V2A (Result); - end Nodes; + end Nodes_In_Subgraph; @@ -2093,7 +2140,7 @@ package body Directed_Graphs is function Outbound (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Edge_Array is begin if Impl.Checks and then not Container.Contains (Node) then @@ -2106,8 +2153,9 @@ package body Directed_Graphs is begin for I in Result'Range loop Result (I) := - (From => Node, - To => Node_Vectors.Element (Ref, I)); + (ID => Ref.Element.Element (I).Edge_ID, + From => Node, + To => Ref.Element.Element (I).Node_ID); end loop; return Result; end; @@ -2137,7 +2185,7 @@ package body Directed_Graphs is function Outdegree (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Ada.Containers.Count_Type is begin if Impl.Checks and then not Container.Contains (Node) then @@ -2171,16 +2219,16 @@ package body Directed_Graphs is function Parents (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Node_Array is Lock : Impl.With_Lock (Container.Tamper_Info'Unrestricted_Access); Froms : Node_Vectors.Vector; - function V2A is new Vector_To_Array (Node_Type, Node_Array, Node_Vectors); + function V2A is new Vector_To_Array (Node_ID_Type, Node_Array, Node_Vectors); begin for C in Container.Connections.Iterate loop for N of Container.Connections.Constant_Reference (C) loop - if N = Node then + if N.Node_ID = Node and not Froms.Contains (Node_Maps.Key (C)) then Froms.Append (Node_Maps.Key (C)); exit; end if; @@ -2337,7 +2385,7 @@ package body Directed_Graphs is procedure Replace_Label (Container : in out Graph; - Node : in Node_Type; + Node : in Node_ID_Type; Label : in Node_Label_Type) is begin if Impl.Checks and then not Container.Contains (Node) then @@ -2347,8 +2395,8 @@ package body Directed_Graphs is end Replace_Label; procedure Replace_Label - (Position : in out Cursor; - Label : in Node_Label_Type) is + (Position : in Cursor; + Label : in Node_Label_Type) is begin if Impl.Checks then if Position.Container = null then @@ -2373,25 +2421,14 @@ package body Directed_Graphs is end Replace_Label; procedure Replace_Label - (Parent, Child : in out Cursor; - Label : in Edge_Label_Type) is + (Container : in Cursor; + Edge : in Edge_Type; + Label : in Edge_Label_Type) is begin - if Impl.Checks then - if Parent.Container = null then - raise Constraint_Error with "Graph for parent cursor does not exist"; - end if; - if Child.Container = null then - raise Constraint_Error with "Graph for child cursor does not exist"; - end if; - if Parent.Container /= Child.Container then - raise Constraint_Error with "Cursors belong to different graphs"; - end if; - if not Has_Edge (Parent, Child) then - raise Constraint_Error with "Graph does not contain edge"; - end if; + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; end if; - Parent.Container.Edge_Labels.Replace - ((From => Element (Parent), To => Element (Child)), Label); + Container.Container.Replace_Label (Edge, Label); end Replace_Label; @@ -2403,9 +2440,9 @@ package body Directed_Graphs is procedure Swap (Container : in out Graph; - Left, Right : in Node_Type) + Left, Right : in Node_ID_Type) is - Temp_Vector : Node_Vectors.Vector; + Temp_Vector : Adj_Vectors.Vector; begin if Impl.Checks then if not Container.Contains (Left) then @@ -2423,10 +2460,10 @@ package body Directed_Graphs is -- Switch the edge connections around for V of Container.Connections loop for N of V loop - if N = Left then - N := Right; - elsif N = Right then - N := Left; + if N.Node_ID = Left then + N.Node_ID := Right; + elsif N.Node_ID = Right then + N.Node_ID := Left; end if; end loop; end loop; @@ -2458,7 +2495,7 @@ package body Directed_Graphs is function To_Cursor (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Cursor is begin if not Container.Connections.Contains (Node) then @@ -2497,7 +2534,7 @@ package body Directed_Graphs is end if; end loop; end if; - Adj_Map.Insert (Nodes (I), Node_Vectors.Empty_Vector); + Adj_Map.Insert (Nodes (I), Adj_Vectors.Empty_Vector); end loop; for E of Edges loop @@ -2506,7 +2543,7 @@ package body Directed_Graphs is then raise Constraint_Error with "Edge uses nodes not in graph"; end if; - Adj_Map.Reference (E.From).Append (E.To); + Adj_Map.Reference (E.From).Append ((E.ID, E.To)); end loop; return G : Graph := @@ -2518,18 +2555,64 @@ package body Directed_Graphs is ------------------ - -- Unused_Nodes -- + -- Unused -- ------------------ - function Unused_Nodes + function Unused + (Container : in Graph) + return Node_ID_Type is + begin + for N in Node_ID_Type'First .. Node_ID_Type'Last loop + if not Container.Contains (N) then + return N; + end if; + end loop; + raise Constraint_Error with "No unused nodes available"; + return Extended_Node_ID_Type'First; + end Unused; + + function Unused + (Container : in Graph) + return Edge_ID_Type is + begin + for E in Edge_ID_Type'First .. Edge_ID_Type'Last loop + if not Container.Contains (E) then + return E; + end if; + end loop; + raise Constraint_Error with "No unused edges available"; + return Edge_ID_Type'First; + end Unused; + + function Unused + (Container : in Cursor) + return Node_ID_Type is + begin + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + return Unused (Container.Container.all); + end Unused; + + function Unused + (Container : in Cursor) + return Edge_ID_Type is + begin + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + return Unused (Container.Container.all); + end Unused; + + function Unused (Container : in Graph; Count : in Positive := 1) return Node_Array is - function V2A is new Vector_To_Array (Node_Type, Node_Array, Node_Vectors); + function V2A is new Vector_To_Array (Node_ID_Type, Node_Array, Node_Vectors); Nodes : Node_Vectors.Vector; begin - for N in Node_Type'First .. Node_Type'Last loop + for N in Node_ID_Type'First .. Node_ID_Type'Last loop if not Container.Contains (N) then Nodes.Append (N); end if; @@ -2539,7 +2622,7 @@ package body Directed_Graphs is end loop; raise Constraint_Error with "Not enough unused nodes"; return V2A (Nodes); - end Unused_Nodes; + end Unused; diff --git a/src/directed_graphs.ads b/src/directed_graphs.ads index c8812a9..925948d 100644 --- a/src/directed_graphs.ads +++ b/src/directed_graphs.ads @@ -22,12 +22,18 @@ private with generic - type Node_Type is (<>); + type Node_ID_Type is (<>); + type Edge_ID_Type is (<>); + type Node_Label_Type is private; type Edge_Label_Type is private; with function "=" - (Left, Right : in Node_Type) + (Left, Right : in Node_ID_Type) + return Boolean is <>; + + with function "=" + (Left, Right : in Edge_ID_Type) return Boolean is <>; with function "=" @@ -47,13 +53,12 @@ package Directed_Graphs is - subtype Extended_Node_Type is Node_Type'Base - range Node_Type'Pred (Node_Type'First) .. Node_Type'Succ - (Node_Type'Min (Node_Type'Base'Pred (Node_Type'Base'Last), Node_Type'Last)); + subtype Extended_Node_ID_Type is Node_ID_Type'Base + range Node_ID_Type'Pred (Node_ID_Type'First) .. Node_ID_Type'Last; - No_Node : constant Extended_Node_Type := Extended_Node_Type'First; + No_Node : constant Extended_Node_ID_Type := Extended_Node_ID_Type'First; - type Node_Array is array (Positive range <>) of Node_Type; + type Node_Array is array (Positive range <>) of Node_ID_Type; subtype Path is Node_Array; @@ -61,8 +66,9 @@ package Directed_Graphs is type Edge_Type is record - From : Node_Type; - To : Node_Type; + ID : Edge_ID_Type; + From : Node_ID_Type; + To : Node_ID_Type; end record; type Edge_Array is array (Positive range <>) of Edge_Type; @@ -87,7 +93,7 @@ package Directed_Graphs is function Element (Position : in Cursor) - return Node_Type; + return Extended_Node_ID_Type; package Graph_Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element); @@ -105,7 +111,7 @@ package Directed_Graphs is function To_Cursor (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Cursor; @@ -143,6 +149,10 @@ package Directed_Graphs is return Ada.Containers.Count_Type; function Node_Count + (Container : in Cursor) + return Ada.Containers.Count_Type; + + function Node_Count_In_Subgraph (Position : in Cursor) return Ada.Containers.Count_Type; @@ -151,6 +161,10 @@ package Directed_Graphs is return Ada.Containers.Count_Type; function Edge_Count + (Container : in Cursor) + return Ada.Containers.Count_Type; + + function Edge_Count_In_Subgraph (Position : in Cursor) return Ada.Containers.Count_Type; @@ -159,6 +173,10 @@ package Directed_Graphs is return Node_Array; function Nodes + (Container : in Cursor) + return Node_Array; + + function Nodes_In_Subgraph (Position : in Cursor) return Node_Array; @@ -167,15 +185,35 @@ package Directed_Graphs is return Edge_Array; function Edges + (Container : in Cursor) + return Edge_Array; + + function Edges_In_Subgraph (Position : in Cursor) return Edge_Array; procedure Node_Range (Container : in Graph; - Minimum : out Node_Type; - Maximum : out Node_Type); + Minimum : out Node_ID_Type; + Maximum : out Node_ID_Type); + + function Unused + (Container : in Graph) + return Node_ID_Type; + + function Unused + (Container : in Graph) + return Edge_ID_Type; + + function Unused + (Container : in Cursor) + return Node_ID_Type; - function Unused_Nodes + function Unused + (Container : in Cursor) + return Edge_ID_Type; + + function Unused (Container : in Graph; Count : in Positive := 1) return Node_Array; @@ -185,14 +223,23 @@ package Directed_Graphs is procedure Insert (Container : in out Graph; - Node : in Node_Type); + Node : in Node_ID_Type); procedure Insert (Container : in out Graph; - Node : in Node_Type; + Node : in Node_ID_Type; Label : in Node_Label_Type); procedure Insert + (Container : in Cursor; + Node : in Node_ID_Type); + + procedure Insert + (Container : in Cursor; + Node : in Node_ID_Type; + Label : in Node_Label_Type); + + procedure Insert (Container : in out Graph; Nodes : in Node_Array); @@ -206,28 +253,21 @@ package Directed_Graphs is Label : in Edge_Label_Type); procedure Insert - (Parent, Child : in out Cursor); + (Container : in Cursor; + Edge : in Edge_Type); procedure Insert - (Parent, Child : in out Cursor; - Label : in Edge_Label_Type); + (Container : in Cursor; + Edge : in Edge_Type; + Label : in Edge_Label_Type); procedure Insert (Container : in out Graph; Edges : in Edge_Array); - procedure Append - (Container : in out Graph; - Position : out Cursor); - - procedure Append - (Container : in out Graph; - Label : in Node_Label_Type; - Position : out Cursor); - procedure Delete (Container : in out Graph; - Node : in Node_Type); + Node : in Node_ID_Type); procedure Delete (Position : in out Cursor); @@ -241,7 +281,8 @@ package Directed_Graphs is Edge : in Edge_Type); procedure Delete - (Parent, Child : in out Cursor); + (Container : in Cursor; + Edge : in Edge_Type); procedure Delete (Container : in out Graph; @@ -249,12 +290,12 @@ package Directed_Graphs is procedure Append_Label (Container : in out Graph; - Node : in Node_Type; + Node : in Node_ID_Type; Label : in Node_Label_Type); procedure Append_Label - (Position : in out Cursor; - Label : in Node_Label_Type); + (Position : in Cursor; + Label : in Node_Label_Type); procedure Append_Label (Container : in out Graph; @@ -262,17 +303,18 @@ package Directed_Graphs is Label : in Edge_Label_Type); procedure Append_Label - (Parent, Child : in out Cursor; - Label : in Edge_Label_Type); + (Container : in Cursor; + Edge : in Edge_Type; + Label : in Edge_Label_Type); procedure Replace_Label (Container : in out Graph; - Node : in Node_Type; + Node : in Node_ID_Type; Label : in Node_Label_Type); procedure Replace_Label - (Position : in out Cursor; - Label : in Node_Label_Type); + (Position : in Cursor; + Label : in Node_Label_Type); procedure Replace_Label (Container : in out Graph; @@ -280,29 +322,31 @@ package Directed_Graphs is Label : in Edge_Label_Type); procedure Replace_Label - (Parent, Child : in out Cursor; - Label : in Edge_Label_Type); + (Container : in Cursor; + Edge : in Edge_Type; + Label : in Edge_Label_Type); procedure Delete_Label (Container : in out Graph; - Node : in Node_Type); + Node : in Node_ID_Type); procedure Delete_Label - (Position : in out Cursor); + (Position : in Cursor); procedure Delete_Label (Container : in out Graph; Edge : in Edge_Type); procedure Delete_Label - (Parent, Child : in out Cursor); + (Container : in Cursor; + Edge : in Edge_Type); procedure Delete_Subgraph (Position : in out Cursor); procedure Swap (Container : in out Graph; - Left, Right : in Node_Type); + Left, Right : in Node_ID_Type); procedure Swap (Left, Right : in out Cursor); @@ -316,7 +360,7 @@ package Directed_Graphs is function Constant_Label_Reference (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Node_Label_Constant_Reference; function Constant_Label_Reference @@ -329,7 +373,7 @@ package Directed_Graphs is function Label_Reference (Container : aliased in out Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Node_Label_Reference; function Label_Reference @@ -346,7 +390,8 @@ package Directed_Graphs is return Edge_Label_Constant_Reference; function Constant_Label_Reference - (Parent, Child : in Cursor) + (Container : in Cursor; + Edge : in Edge_Type) return Edge_Label_Constant_Reference; type Edge_Label_Reference @@ -359,7 +404,8 @@ package Directed_Graphs is return Edge_Label_Reference; function Label_Reference - (Parent, Child : in Cursor) + (Container : in Cursor; + Edge : in Edge_Type) return Edge_Label_Reference; @@ -367,7 +413,7 @@ package Directed_Graphs is function Has_Label (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Boolean; function Has_Label @@ -380,12 +426,13 @@ package Directed_Graphs is return Boolean; function Has_Label - (Parent, Child : in Cursor) + (Container : in Cursor; + Edge : in Edge_Type) return Boolean; function Label (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Node_Label_Type; function Label @@ -398,12 +445,13 @@ package Directed_Graphs is return Edge_Label_Type; function Label - (Parent, Child : in Cursor) + (Container : in Cursor; + Edge : in Edge_Type) return Edge_Label_Type; function Neighbors (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Node_Array; function Neighbors @@ -412,7 +460,7 @@ package Directed_Graphs is function Parents (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Node_Array; function Parents @@ -421,7 +469,7 @@ package Directed_Graphs is function Children (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Node_Array; function Children @@ -430,7 +478,7 @@ package Directed_Graphs is function Outbound (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Edge_Array; function Outbound @@ -439,16 +487,25 @@ package Directed_Graphs is function Inbound (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Edge_Array; function Inbound (Position : in Cursor) return Edge_Array; + function Between + (Container : in Graph; + Parent, Child : in Node_ID_Type) + return Edge_Array; + + function Between + (Parent, Child : in Cursor) + return Edge_Array; + function Outdegree (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Ada.Containers.Count_Type; function Outdegree @@ -457,7 +514,7 @@ package Directed_Graphs is function Indegree (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Ada.Containers.Count_Type; function Indegree @@ -466,7 +523,7 @@ package Directed_Graphs is function Degree (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Ada.Containers.Count_Type; function Degree @@ -475,7 +532,7 @@ package Directed_Graphs is function Has_Edge (Container : in Graph; - Parent, Child : in Node_Type) + Parent, Child : in Node_ID_Type) return Boolean; function Has_Edge @@ -484,7 +541,7 @@ package Directed_Graphs is function Has_Labeled_Edge (Container : in Graph; - Parent, Child : Node_Type) + Parent, Child : in Node_ID_Type) return Boolean; function Has_Labeled_Edge @@ -493,7 +550,7 @@ package Directed_Graphs is function Has_Neighbor (Container : in Graph; - Left, Right : in Node_Type) + Left, Right : in Node_ID_Type) return Boolean; function Has_Neighbor @@ -525,17 +582,22 @@ package Directed_Graphs is function Contains (Container : in Graph; - Node : in Node_Type) + Node : in Node_ID_Type) return Boolean; function Contains (Container : in Graph; - Node : in Node_Type; + Node : in Node_ID_Type; Label : in Node_Label_Type) return Boolean; function Contains (Container : in Graph; + Edge_ID : in Edge_ID_Type) + return Boolean; + + function Contains + (Container : in Graph; Edge : in Edge_Type) return Boolean; @@ -557,17 +619,22 @@ package Directed_Graphs is function Contains_In_Subgraph (Position : in Cursor; - Node : in Node_Type) + Node : in Node_ID_Type) return Boolean; function Contains_In_Subgraph (Position : in Cursor; - Node : in Node_Type; + Node : in Node_ID_Type; Label : in Node_Label_Type) return Boolean; function Contains_In_Subgraph (Position : in Cursor; + Edge_ID : in Edge_ID_Type) + return Boolean; + + function Contains_In_Subgraph + (Position : in Cursor; Edge : in Edge_Type) return Boolean; @@ -590,13 +657,13 @@ package Directed_Graphs is - -- Iterates through all Nodes in the Graph in order of Node_Type. + -- Iterates through all Nodes in the Graph in order of Node_ID_Type. function Iterate (Container : in Graph) return Graph_Iterator_Interfaces.Reversible_Iterator'Class; -- Iterates through all reachable Nodes in the subgraph in order - -- of Node_Type. Note that this is NOT the same as the order of + -- of Node_ID_Type. Note that this is NOT the same as the order of -- either breadth first or depth first search. function Iterate_Subgraph (Container : in Graph; @@ -632,7 +699,7 @@ package Directed_Graphs is function Cursor_To (Position : in Cursor; - Node : in Node_Type) + Node : in Node_ID_Type) return Cursor; @@ -665,26 +732,35 @@ private package Streams renames Ada.Streams; + type Node_Adj is record + Edge_ID : Edge_ID_Type; + Node_ID : Node_ID_Type; + end record; + package Node_Vectors is new Ada.Containers.Vectors (Index_Type => Positive, - Element_Type => Node_Type); - - use type Node_Vectors.Vector; - use type Ada.Containers.Count_Type; + Element_Type => Node_ID_Type); - package Node_Sort is new Node_Vectors.Generic_Sorting; + package Adj_Vectors is new Ada.Containers.Vectors + (Index_Type => Positive, + Element_Type => Node_Adj); package Edge_Vectors is new Ada.Containers.Vectors (Index_Type => Positive, Element_Type => Edge_Type); + use type Node_Vectors.Vector; + use type Adj_Vectors.Vector; + use type Ada.Containers.Count_Type; + + package Node_Sort is new Node_Vectors.Generic_Sorting; + package Node_Maps is new Ada.Containers.Ordered_Maps - (Key_Type => Node_Type, - Element_Type => Node_Vectors.Vector, - "=" => Node_Vectors."="); + (Key_Type => Node_ID_Type, + Element_Type => Adj_Vectors.Vector); package Node_Label_Maps is new Ada.Containers.Ordered_Maps - (Key_Type => Node_Type, + (Key_Type => Node_ID_Type, Element_Type => Node_Label_Type); package Edge_Label_Maps is new Ada.Containers.Ordered_Maps |