diff options
| -rw-r--r-- | design_notes.txt | 18 | ||||
| -rw-r--r-- | src/ada-containers-directed_graphs.ads | 508 |
2 files changed, 500 insertions, 26 deletions
diff --git a/design_notes.txt b/design_notes.txt index 08993b8..700ed9d 100644 --- a/design_notes.txt +++ b/design_notes.txt @@ -20,14 +20,14 @@ Ada.Containers.Directed_Graphs List of types: Extended_Node_Type Edge_Type - Edge_Array_Type + Edge_Array Path (derived from the node array type) Graph Cursor - Node_Label_Reference_Type - Constant_Node_Label_Reference_Type - Edge_Label_Reference_Type - Constant_Edge_Label_Reference_Type + Node_Label_Reference + Constant_Node_Label_Reference + Edge_Label_Reference + Constant_Edge_Label_Reference Constants: No_Node (of Extended_Node_Type) @@ -45,6 +45,8 @@ List of Cursor funcs: List of Graph funcs: "=" + To_Graph + To_Cursor Assign Copy @@ -53,11 +55,9 @@ List of Graph funcs: Is_Empty Clear Clear_Labels - To_Cursor (node -> cursor) Node_Count (a measure of number of nodes in the graph) Edge_Count (a measure of number of edges in the graph) - Nodes (array of all nodes in the graph) Edges (array of all edges in the graph) Node_Range (returns minimum and maximum of nodes in the graph) @@ -90,10 +90,12 @@ List of Graph funcs: Has_Labeled_Edge (check whether two nodes are connected with a labeled edge) Has_Neighbor (check whether two nodes are neighbors) - Find (find a node or edge with a particular label) + Find (find nodes or edges with a particular label) Find_In_Subgraph Contains (check whether a node or an edge is in the graph) Contains_Label (check if graph contains a particular node/edge label) + Contains_In_Subgraph + Contains_Label_In_Subgraph Iterate Iterate_Subgraph 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 |