diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/ada-containers-directed_graphs.ads | 508 |
1 files changed, 490 insertions, 18 deletions
diff --git a/src/ada-containers-directed_graphs.ads b/src/ada-containers-directed_graphs.ads index 6d0a2b0..e383c0c 100644 --- a/src/ada-containers-directed_graphs.ads +++ b/src/ada-containers-directed_graphs.ads @@ -13,52 +13,524 @@ private with generic - with Node_Type is (<>); - with Node_Array_Type is array (Positive) of Node_Type; - with Node_Label_Type is private; - with Edge_Label_Type is private; + type Node_Type is (<>); + type Node_Array is array (Positive) of Node_Type; + + type Node_Label_Type is private; + type Edge_Label_Type is private; package Ada.Containers.Directed_Graphs is + subtype Path is Node_Array; + subtype Extended_Node_Type is Node_Type'Base range Node_Type'First - 1 .. Node_Type'Min (Node_Type'Base'Last - 1, Node_Type'Last) + 1; - subtype Path is Node_Array_Type; + No_Node : constant Extended_Node_Type := Extended_Node_Type'First; + + + type Edge_Type is record From : Node_Type; To : Node_Type; end record; - type Edge_Array_Type is array (Positive) of Edge_Type; + type Edge_Array is array (Positive) of Edge_Type; + + + type Graph is tagged private; type Cursor is private; + No_Element : constant Cursor; + + function Has_Element + (Position : in Cursor) + return Boolean; + + package Graph_Iterator_Interfaces is new + Ada.Iterator_Interfaces (Cursor, Has_Element); + + Empty_Graph : constant Graph; + + overriding function "=" + (Left, Right : in Graph) + return Boolean; + + function To_Graph + (Nodes : in Node_Array; + Edges : in Edge_Array) + return Graph; + + function To_Cursor + (Container : in Graph; + Node : in Node_Type) + return Cursor; + + + + + procedure Assign + (Target : in out Graph; + Source : in Graph); + + function Copy + (Source : in Graph) + return Graph; + + procedure Move + (Target, Source : in out Graph); + + + + + function Is_Empty + (Container : in Graph) + return Boolean; + + procedure Clear + (Container : in out Graph); + + procedure Clear_Labels + (Container : in out Graph); + + + + + function Node_Count + (Container : in Graph) + return Count_Type; + + function Edge_Count + (Container : in Graph) + return Count_Type; + + function Nodes + (Container : in Graph) + return Node_Array; + + function Edges + (Container : in Graph) + return Edge_Array; + + procedure Node_Range + (Container : in Graph; + Minimum : out Node; + Maximum : out Node); + + function Unused_Nodes + (Container : in Graph; + Count : in Positive := 1) + return Node_Array; + + + + + procedure Insert + (Container : in out Graph; + Node : in Node_Type); + + procedure Insert + (Container : in out Graph; + Node : in Node_Type; + Label : in Node_Label_Type); + + procedure Insert + (Container : in out Graph; + Nodes : in Node_Array); + + procedure Insert + (Container : in out Graph; + Edge : in Edge_Type); + + procedure Insert + (Container : in out Graph; + 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); + + procedure Delete + (Position : in out Cursor); + + procedure Delete + (Container : in out Graph; + Nodes : in Node_Array); + + procedure Delete + (Container : in out Graph; + Edge : in Edge_Type); + + procedure Delete + (Container : in out Graph; + Edges : in Edge_Array); + + procedure Append_Label + (Container : in out Graph; + Node : in Node_Type; + Label : in Node_Label_Type); + + procedure Append_Label + (Position : in out Cursor; + Label : in Node_Label_Type); + + procedure Append_Label + (Container : in out Graph; + Edge : in Edge_Type; + Label : in Edge_Label_Type); + + procedure Replace_Label + (Container : in out Graph; + Node : in Node_Type; + Label : in Node_Label_Type); + + procedure Replace_Label + (Position : in out Cursor; + Label : in Node_Label_Type); + + procedure Replace_Label + (Container : in out Graph; + Edge : in Edge_Type; + Label : in Edge_Label_Type); + + procedure Delete_Label + (Container : in out Graph; + Node : in Node_Type); + + procedure Delete_Label + (Position : in out Cursor); + + procedure Delete_Label + (Container : in out Graph; + Edge : in Edge_Type); + + procedure Delete_Subgraph + (Position : in out Cursor); + + procedure Swap + (Container : in out Graph; + Left, Right : in Node_Type); + + procedure Swap + (Left, Right : in out Cursor); - type Node_Label_Constant_Reference_Type + + procedure Context + (Container : in Graph; + Node : in Node_Type; + Parents : out Node_Array; + Children : out Node_Array); + + procedure Context + (Position : in Cursor; + Parents : out Node_Array; + Children : out Node_Array); + + procedure Labeled_Context + (Container : in Graph; + Node : in Node_Type; + Parents : out Node_Array; + Children : out Node_Array; + Label : out Node_Label_Type); + + procedure Labeled_Context + (Position : in Cursor; + Parents : out Node_Array; + Children : out Node_Array; + Label : out Node_Label_Type); + + function Has_Label + (Container : in Graph; + Node : in Node_Type) + return Boolean; + + function Has_Label + (Position : in Cursor) + return Boolean; + + function Has_Label + (Container : in Graph; + Edge : in Edge_Type) + return Boolean; + + function Label + (Container : in Graph; + Node : in Node_Type) + return Node_Label_Type; + + function Label + (Position : in Cursor) + return Node_Label_Type; + + function Label + (Container : in Graph; + Edge : in Edge_Type) + return Edge_Label_Type; + + type Node_Label_Constant_Reference (Element : not null access constant Node_Label_Type) is private - with - Implicit_Dereference => Element; + with Implicit_Dereference => Element; + + function Constant_Label_Reference + (Container : in Graph; + Node : in Node_Type) + return Node_Label_Constant_Reference; - type Node_Label_Reference_Type (Element : not null access Node_Label_Type) is private - with - Implicit_Dereference => Element; + function Constant_Label_Reference + (Position : in Cursor) + return Node_Label_Constant_Reference; - type Edge_Label_Constant_Reference_Type + type Node_Label_Reference + (Element : not null access Node_Label_Type) is private + with Implicit_Dereference => Element; + + function Label_Reference + (Container : in Graph; + Node : in Node_Type) + return Node_Label_Reference; + + function Label_Reference + (Position : in Cursor) + return Node_Label_Reference; + + type Edge_Label_Constant_Reference (Element : not null access constant Edge_Label_Type) is private - with - Implicit_Dereference => Element; + with Implicit_Dereference => Element; + + function Constant_Label_Reference + (Container : in Graph; + Edge : in Edge_Type) + return Edge_Label_Constant_Reference; + + type Edge_Label_Reference + (Element : not null access Edge_Label_Type) is private + with Implicit_Dereference => Element; + + function Label_Reference + (Container : in Graph; + Edge : in Edge_Type) + return Edge_Label_Reference; + + function Neighbors + (Container : in Graph; + Node : in Node_Type) + return Node_Array; + + function Neighbors + (Position : in Cursor) + return Node_Array; + + function Parents + (Container : in Graph; + Node : in Node_Type) + return Node_Array; + + function Parents + (Position : in Cursor) + return Node_Array; + + function Children + (Container : in Graph; + Node : in Node_Type) + return Node_Array; + + function Children + (Position : in Cursor) + return Node_Array; + + function Outbound + (Container : in Graph; + Node : in Node_Type) + return Edge_Array; + + function Outbound + (Position : in Cursor) + return Edge_Array; + + function Inbound + (Container : in Graph; + Node : in Node_Type) + return Edge_Array; + + function Inbound + (Position : in Cursor) + return Edge_Array; + + function Outdegree + (Container : in Graph; + Node : in Node_Type) + return Count_Type; + + function Outdegree + (Position : in Cursor) + return Count_Type; + + function Indegree + (Container : in Graph; + Node : in Node_Type) + return Count_Type; + + function Indegree + (Position : in Cursor) + return Count_Type; + + function Degree + (Container : in Graph; + Node : in Node_Type) + return Count_Type; + + function Degree + (Position : in Cursor) + return Count_Type; + + function Has_Edge + (Container : in Graph; + Parent, Child : in Node_Type) + return Boolean; + + function Has_Edge + (Parent, Child : in Cursor) + return Boolean; + + function Has_Labeled_Edge + (Container : in Graph; + Parent, Child : Node_Type) + return Boolean; + + function Has_Labeled_Edge + (Parent, Child : in Cursor) + return Boolean; + + function Has_Neighbor + (Container : in Graph; + Left, Right : in Node_Type) + return Boolean; + + function Has_Neighbor + (Left, Right : in Cursor) + return Boolean; + + + + + function Find + (Container : in Graph; + Label : in Node_Label_Type) + return Node_Array; + + function Find + (Container : in Graph; + Label : in Edge_Label_Type) + return Edge_Array; + + function Find_In_Subgraph + (Position : in Cursor; + Label : in Node_Label_Type) + return Node_Array; + + function Find_In_Subgraph + (Position : in Cursor; + Label : in Edge_Label_Type) + return Edge_Array; + + function Contains + (Container : in Graph; + Node : in Node_Type) + return Boolean; + + function Contains + (Container : in Graph; + Node : in Node_Type; + Label : in Node_Label_Type) + return Boolean; + + function Contains + (Container : in Graph; + Edge : in Edge_Type) + return Boolean; + + function Contains + (Container : in Graph; + Edge : in Edge_Type; + Label : in Edge_Label_Type) + return Boolean; + + function Contains_Label + (Container : in Graph; + Label : in Node_Label_Type) + return Boolean; + + function Contains_Label + (Container : in Graph; + Label : in Edge_Label_Type) + return Boolean; + + function Contains_In_Subgraph + (Position : in Cursor; + Node : in Node_Type) + return Boolean; + + function Contains_In_Subgraph + (Position : in Cursor; + Node : in Node_Type; + Label : in Node_Label_Type) + return Boolean; + + function Contains_In_Subgraph + (Position : in Cursor; + Edge : in Edge_Type) + return Boolean; + + function Contains_In_Subgraph + (Position : in Cursor; + Edge : in Edge_Type; + Label : in Edge_Label_Type) + return Boolean; + + function Contains_Label_In_Subgraph + (Position : in Cursor; + Label : in Node_Label_Type) + return Boolean; + + function Contains_Label_In_Subgraph + (Position : in Cursor; + Label : in Edge_Label_Type) + return Boolean; + + + + + function Iterate + (Container : in Graph) + return Graph_Iterator_Interfaces.Reversible_Iterator'Class; - type Edge_Label_Reference_Type (Element : not null access Edge_Label_Type) is private - with - Implicit_Dereference => Element; + function Iterate_Subgraph + (Container : in Graph; + Position : in Cursor) + return Graph_Iterator_Interfaces.Forward_Iterator'Class; private |