From 56947ad5bbf0df7d35111010d0d5b7b3c19329cf Mon Sep 17 00:00:00 2001 From: Jed Barber Date: Wed, 27 May 2020 17:51:42 +1000 Subject: Removed Follow, Path; Added LNode, LEdge, Node_Path, Edge_Path, Contains functions for Paths --- src/directed_graphs.ads | 101 ++++++++++++++++++++++++++++++++++++------------ 1 file changed, 77 insertions(+), 24 deletions(-) (limited to 'src/directed_graphs.ads') diff --git a/src/directed_graphs.ads b/src/directed_graphs.ads index 3154f75..8be31a3 100644 --- a/src/directed_graphs.ads +++ b/src/directed_graphs.ads @@ -56,11 +56,18 @@ package Directed_Graphs is subtype Extended_Node_ID_Type is Node_ID_Type'Base range Node_ID_Type'Pred (Node_ID_Type'First) .. Node_ID_Type'Last; + type Labeled_Node_Type is record + Node : Node_ID_Type; + Label : Node_Label_Type; + end record; + No_Node : constant Extended_Node_ID_Type := Extended_Node_ID_Type'First; type Node_Array is array (Positive range <>) of Node_ID_Type; - subtype Path is Node_Array; + type Labeled_Node_Array is array (Positive range <>) of Labeled_Node_Type; + + subtype Node_Path is Node_Array; @@ -71,8 +78,20 @@ package Directed_Graphs is To : Node_ID_Type; end record; + type Labeled_Edge_Type is record + Edge : Edge_Type; + Label : Edge_Label_Type; + end record; + type Edge_Array is array (Positive range <>) of Edge_Type; + type Labeled_Edge_Array is array (Positive range <>) of Labeled_Edge_Type; + + subtype Edge_Path is Edge_Array + with Dynamic_Predicate => + (for all Index in Edge_Path'First .. Edge_Path'Last - 1 => + Edge_Path (Index).To = Edge_Path (Index + 1).From); + function "<" (Left, Right : in Edge_Type) return Boolean; @@ -109,6 +128,11 @@ package Directed_Graphs is Edges : in Edge_Array) return Graph; + function To_Graph + (LNodes : in Labeled_Node_Array; + LEdges : in Labeled_Edge_Array) + return Graph; + function To_Cursor (Container : in Graph; Node : in Node_ID_Type) @@ -227,8 +251,7 @@ package Directed_Graphs is procedure Insert (Container : in out Graph; - Node : in Node_ID_Type; - Label : in Node_Label_Type); + LNode : in Labeled_Node_Type); procedure Insert (Container : in Cursor; @@ -236,21 +259,23 @@ package Directed_Graphs is procedure Insert (Container : in Cursor; - Node : in Node_ID_Type; - Label : in Node_Label_Type); + LNode : in Labeled_Node_Type); procedure Insert (Container : in out Graph; Nodes : in Node_Array); + procedure Insert + (Container : in out Graph; + LNodes : in Labeled_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); + LEdge : in Labeled_Edge_Type); procedure Insert (Container : in Cursor; @@ -258,13 +283,16 @@ package Directed_Graphs is procedure Insert (Container : in Cursor; - Edge : in Edge_Type; - Label : in Edge_Label_Type); + LEdge : in Labeled_Edge_Type); procedure Insert (Container : in out Graph; Edges : in Edge_Array); + procedure Insert + (Container : in out Graph; + LEdges : in Labeled_Edge_Array); + procedure Delete (Container : in out Graph; Node : in Node_ID_Type); @@ -582,13 +610,12 @@ package Directed_Graphs is function Contains (Container : in Graph; - Node : in Extended_Node_ID_Type) + Node : in Node_ID_Type) return Boolean; function Contains (Container : in Graph; - Node : in Extended_Node_ID_Type; - Label : in Node_Label_Type) + LNode : in Labeled_Node_Type) return Boolean; function Contains @@ -603,8 +630,7 @@ package Directed_Graphs is function Contains (Container : in Graph; - Edge : in Edge_Type; - Label : in Edge_Label_Type) + LEdge : in Labeled_Edge_Type) return Boolean; function Contains_Label @@ -619,13 +645,12 @@ package Directed_Graphs is function Contains_In_Subgraph (Position : in Cursor; - Node : in Extended_Node_ID_Type) + Node : in Node_ID_Type) return Boolean; function Contains_In_Subgraph (Position : in Cursor; - Node : in Extended_Node_ID_Type; - Label : in Node_Label_Type) + LNode : in Labeled_Node_Type) return Boolean; function Contains_In_Subgraph @@ -640,8 +665,7 @@ package Directed_Graphs is function Contains_In_Subgraph (Position : in Cursor; - Edge : in Edge_Type; - Label : in Edge_Label_Type) + LEdge : in Labeled_Edge_Type) return Boolean; function Contains_Label_In_Subgraph @@ -654,6 +678,36 @@ package Directed_Graphs is Label : in Edge_Label_Type) return Boolean; + function Contains_Path + (Container : in Graph; + Path : in Node_Path) + return Boolean; + + function Contains_Path + (Container : in Cursor; + Path : in Node_Path) + return Boolean; + + function Contains_Path + (Container : in Graph; + Path : in Edge_Path) + return Boolean; + + function Contains_Path + (Container : in Cursor; + Path : in Edge_Path) + return Boolean; + + function Contains_Path_In_Subgraph + (Position : in Cursor; + Path : in Node_Path) + return Boolean; + + function Contains_Path_In_Subgraph + (Position : in Cursor; + Path : in Edge_Path) + return Boolean; + @@ -678,6 +732,10 @@ package Directed_Graphs is (Position : in Cursor) return Boolean; + -- This will continue iterating until the Choice_Function returns a + -- No_Element Cursor, and any Cursors that the Filter_Function returns + -- False for are skipped over, so this can easily lead to infinite loops. + -- Be careful of which functions you select. function Iterate_By (Container : in Graph; Start : in Cursor; @@ -707,11 +765,6 @@ package Directed_Graphs is procedure Previous (Position : in out Cursor); - function Follow - (Position : in Cursor; - Edge : in Edge_Type) - return Cursor; - function Cursor_To (Position : in Cursor; Node : in Node_ID_Type) -- cgit