summaryrefslogtreecommitdiff
path: root/src/directed_graphs.ads
diff options
context:
space:
mode:
authorJed Barber <jjbarber@y7mail.com>2020-05-27 17:51:42 +1000
committerJed Barber <jjbarber@y7mail.com>2020-05-27 17:51:42 +1000
commit56947ad5bbf0df7d35111010d0d5b7b3c19329cf (patch)
tree86a87e847aba9f4bb4a4cc3bd1c5e3e21afd3e66 /src/directed_graphs.ads
parent7f56d08907ffdd192f4b4898bfb22c1dce8f1cd0 (diff)
Removed Follow, Path; Added LNode, LEdge, Node_Path, Edge_Path, Contains functions for PathsHEADmaster
Diffstat (limited to 'src/directed_graphs.ads')
-rw-r--r--src/directed_graphs.ads101
1 files changed, 77 insertions, 24 deletions
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,8 +259,7 @@ 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;
@@ -245,12 +267,15 @@ package Directed_Graphs is
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)