diff options
Diffstat (limited to 'src/directed_graphs.ads')
| -rw-r--r-- | src/directed_graphs.ads | 234 |
1 files changed, 155 insertions, 79 deletions
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 |