diff options
| -rw-r--r-- | src/directed_graphs.adb | 299 | ||||
| -rw-r--r-- | src/directed_graphs.ads | 101 | ||||
| -rw-r--r-- | test/graph_tests-curses.adb | 13 | ||||
| -rw-r--r-- | test/graph_tests-curses.ads | 2 | ||||
| -rw-r--r-- | test/graph_tests-modify.adb | 4 | ||||
| -rw-r--r-- | test/graph_tests-search.adb | 83 | ||||
| -rw-r--r-- | test/graph_tests-search.ads | 4 | ||||
| -rw-r--r-- | tests.gpr | 2 |
8 files changed, 375 insertions, 133 deletions
diff --git a/src/directed_graphs.adb b/src/directed_graphs.adb index bacb040..d7185e4 100644 --- a/src/directed_graphs.adb +++ b/src/directed_graphs.adb @@ -370,27 +370,20 @@ package body Directed_Graphs is function Contains (Container : in Graph; - Node : in Extended_Node_ID_Type) + Node : in Node_ID_Type) return Boolean is begin - if Node = No_Node then - return False; - end if; return Container.Connections.Contains (Node); end Contains; function Contains (Container : in Graph; - Node : in Extended_Node_ID_Type; - Label : in Node_Label_Type) + LNode : in Labeled_Node_Type) return Boolean is begin - if Node = No_Node then - return False; - end if; - return Container.Contains (Node) and then - Container.Node_Labels.Contains (Node) and then - Container.Node_Labels.Constant_Reference (Node) = Label; + return Container.Contains (LNode.Node) and then + Container.Node_Labels.Contains (LNode.Node) and then + Container.Node_Labels.Constant_Reference (LNode.Node) = LNode.Label; end Contains; function Contains @@ -420,13 +413,12 @@ package body Directed_Graphs is function Contains (Container : in Graph; - Edge : in Edge_Type; - Label : in Edge_Label_Type) + LEdge : in Labeled_Edge_Type) return Boolean is begin - return Container.Contains (Edge) and then - Container.Edge_Labels.Contains (Edge) and then - Container.Edge_Labels.Constant_Reference (Edge) = Label; + return Container.Contains (LEdge.Edge) and then + Container.Edge_Labels.Contains (LEdge.Edge) and then + Container.Edge_Labels.Constant_Reference (LEdge.Edge) = LEdge.Label; end Contains; @@ -438,10 +430,10 @@ package body Directed_Graphs is function Contains_In_Subgraph (Position : in Cursor; - Node : in Extended_Node_ID_Type) + Node : in Node_ID_Type) return Boolean is begin - if Position.Container = null or Node = No_Node then + if Position.Container = null then return False; end if; for C in Position.Container.Iterate_Subgraph (Position) loop @@ -454,16 +446,15 @@ package body Directed_Graphs is 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 is begin - if Position.Container = null or Node = No_Node then + if Position.Container = null then return False; end if; - return Contains_In_Subgraph (Position, Node) and then - Position.Container.Has_Label (Node) and then - Position.Container.Constant_Label_Reference (Node) = Label; + return Contains_In_Subgraph (Position, LNode.Node) and then + Position.Container.Has_Label (LNode.Node) and then + Position.Container.Constant_Label_Reference (LNode.Node) = LNode.Label; end Contains_In_Subgraph; function Contains_In_Subgraph @@ -504,8 +495,7 @@ package body 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 is Parent_Check, Child_Check : Boolean := False; @@ -513,9 +503,9 @@ package body Directed_Graphs is if Position.Container = null then return False; end if; - return Contains_In_Subgraph (Position, Edge) and then - Position.Container.Has_Label (Edge) and then - Position.Container.Constant_Label_Reference (Edge) = Label; + return Contains_In_Subgraph (Position, LEdge.Edge) and then + Position.Container.Has_Label (LEdge.Edge) and then + Position.Container.Constant_Label_Reference (LEdge.Edge) = LEdge.Label; end Contains_In_Subgraph; @@ -609,6 +599,144 @@ package body Directed_Graphs is + ------------------- + -- Contains_Path -- + ------------------- + + function Contains_Path + (Container : in Graph; + Path : in Node_Path) + return Boolean is + begin + for Node of Path loop + if not Container.Contains (Node) then + return False; + end if; + end loop; + for Index in Path'First .. Path'Last - 1 loop + if not Container.Has_Edge (Path (Index), Path (Index + 1)) then + return False; + end if; + end loop; + return True; + end Contains_Path; + + function Contains_Path + (Container : in Cursor; + Path : in Node_Path) + return Boolean is + begin + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + return Container.Container.Contains_Path (Path); + end Contains_Path; + + function Contains_Path + (Container : in Graph; + Path : in Edge_Path) + return Boolean is + begin + for Edge of Path loop + if not Container.Contains (Edge) then + return False; + end if; + end loop; + for Index in Path'First .. Path'Last - 1 loop + if Path (Index).To /= Path (Index + 1).From then + return False; + end if; + end loop; + return True; + end Contains_Path; + + function Contains_Path + (Container : in Cursor; + Path : in Edge_Path) + return Boolean is + begin + if Impl.Checks and then Container.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + return Container.Container.Contains_Path (Path); + end Contains_Path; + + + + + ------------------------------- + -- Contains_Path_In_Subgraph -- + ------------------------------- + + function Contains_Path_In_Subgraph + (Position : in Cursor; + Path : in Node_Path) + return Boolean is + begin + if Impl.Checks and then Position.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + declare + Node_List : Node_Array := Nodes_In_Subgraph (Position); + Has_Node : Boolean; + begin + for Node of Path loop + Has_Node := False; + for Subgraph_Node of Node_List loop + if Node = Subgraph_Node then + Has_Node := True; + exit; + end if; + end loop; + if not Has_Node then + return False; + end if; + end loop; + for Index in Path'First .. Path'Last - 1 loop + if not Position.Container.Has_Edge (Path (Index), Path (Index + 1)) then + return False; + end if; + end loop; + return True; + end; + end Contains_Path_In_Subgraph; + + function Contains_Path_In_Subgraph + (Position : in Cursor; + Path : in Edge_Path) + return Boolean is + begin + if Impl.Checks and then Position.Container = null then + raise Constraint_Error with "Graph does not exist"; + end if; + declare + Edge_List : Edge_Array := Edges_In_Subgraph (Position); + Has_Edge : Boolean; + begin + for Edge of Path loop + Has_Edge := False; + for Subgraph_Edge of Edge_List loop + if Edge = Subgraph_Edge then + Has_Edge := True; + exit; + end if; + end loop; + if not Has_Edge then + return False; + end if; + end loop; + for Index in Path'First .. Path'Last - 1 loop + if Path (Index).To /= Path (Index + 1).From then + return False; + end if; + end loop; + return True; + end; + end Contains_Path_In_Subgraph; + + + + ---------- -- Copy -- ---------- @@ -1183,32 +1311,6 @@ package body Directed_Graphs is - ------------ - -- Follow -- - ------------ - - function Follow - (Position : in Cursor; - Edge : in Edge_Type) - return Cursor is - begin - if Impl.Checks then - if Position.Container = null then - raise Constraint_Error with "Graph does not exist"; - end if; - if not Has_Element (Position) then - raise Constraint_Error with "Cursor points to nothing"; - end if; - if Element (Position) /= Edge.From then - raise Constraint_Error with "Cursor is not at tail of edge"; - end if; - end if; - return Position.Container.To_Cursor (Edge.To); - end Follow; - - - - -------------- -- Has_Edge -- -------------- @@ -1519,11 +1621,10 @@ package body Directed_Graphs is procedure Insert (Container : in out Graph; - Node : in Node_ID_Type; - Label : in Node_Label_Type) is + LNode : in Labeled_Node_Type) is begin - Container.Insert (Node); - Container.Node_Labels.Insert (Node, Label); + Container.Insert (LNode.Node); + Container.Node_Labels.Insert (LNode.Node, LNode.Label); end Insert; procedure Insert @@ -1538,13 +1639,12 @@ package body Directed_Graphs is procedure Insert (Container : in Cursor; - Node : in Node_ID_Type; - Label : in Node_Label_Type) is + LNode : in Labeled_Node_Type) is begin if Impl.Checks and then Container.Container = null then raise Constraint_Error with "Graph does not exist"; end if; - Container.Container.Insert (Node, Label); + Container.Container.Insert (Labeled_Node_Type'(LNode.Node, LNode.Label)); end Insert; procedure Insert @@ -1558,6 +1658,15 @@ package body Directed_Graphs is procedure Insert (Container : in out Graph; + LNodes : in Labeled_Node_Array) is + begin + for N of LNodes loop + Container.Insert (N); + end loop; + end Insert; + + procedure Insert + (Container : in out Graph; Edge : in Edge_Type) is begin if Impl.Checks then @@ -1574,11 +1683,10 @@ package body Directed_Graphs is procedure Insert (Container : in out Graph; - Edge : in Edge_Type; - Label : in Edge_Label_Type) is + LEdge : in Labeled_Edge_Type) is begin - Container.Insert (Edge); - Container.Edge_Labels.Insert (Edge, Label); + Container.Insert (LEdge.Edge); + Container.Edge_Labels.Insert (LEdge.Edge, LEdge.Label); end Insert; procedure Insert @@ -1593,13 +1701,12 @@ package body Directed_Graphs is procedure Insert (Container : in Cursor; - Edge : in Edge_Type; - Label : in Edge_Label_Type) is + LEdge : in Labeled_Edge_Type) is begin if Impl.Checks and then Container.Container = null then raise Constraint_Error with "Graph does not exist"; end if; - Container.Container.Insert (Edge, Label); + Container.Container.Insert (Labeled_Edge_Type'(LEdge.Edge, LEdge.Label)); end Insert; procedure Insert @@ -1611,6 +1718,15 @@ package body Directed_Graphs is end loop; end Insert; + procedure Insert + (Container : in out Graph; + LEdges : in Labeled_Edge_Array) is + begin + for E of LEdges loop + Container.Insert (E); + end loop; + end Insert; + @@ -2637,6 +2753,49 @@ package body Directed_Graphs is Connections => Adj_Map, others => <>); end To_Graph; + function To_Graph + (LNodes : in Labeled_Node_Array; + LEdges : in Labeled_Edge_Array) + return Graph + is + Adj_Map : Node_Maps.Map; + NLabel_Map : Node_Label_Maps.Map; + ELabel_Map : Edge_Label_Maps.Map; + begin + if LNodes'Length = 0 and LEdges'Length = 0 then + return Empty_Graph; + end if; + + for I in Positive range LNodes'First .. LNodes'Last loop + if Impl.Checks then + for J in Positive range I + 1 .. LNodes'Last loop + if LNodes (I).Node = LNodes (J).Node then + raise Constraint_Error with "Duplicate nodes in node array"; + end if; + end loop; + end if; + Adj_Map.Insert (LNodes (I).Node, Adj_Vectors.Empty_Vector); + NLabel_Map.Insert (LNodes (I).Node, LNodes (I).Label); + end loop; + + for E of LEdges loop + if Impl.Checks and then + (not Adj_Map.Contains (E.Edge.From) or not Adj_Map.Contains (E.Edge.To)) + then + raise Constraint_Error with "Edge uses nodes not in graph"; + end if; + Adj_Map.Reference (E.Edge.From).Append ((E.Edge.ID, E.Edge.To)); + ELabel_Map.Insert (E.Edge, E.Label); + end loop; + + return G : Graph := + (Ada.Finalization.Controlled with + Connections => Adj_Map, + Node_Labels => NLabel_Map, + Edge_Labels => ELabel_Map, + others => <>); + end To_Graph; + 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) diff --git a/test/graph_tests-curses.adb b/test/graph_tests-curses.adb index 3667825..4d32ec1 100644 --- a/test/graph_tests-curses.adb +++ b/test/graph_tests-curses.adb @@ -59,19 +59,6 @@ package body Graph_Tests.Curses is end Previous_Check; - function Follow_Check - return Test_Result - is - use type Graphs.Cursor; - Start : Graphs.Cursor := My_Complex_Graph.To_Cursor (1); - begin - if Graphs.Follow (Start, (1, 1, 2)) /= My_Complex_Graph.To_Cursor (2) then - return Fail; - end if; - return Pass; - end Follow_Check; - - function Cursor_To_Check return Test_Result is diff --git a/test/graph_tests-curses.ads b/test/graph_tests-curses.ads index dff209b..302c7b3 100644 --- a/test/graph_tests-curses.ads +++ b/test/graph_tests-curses.ads @@ -11,7 +11,6 @@ package Graph_Tests.Curses is function Last_Check return Test_Result; function Next_Check return Test_Result; function Previous_Check return Test_Result; - function Follow_Check return Test_Result; function Cursor_To_Check return Test_Result; @@ -20,7 +19,6 @@ package Graph_Tests.Curses is (+"Last", Last_Check'Access), (+"Next", Next_Check'Access), (+"Previous", Previous_Check'Access), - (+"Follow", Follow_Check'Access), (+"Cursor_To", Cursor_To_Check'Access)); diff --git a/test/graph_tests-modify.adb b/test/graph_tests-modify.adb index 0c1d5d9..74f62a9 100644 --- a/test/graph_tests-modify.adb +++ b/test/graph_tests-modify.adb @@ -26,7 +26,7 @@ package body Graph_Tests.Modify is if Copy_Graph.To_Cursor (To_Insert) /= Graphs.No_Element then return Fail; end if; - Copy_Graph.Insert (To_Insert, Node_Label (+"HAHA")); + Copy_Graph.Insert (Graphs.Labeled_Node_Type'(To_Insert, Node_Label (+"HAHA"))); if Copy_Graph.To_Cursor (To_Insert) = Graphs.No_Element or else not Copy_Graph.Has_Label (To_Insert) or else Copy_Graph.Label (To_Insert) /= Node_Label (+"HAHA") @@ -60,7 +60,7 @@ package body Graph_Tests.Modify is return Fail; end if; To_Edge := Copy_Graph.Unused; - Copy_Graph.Insert ((To_Edge, 5, 11), Edge_Label (+"LOL")); + Copy_Graph.Insert (Graphs.Labeled_Edge_Type'((To_Edge, 5, 11), Edge_Label (+"LOL"))); if not Copy_Graph.Has_Edge (5, 11) or else not Copy_Graph.Has_Label ((To_Edge, 5, 11)) or else Copy_Graph.Label ((To_Edge, 5, 11)) /= Edge_Label (+"LOL") diff --git a/test/graph_tests-search.adb b/test/graph_tests-search.adb index d72ce67..9933c7d 100644 --- a/test/graph_tests-search.adb +++ b/test/graph_tests-search.adb @@ -64,23 +64,21 @@ package body Graph_Tests.Search is is Copy_Graph : Graphs.Graph := My_Nonempty_Graph; begin - if Copy_Graph.Contains (Graphs.No_Node) or - Copy_Graph.Contains (Graphs.No_Node, Node_Label (+"ABC")) or - Copy_Graph.Contains (Node_ID (20)) or + if Copy_Graph.Contains (Node_ID (20)) or not Copy_Graph.Contains (Node_ID (2)) or Copy_Graph.Contains (Edge_ID (20)) or not Copy_Graph.Contains (Edge_ID (7)) or - Copy_Graph.Contains ((99, 99, 99)) or - not Copy_Graph.Contains ((7, 2, 5)) or - Copy_Graph.Contains (2, Node_Label (+"ABC")) or - Copy_Graph.Contains ((7, 2, 5), Edge_Label (+"DEF")) + Copy_Graph.Contains (Graphs.Edge_Type'(99, 99, 99)) or + not Copy_Graph.Contains (Graphs.Edge_Type'(7, 2, 5)) or + Copy_Graph.Contains (Graphs.Labeled_Node_Type'(2, Node_Label (+"ABC"))) or + Copy_Graph.Contains (Graphs.Labeled_Edge_Type'((7, 2, 5), Edge_Label (+"DEF"))) then return Fail; end if; Copy_Graph.Append_Label (2, Node_Label (+"ABC")); Copy_Graph.Append_Label ((7, 2, 5), Edge_Label (+"DEF")); - if not Copy_Graph.Contains (2, Node_Label (+"ABC")) or - not Copy_Graph.Contains ((7, 2, 5), Edge_Label (+"DEF")) + if not Copy_Graph.Contains (Graphs.Labeled_Node_Type'(2, Node_Label (+"ABC"))) or + not Copy_Graph.Contains (Graphs.Labeled_Edge_Type'((7, 2, 5), Edge_Label (+"DEF"))) then return Fail; end if; @@ -116,25 +114,29 @@ package body Graph_Tests.Search is Branch_1 : Graphs.Cursor := Copy_Graph.To_Cursor (5); Branch_2 : Graphs.Cursor := Copy_Graph.To_Cursor (2); begin - if Graphs.Contains_In_Subgraph (Branch_1, Graphs.No_Node) or - Graphs.Contains_In_Subgraph (Branch_1, Graphs.No_Node, Node_Label (+"ABC")) or - Graphs.Contains_In_Subgraph (Branch_1, Node_ID (2)) or + if Graphs.Contains_In_Subgraph (Branch_1, Node_ID (2)) or not Graphs.Contains_In_Subgraph (Branch_1, Node_ID (10)) or - Graphs.Contains_In_Subgraph (Branch_1, (2, 2, 3)) or - not Graphs.Contains_In_Subgraph (Branch_1, (13, 7, 5)) or + Graphs.Contains_In_Subgraph (Branch_1, Graphs.Edge_Type'(2, 2, 3)) or + not Graphs.Contains_In_Subgraph (Branch_1, Graphs.Edge_Type'(13, 7, 5)) or Graphs.Contains_In_Subgraph (Branch_2, Node_ID (99)) or - Graphs.Contains_In_Subgraph (Branch_2, (1, 99, 99)) or - Graphs.Contains_In_Subgraph (Branch_1, Node_ID (5), Node_Label (+"ABC")) or - Graphs.Contains_In_Subgraph (Branch_1, (13, 7, 5), Edge_Label (+"DEF")) + Graphs.Contains_In_Subgraph (Branch_2, Graphs.Edge_Type'(1, 99, 99)) or + Graphs.Contains_In_Subgraph + (Branch_1, Graphs.Labeled_Node_Type'(Node_ID (5), Node_Label (+"ABC"))) or + Graphs.Contains_In_Subgraph + (Branch_1, Graphs.Labeled_Edge_Type'((13, 7, 5), Edge_Label (+"DEF"))) then return Fail; end if; Copy_Graph.Append_Label (5, Node_Label (+"ABC")); Copy_Graph.Append_Label ((13, 7, 5), Edge_Label (+"DEF")); - if Graphs.Contains_In_Subgraph (Branch_2, Node_ID (5), Node_Label (+"ABC")) or - not Graphs.Contains_In_Subgraph (Branch_1, Node_ID (5), Node_Label (+"ABC")) or - Graphs.Contains_In_Subgraph (Branch_2, (13, 7, 5), Edge_Label (+"DEF")) or - not Graphs.Contains_In_Subgraph (Branch_1, (13, 7, 5), Edge_Label (+"DEF")) + if Graphs.Contains_In_Subgraph + (Branch_2, Graphs.Labeled_Node_Type'(Node_ID (5), Node_Label (+"ABC"))) or + not Graphs.Contains_In_Subgraph + (Branch_1, Graphs.Labeled_Node_Type'(Node_ID (5), Node_Label (+"ABC"))) or + Graphs.Contains_In_Subgraph + (Branch_2, Graphs.Labeled_Edge_Type'((13, 7, 5), Edge_Label (+"DEF"))) or + not Graphs.Contains_In_Subgraph + (Branch_1, Graphs.Labeled_Edge_Type'((13, 7, 5), Edge_Label (+"DEF"))) then return Fail; end if; @@ -169,6 +171,45 @@ package body Graph_Tests.Search is end Contains_Label_Subgraph_Check; + function Contains_Path_Check + return Test_Result + is + Node_Path_In : Graphs.Node_Path := (1, 2, 3); + Node_Path_Out : Graphs.Node_Path := (87, 88, 89, 100); + Edge_Path_In : Graphs.Edge_Path := ((5, 1, 5), (6, 5, 6), (8, 6, 8)); + Edge_Path_Out : Graphs.Edge_Path := ((1, 1, 4), (5, 4, 7)); + begin + if not My_Complex_Graph.Contains_Path (Node_Path_In) or + My_Complex_Graph.Contains_Path (Node_Path_Out) or + not My_Complex_Graph.Contains_Path (Edge_Path_In) or + My_Complex_Graph.Contains_Path (Edge_Path_Out) + then + return Fail; + end if; + return Pass; + end Contains_Path_Check; + + + function Contains_Path_Subgraph_Check + return Test_Result + is + Node_Path_In : Graphs.Node_Path := (5, 7, 7, 5); + Node_Path_Out : Graphs.Node_Path := (1, 2, 3); + Edge_Path_In : Graphs.Edge_Path := ((6, 5, 6), (8, 6, 8)); + Edge_Path_Out : Graphs.Edge_Path := ((1, 1, 2), (2, 2, 3)); + Position : Graphs.Cursor := My_Complex_Graph.To_Cursor (5); + begin + if not Graphs.Contains_Path_In_Subgraph (Position, Node_Path_In) or + Graphs.Contains_Path_In_Subgraph (Position, Node_Path_Out) or + not Graphs.Contains_Path_In_Subgraph (Position, Edge_Path_In) or + Graphs.Contains_Path_In_Subgraph (Position, Edge_Path_Out) + then + return Fail; + end if; + return Pass; + end Contains_Path_Subgraph_Check; + + function Iterate_Check return Test_Result is diff --git a/test/graph_tests-search.ads b/test/graph_tests-search.ads index 63602e7..f2c1740 100644 --- a/test/graph_tests-search.ads +++ b/test/graph_tests-search.ads @@ -13,6 +13,8 @@ package Graph_Tests.Search is function Contains_Label_Check return Test_Result; function Contains_Subgraph_Check return Test_Result; function Contains_Label_Subgraph_Check return Test_Result; + function Contains_Path_Check return Test_Result; + function Contains_Path_Subgraph_Check return Test_Result; function Iterate_Check return Test_Result; function Iterate_Subgraph_Check return Test_Result; function Iterate_By_Check return Test_Result; @@ -25,6 +27,8 @@ package Graph_Tests.Search is (+"Contains_Label", Contains_Label_Check'Access), (+"Contains_In_Subgraph", Contains_Subgraph_Check'Access), (+"Contains_Label_In_Subgraph", Contains_Label_Subgraph_Check'Access), + (+"Contains_Path", Contains_Path_Check'Access), + (+"Contains_Path_In_Subgraph", Contains_Path_Subgraph_Check'Access), (+"Iterate", Iterate_Check'Access), (+"Iterate_Subgraph", Iterate_Subgraph_Check'Access), (+"Iterate_By", Iterate_By_Check'Access)); @@ -21,7 +21,7 @@ project Tests is package Compiler is - for Default_Switches("Ada") use ("-gnaty4aAbcefhiklM100nprt"); + for Default_Switches("Ada") use ("-gnaty4aAbcefhiklM100nprt","-gnata"); end Compiler; |