diff options
| -rw-r--r-- | src/directed_graphs.adb | 26 | ||||
| -rw-r--r-- | test/graph_tests-basic.adb | 82 | ||||
| -rw-r--r-- | test/graph_tests-basic.ads | 10 | ||||
| -rw-r--r-- | test/graph_tests-context.adb | 179 | ||||
| -rw-r--r-- | test/graph_tests-context.ads | 39 | ||||
| -rw-r--r-- | test/graph_tests-curses.adb | 90 | ||||
| -rw-r--r-- | test/graph_tests-curses.ads | 29 | ||||
| -rw-r--r-- | test/graph_tests-inspection.adb | 198 | ||||
| -rw-r--r-- | test/graph_tests-inspection.ads | 37 | ||||
| -rw-r--r-- | test/graph_tests-labels.adb | 201 | ||||
| -rw-r--r-- | test/graph_tests-labels.ads | 31 | ||||
| -rw-r--r-- | test/graph_tests-modify.adb | 160 | ||||
| -rw-r--r-- | test/graph_tests-modify.ads | 25 | ||||
| -rw-r--r-- | test/graph_tests-search.adb | 231 | ||||
| -rw-r--r-- | test/graph_tests-search.ads | 33 | ||||
| -rw-r--r-- | test/graph_tests.adb | 34 | ||||
| -rw-r--r-- | test/graph_tests.ads | 38 | ||||
| -rw-r--r-- | test/test_main.adb | 36 |
18 files changed, 1454 insertions, 25 deletions
diff --git a/src/directed_graphs.adb b/src/directed_graphs.adb index 4b9e823..c690d87 100644 --- a/src/directed_graphs.adb +++ b/src/directed_graphs.adb @@ -226,7 +226,9 @@ package body Directed_Graphs is raise Constraint_Error with "Graph does not contain node"; end if; for A of Container.Connections.Element (Node) loop - Result.Append (A.Node_ID); + if not Result.Contains (A.Node_ID) then + Result.Append (A.Node_ID); + end if; end loop; return V2A (Result); end Children; @@ -454,6 +456,7 @@ package body Directed_Graphs is 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; end Contains_In_Subgraph; @@ -505,6 +508,7 @@ package body Directed_Graphs is 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; end Contains_In_Subgraph; @@ -891,7 +895,7 @@ package body Directed_Graphs is end if; end if; for C in Position.Container.Iterate_Subgraph (Position) loop - Result := Result + Outdegree (Position); + Result := Result + Outdegree (C); end loop; return Result; end Edge_Count_In_Subgraph; @@ -1072,7 +1076,9 @@ package body Directed_Graphs is end if; end if; for C in Position.Container.Iterate_Subgraph (Position) loop - if Position.Container.Node_Labels.Constant_Reference (Element (C)) = Label then + if Position.Container.Has_Label (Element (C)) and then + Position.Container.Node_Labels.Constant_Reference (Element (C)) = Label + then Result.Append (Element (C)); end if; end loop; @@ -1939,13 +1945,18 @@ package body Directed_Graphs is end Next; procedure Next - (Position : in out Cursor) is + (Position : in out Cursor) + is + use type Node_Maps.Cursor; begin if Position.Container = null then Position := No_Element; return; end if; Node_Maps.Next (Position.Place); + if Position.Place = Node_Maps.No_Element then + Position := No_Element; + end if; end Next; function Next @@ -2268,13 +2279,18 @@ package body Directed_Graphs is end Previous; procedure Previous - (Position : in out Cursor) is + (Position : in out Cursor) + is + use type Node_Maps.Cursor; begin if Position.Container = null then Position := No_Element; return; end if; Node_Maps.Previous (Position.Place); + if Position.Place = Node_Maps.No_Element then + Position := No_Element; + end if; end Previous; function Previous diff --git a/test/graph_tests-basic.adb b/test/graph_tests-basic.adb index b0292a8..5d3aa33 100644 --- a/test/graph_tests-basic.adb +++ b/test/graph_tests-basic.adb @@ -1,25 +1,12 @@ --- Remove these when all tests are written -with Ada.Text_IO, Ada.Exceptions; -use Ada.Text_IO, Ada.Exceptions; +-- with Ada.Text_IO, Ada.Exceptions; +-- use Ada.Text_IO, Ada.Exceptions; package body Graph_Tests.Basic is - No_Nodes : Graphs.Node_Array (1 .. 0); - No_Edges : Graphs.Edge_Array (1 .. 0); - - Dup_Nodes : Graphs.Node_Array := (1, 2, 2, 3, 5, 9, 9, 9); - - Some_Nodes : Graphs.Node_Array := (1, 2, 5, 9); - Some_Edges : Graphs.Edge_Array := ((1, 1, 2), (2, 5, 9), (5, 9, 1)); - - My_Empty_Graph : Graphs.Graph := Graphs.To_Graph (No_Nodes, No_Edges); - My_Nonempty_Graph : Graphs.Graph := Graphs.To_Graph (Some_Nodes, Some_Edges); - - function To_Graph_Check return Test_Result is @@ -91,6 +78,71 @@ package body Graph_Tests.Basic is end Cursor_Element_Check; + function Equals_Check + return Test_Result + is + use type Graphs.Graph; + Other_Nonempty_Graph : Graphs.Graph := Graphs.To_Graph (Some_Nodes, Some_Edges); + begin + if not (Graphs.Empty_Graph = My_Empty_Graph) or + My_Empty_Graph = My_Nonempty_Graph or + not (My_Nonempty_Graph = Other_Nonempty_Graph) + then + return Fail; + else + return Pass; + end if; + end Equals_Check; + + + function Assign_Check + return Test_Result + is + use type Graphs.Graph; + Target_Graph : Graphs.Graph := Graphs.Empty_Graph; + begin + if Target_Graph = My_Nonempty_Graph then + return Fail; + end if; + Target_Graph.Assign (My_Nonempty_Graph); + if not (Target_Graph = My_Nonempty_Graph) then + return Fail; + end if; + return Pass; + end Assign_Check; + + + function Copy_Check + return Test_Result + is + use type Graphs.Graph; + begin + if My_Nonempty_Graph.Copy = My_Empty_Graph or + not (My_Nonempty_Graph.Copy = My_Nonempty_Graph) + then + return Fail; + end if; + return Pass; + end Copy_Check; + + + function Move_Check + return Test_Result + is + use type Graphs.Graph; + Source_Graph : Graphs.Graph := My_Nonempty_Graph; + Target_Graph : Graphs.Graph := Graphs.Empty_Graph; + begin + Target_Graph.Move (Source_Graph); + if not (Source_Graph = Graphs.Empty_Graph) or + not (Target_Graph = My_Nonempty_Graph) + then + return Fail; + end if; + return Pass; + end Move_Check; + + end Graph_Tests.Basic; diff --git a/test/graph_tests-basic.ads b/test/graph_tests-basic.ads index 80fb05d..fa868bf 100644 --- a/test/graph_tests-basic.ads +++ b/test/graph_tests-basic.ads @@ -11,13 +11,21 @@ package Graph_Tests.Basic is function Is_Empty_Check return Test_Result; function Clear_Check return Test_Result; function Cursor_Element_Check return Test_Result; + function Equals_Check return Test_Result; + function Assign_Check return Test_Result; + function Copy_Check return Test_Result; + function Move_Check return Test_Result; Tests : Test_Array := ((+"To_Graph", To_Graph_Check'Access), (+"Is_Empty", Is_Empty_Check'Access), (+"Clear", Clear_Check'Access), - (+"To_Cursor, Has_Element, Element", Cursor_Element_Check'Access)); + (+"To_Cursor, Has_Element, Element", Cursor_Element_Check'Access), + (+"Graph Equals", Equals_Check'Access), + (+"Assign", Assign_Check'Access), + (+"Copy", Copy_Check'Access), + (+"Move", Move_Check'Access)); end Graph_Tests.Basic; diff --git a/test/graph_tests-context.adb b/test/graph_tests-context.adb new file mode 100644 index 0000000..be0c6af --- /dev/null +++ b/test/graph_tests-context.adb @@ -0,0 +1,179 @@ + + +with Ada.Text_IO; +use Ada.Text_IO; + + +with Ada.Containers; + + +package body Graph_Tests.Context is + + + function Neighbors_Check + return Test_Result + is + function Perm is new Is_Permutation (Node_ID, Positive, Graphs.Node_Array); + begin + if not Perm (My_Neigh_Graph.Neighbors (2), (1 => 3)) or + not Perm (My_Neigh_Graph.Neighbors (3), (2, 4)) or + not Perm (My_Complex_Graph.Neighbors (7), (5, 7)) or + not Perm (My_Nonempty_Graph.Neighbors (5), No_Nodes) + then + return Fail; + end if; + return Pass; + end Neighbors_Check; + + + function Parents_Check + return Test_Result + is + function Perm is new Is_Permutation (Node_ID, Positive, Graphs.Node_Array); + begin + if not Perm (My_Complex_Graph.Parents (9), (6, 7)) or + not Perm (My_Complex_Graph.Parents (7), (5, 7)) or + not Perm (My_Complex_Graph.Parents (1), No_Nodes) + then + return Fail; + end if; + return Pass; + end Parents_Check; + + + function Children_Check + return Test_Result + is + function Perm is new Is_Permutation (Node_ID, Positive, Graphs.Node_Array); + begin + if not Perm (My_Complex_Graph.Children (1), (5, 2)) or + not Perm (My_Complex_Graph.Children (2), (3, 4)) or + not Perm (My_Complex_Graph.Children (7), (5, 7, 9, 10)) or + not Perm (My_Complex_Graph.Children (10), No_Nodes) + then + return Fail; + end if; + return Pass; + end Children_Check; + + + function Outbound_Check + return Test_Result + is + function Perm is new Is_Permutation (Graphs.Edge_Type, Positive, Graphs.Edge_Array); + begin + if not Perm (My_Complex_Graph.Outbound (1), ((1, 1, 2), (5, 1, 5))) or + not Perm (My_Complex_Graph.Outbound (7), + ((10, 7, 9), (11, 7, 10), (12, 7, 7), (13, 7, 5))) or + not Perm (My_Complex_Graph.Outbound (10), No_Edges) + then + return Fail; + end if; + return Pass; + end Outbound_Check; + + + function Inbound_Check + return Test_Result + is + function Perm is new Is_Permutation (Graphs.Edge_Type, Positive, Graphs.Edge_Array); + begin + if not Perm (My_Complex_Graph.Inbound (1), No_Edges) or + not Perm (My_Complex_Graph.Inbound (7), ((7, 5, 7), (12, 7, 7))) or + not Perm (My_Complex_Graph.Inbound (9), ((9, 6, 9), (10, 7, 9))) + then + return Fail; + end if; + return Pass; + end Inbound_Check; + + + function Between_Check + return Test_Result + is + function Perm is new Is_Permutation (Graphs.Edge_Type, Positive, Graphs.Edge_Array); + begin + if not Perm (My_Complex_Graph.Between (1, 10), No_Edges) or + not Perm (My_Complex_Graph.Between (2, 4), ((3, 2, 4), (4, 2, 4))) + then + return Fail; + end if; + return Pass; + end Between_Check; + + + function Outdegree_Check + return Test_Result + is + use type Ada.Containers.Count_Type; + begin + if My_Complex_Graph.Outdegree (1) /= 2 or + My_Complex_Graph.Outdegree (10) /= 0 or + My_Complex_Graph.Outdegree (2) /= 3 + then + return Fail; + end if; + return Pass; + end Outdegree_Check; + + + function Indegree_Check + return Test_Result + is + use type Ada.Containers.Count_Type; + begin + if My_Complex_Graph.Indegree (1) /= 0 or + My_Complex_Graph.Indegree (7) /= 2 or + My_Complex_Graph.Indegree (2) /= 1 + then + return Fail; + end if; + return Pass; + end Indegree_Check; + + + function Degree_Check + return Test_Result + is + use type Ada.Containers.Count_Type; + begin + if My_Complex_Graph.Degree (1) /= 2 or + My_Complex_Graph.Degree (10) /= 1 or + My_Complex_Graph.Degree (2) /= 4 + then + return Fail; + end if; + return Pass; + end Degree_Check; + + + function Has_Edge_Check + return Test_Result is + begin + if not My_Complex_Graph.Has_Edge (1, 2) or + not My_Complex_Graph.Has_Edge (2, 4) or + My_Complex_Graph.Has_Edge (1, 10) + then + return Fail; + end if; + return Pass; + end Has_Edge_Check; + + + function Has_Neighbor_Check + return Test_Result is + begin + if not My_Neigh_Graph.Has_Neighbor (2, 3) or + not My_Neigh_Graph.Has_Neighbor (3, 2) or + My_Neigh_Graph.Has_Neighbor (2, 4) or + not My_Complex_Graph.Has_Neighbor (7, 7) + then + return Fail; + end if; + return Pass; + end Has_Neighbor_Check; + + +end Graph_Tests.Context; + + diff --git a/test/graph_tests-context.ads b/test/graph_tests-context.ads new file mode 100644 index 0000000..2065040 --- /dev/null +++ b/test/graph_tests-context.ads @@ -0,0 +1,39 @@ + + +with Unit_Tests; +use Unit_Tests; + + +package Graph_Tests.Context is + + + function Neighbors_Check return Test_Result; + function Parents_Check return Test_Result; + function Children_Check return Test_Result; + function Outbound_Check return Test_Result; + function Inbound_Check return Test_Result; + function Between_Check return Test_Result; + function Outdegree_Check return Test_Result; + function Indegree_Check return Test_Result; + function Degree_Check return Test_Result; + function Has_Edge_Check return Test_Result; + function Has_Neighbor_Check return Test_Result; + + + Tests : Test_Array := + ((+"Neighbors", Neighbors_Check'Access), + (+"Parents", Parents_Check'Access), + (+"Children", Children_Check'Access), + (+"Outbound", Outbound_Check'Access), + (+"Inbound", Inbound_Check'Access), + (+"Between", Between_Check'Access), + (+"Outdegree", Outdegree_Check'Access), + (+"Indegree", Indegree_Check'Access), + (+"Degree", Degree_Check'Access), + (+"Has_Edge", Has_Edge_Check'Access), + (+"Has_Neighbor", Has_Neighbor_Check'Access)); + + +end Graph_Tests.Context; + + diff --git a/test/graph_tests-curses.adb b/test/graph_tests-curses.adb new file mode 100644 index 0000000..3667825 --- /dev/null +++ b/test/graph_tests-curses.adb @@ -0,0 +1,90 @@ + + +package body Graph_Tests.Curses is + + + function First_Check + return Test_Result + is + use type Graphs.Cursor; + begin + if My_Complex_Graph.First /= My_Complex_Graph.To_Cursor (1) or + My_Nonempty_Graph.First /= My_Nonempty_Graph.To_Cursor (2) + then + return Fail; + end if; + return Pass; + end First_Check; + + + function Last_Check + return Test_Result + is + use type Graphs.Cursor; + begin + if My_Complex_Graph.Last /= My_Complex_Graph.To_Cursor (10) or + My_Nonempty_Graph.Last /= My_Nonempty_Graph.To_Cursor (11) + then + return Fail; + end if; + return Pass; + end Last_Check; + + + function Next_Check + return Test_Result + is + use type Graphs.Cursor; + begin + if Graphs.Next (My_Complex_Graph.To_Cursor (3)) /= My_Complex_Graph.To_Cursor (4) or + Graphs.Next (My_Complex_Graph.To_Cursor (10)) /= Graphs.No_Element + then + return Fail; + end if; + return Pass; + end Next_Check; + + + function Previous_Check + return Test_Result + is + use type Graphs.Cursor; + begin + if Graphs.Previous (My_Complex_Graph.To_Cursor (6)) /= My_Complex_Graph.To_Cursor (5) or + Graphs.Previous (My_Complex_Graph.To_Cursor (1)) /= Graphs.No_Element + then + return Fail; + end if; + return Pass; + 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 + use type Graphs.Cursor; + Start : Graphs.Cursor := My_Complex_Graph.To_Cursor (2); + begin + if Graphs.Cursor_To (Start, 9) /= My_Complex_Graph.To_Cursor (9) then + return Fail; + end if; + return Pass; + end Cursor_To_Check; + + +end Graph_Tests.Curses; + + diff --git a/test/graph_tests-curses.ads b/test/graph_tests-curses.ads new file mode 100644 index 0000000..dff209b --- /dev/null +++ b/test/graph_tests-curses.ads @@ -0,0 +1,29 @@ + + +with Unit_Tests; +use Unit_Tests; + + +package Graph_Tests.Curses is + + + function First_Check return Test_Result; + 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; + + + Tests : Test_Array := + ((+"First", First_Check'Access), + (+"Last", Last_Check'Access), + (+"Next", Next_Check'Access), + (+"Previous", Previous_Check'Access), + (+"Follow", Follow_Check'Access), + (+"Cursor_To", Cursor_To_Check'Access)); + + +end Graph_Tests.Curses; + + diff --git a/test/graph_tests-inspection.adb b/test/graph_tests-inspection.adb new file mode 100644 index 0000000..ac2cdb3 --- /dev/null +++ b/test/graph_tests-inspection.adb @@ -0,0 +1,198 @@ + + +-- with Ada.Text_IO; +-- use Ada.Text_IO; + + +with Ada.Containers; + + +package body Graph_Tests.Inspection is + + + function Node_Count_Check + return Test_Result + is + use type Ada.Containers.Count_Type; + begin + if Graphs.Empty_Graph.Node_Count /= 0 or + My_Empty_Graph.Node_Count /= 0 or + My_Nonempty_Graph.Node_Count /= Some_Nodes'Length or + My_Complex_Graph.Node_Count /= Complex_Nodes'Length + then + return Fail; + end if; + return Pass; + end Node_Count_Check; + + + function Node_Count_Subgraph_Check + return Test_Result + is + use type Ada.Containers.Count_Type; + Cursor_1 : Graphs.Cursor := My_Complex_Graph.To_Cursor (1); + Cursor_2 : Graphs.Cursor := My_Complex_Graph.To_Cursor (5); + Cursor_3 : Graphs.Cursor := My_Complex_Graph.To_Cursor (7); + Cursor_4 : Graphs.Cursor := My_Complex_Graph.To_Cursor (6); + begin + if Graphs.Node_Count_In_Subgraph (Cursor_1) /= Complex_Nodes'Length or + Graphs.Node_Count_In_Subgraph (Cursor_2) /= 6 or + Graphs.Node_Count_In_Subgraph (Cursor_3) /= 6 or + Graphs.Node_Count_In_Subgraph (Cursor_4) /= 3 + then + return Fail; + end if; + return Pass; + end Node_Count_Subgraph_Check; + + + function Edge_Count_Check + return Test_Result + is + use type Ada.Containers.Count_Type; + begin + if Graphs.Empty_Graph.Edge_Count /= 0 or + My_Empty_Graph.Edge_Count /= 0 or + My_Nonempty_Graph.Edge_Count /= Some_Edges'Length or + My_Complex_Graph.Edge_Count /= Complex_Edges'Length + then + return Fail; + end if; + return Pass; + end Edge_Count_Check; + + + function Edge_Count_Subgraph_Check + return Test_Result + is + use type Ada.Containers.Count_Type; + Cursor_1 : Graphs.Cursor := My_Complex_Graph.To_Cursor (1); + Cursor_2 : Graphs.Cursor := My_Complex_Graph.To_Cursor (5); + Cursor_3 : Graphs.Cursor := My_Complex_Graph.To_Cursor (6); + begin + if Graphs.Edge_Count_In_Subgraph (Cursor_1) /= Complex_Edges'Length or + Graphs.Edge_Count_In_Subgraph (Cursor_2) /= 8 or + Graphs.Edge_Count_In_Subgraph (Cursor_3) /= 2 + then + return Fail; + end if; + return Pass; + end Edge_Count_Subgraph_Check; + + + function Nodes_Check + return Test_Result + is + function Perm is new Is_Permutation (Node_ID, Positive, Graphs.Node_Array); + Node_List : Graphs.Node_Array := My_Complex_Graph.Nodes; + begin + if Perm (Node_List, Complex_Nodes) then + return Pass; + else + return Fail; + end if; + end Nodes_Check; + + + function Nodes_Subgraph_Check + return Test_Result + is + function Perm is new Is_Permutation (Node_ID, Positive, Graphs.Node_Array); + Node_List_1 : Graphs.Node_Array := + Graphs.Nodes_In_Subgraph (My_Complex_Graph.To_Cursor (6)); + Node_List_2 : Graphs.Node_Array := + Graphs.Nodes_In_Subgraph (My_Complex_Graph.To_Cursor (7)); + Node_List_3 : Graphs.Node_Array := + Graphs.Nodes_In_Subgraph (My_Complex_Graph.To_Cursor (1)); + begin + if Perm (Node_List_1, (6, 8, 9)) and + Perm (Node_List_2, (5, 6, 10, 8, 9, 7)) and + Perm (Node_List_3, Complex_Nodes) + then + return Pass; + else + return Fail; + end if; + end Nodes_Subgraph_Check; + + + function Edges_Check + return Test_Result + is + function Perm is new Is_Permutation (Graphs.Edge_Type, Positive, Graphs.Edge_Array); + Edge_List : Graphs.Edge_Array := My_Complex_Graph.Edges; + begin + if Perm (Edge_List, Complex_Edges) then + return Pass; + else + return Fail; + end if; + end Edges_Check; + + + function Edges_Subgraph_Check + return Test_Result + is + function Perm is new Is_Permutation (Graphs.Edge_Type, Positive, Graphs.Edge_Array); + Edge_List_1 : Graphs.Edge_Array := + Graphs.Edges_In_Subgraph (My_Complex_Graph.To_Cursor (6)); + Edge_List_2 : Graphs.Edge_Array := + Graphs.Edges_In_Subgraph (My_Complex_Graph.To_Cursor (7)); + Edge_List_3 : Graphs.Edge_Array := + Graphs.Edges_In_Subgraph (My_Complex_Graph.To_Cursor (1)); + begin + if Perm (Edge_List_1, ((8, 6, 8), (9, 6, 9))) and + Perm (Edge_List_2, ((10, 7, 9), (11, 7, 10), (12, 7, 7), + (13, 7, 5), (6, 5, 6), (7, 5, 7), (8, 6, 8), (9, 6, 9))) and + Perm (Edge_List_3, Complex_Edges) + then + return Pass; + else + return Fail; + end if; + end Edges_Subgraph_Check; + + + function Node_Range_Check + return Test_Result + is + Min, Max : Node_ID; + begin + My_Complex_Graph.Node_Range (Min, Max); + if Min /= 1 or Max /= 10 then + return Fail; + end if; + My_Nonempty_Graph.Node_Range (Min, Max); + if Min /= 2 or Max /= 11 then + return Fail; + end if; + return Pass; + end Node_Range_Check; + + + function Unused_Check + return Test_Result + is + use type Graphs.Node_Array; + begin + if My_Empty_Graph.Unused /= Node_ID (1) or + My_Nonempty_Graph.Unused /= Node_ID (1) or + My_Complex_Graph.Unused /= Node_ID (11) or + My_Empty_Graph.Unused /= Edge_ID (1) or + My_Nonempty_Graph.Unused /= Edge_ID (1) or + My_Complex_Graph.Unused /= Edge_ID (14) or + Graphs.Unused (My_Nonempty_Graph.To_Cursor (2)) /= Node_ID (1) or + Graphs.Unused (My_Complex_Graph.To_Cursor (3)) /= Node_ID (11) or + Graphs.Unused (My_Nonempty_Graph.To_Cursor (2)) /= Edge_ID (1) or + Graphs.Unused (My_Complex_Graph.To_Cursor (10)) /= Edge_ID (14) or + My_Nonempty_Graph.Unused (8) /= (1, 3, 4, 6, 7, 8, 10, 12) + then + return Fail; + end if; + return Pass; + end Unused_Check; + + +end Graph_Tests.Inspection; + + diff --git a/test/graph_tests-inspection.ads b/test/graph_tests-inspection.ads new file mode 100644 index 0000000..ed2d116 --- /dev/null +++ b/test/graph_tests-inspection.ads @@ -0,0 +1,37 @@ + + +with Unit_Tests; +use Unit_Tests; + + +package Graph_Tests.Inspection is + + + function Node_Count_Check return Test_Result; + function Node_Count_Subgraph_Check return Test_Result; + function Edge_Count_Check return Test_Result; + function Edge_Count_Subgraph_Check return Test_Result; + function Nodes_Check return Test_Result; + function Nodes_Subgraph_Check return Test_Result; + function Edges_Check return Test_Result; + function Edges_Subgraph_Check return Test_Result; + function Node_Range_Check return Test_Result; + function Unused_Check return Test_Result; + + + Tests : Test_Array := + ((+"Node_Count", Node_Count_Check'Access), + (+"Node_Count_In_Subgraph", Node_Count_Subgraph_Check'Access), + (+"Edge_Count", Edge_Count_Check'Access), + (+"Edge_Count_In_Subgraph", Edge_Count_Subgraph_Check'Access), + (+"Nodes", Nodes_Check'Access), + (+"Nodes_In_Subgraph", Nodes_Subgraph_Check'Access), + (+"Edges", Edges_Check'Access), + (+"Edges_In_Subgraph", Edges_Subgraph_Check'Access), + (+"Node_Range", Node_Range_Check'Access), + (+"Unused", Unused_Check'Access)); + + +end Graph_Tests.Inspection; + + diff --git a/test/graph_tests-labels.adb b/test/graph_tests-labels.adb new file mode 100644 index 0000000..b99eb5d --- /dev/null +++ b/test/graph_tests-labels.adb @@ -0,0 +1,201 @@ + + +package body Graph_Tests.Labels is + + + function Getter_Setter_Check + return Test_Result + is + Copy_Graph : Graphs.Graph := My_Nonempty_Graph; + begin + if Copy_Graph.Has_Label (2) then + return Fail; + end if; + Copy_Graph.Append_Label (2, Node_Label (+"OMG")); + if not Copy_Graph.Has_Label (2) or + Copy_Graph.Label (2) /= Node_Label (+"OMG") + then + return Fail; + end if; + if Copy_Graph.Has_Label ((7, 2, 5)) then + return Fail; + end if; + Copy_Graph.Append_Label ((7, 2, 5), Edge_Label (+"EDGY")); + if not Copy_Graph.Has_Label ((7, 2, 5)) or + Copy_Graph.Label ((7, 2, 5)) /= Edge_Label (+"EDGY") + then + return Fail; + end if; + return Pass; + end Getter_Setter_Check; + + + function Replace_Label_Check + return Test_Result + is + Copy_Graph : Graphs.Graph := My_Nonempty_Graph; + begin + begin + Copy_Graph.Replace_Label (2, Node_Label (+"OMG")); + return Fail; + exception + when Constraint_Error => null; + end; + Copy_Graph.Append_Label (2, Node_Label (+"OMG")); + Copy_Graph.Replace_Label (2, Node_Label (+"NOOO")); + if Copy_Graph.Label (2) /= Node_Label (+"NOOO") then + return Fail; + end if; + begin + Copy_Graph.Replace_Label ((7, 2, 5), Edge_Label (+"EDGY")); + return Fail; + exception + when Constraint_Error => null; + end; + Copy_Graph.Append_Label ((7, 2, 5), Edge_Label (+"EDGY")); + Copy_Graph.Replace_Label ((7, 2, 5), Edge_Label (+"YEES")); + if Copy_Graph.Label ((7, 2, 5)) /= Edge_Label (+"YEES") then + return Fail; + end if; + return Pass; + end Replace_Label_Check; + + + function Delete_Label_Check + return Test_Result + is + Copy_Graph : Graphs.Graph := My_Nonempty_Graph; + begin + Copy_Graph.Append_Label (2, Node_Label (+"A")); + Copy_Graph.Delete_Label (2); + if Copy_Graph.Has_Label (2) then + return Fail; + end if; + Copy_Graph.Append_Label ((7, 2, 5), Edge_Label (+"B")); + Copy_Graph.Delete_Label ((7, 2, 5)); + if Copy_Graph.Has_Label ((7, 2, 5)) then + return Fail; + end if; + return Pass; + end Delete_Label_Check; + + + function Const_Ref_Check + return Test_Result + is + Copy_Graph : Graphs.Graph := My_Nonempty_Graph; + begin + Copy_Graph.Append_Label (2, Node_Label (+"A")); + Copy_Graph.Append_Label ((7, 2, 5), Edge_Label (+"B")); + begin + declare + Ref : Graphs.Node_Label_Constant_Reference := + Copy_Graph.Constant_Label_Reference (11); + begin + return Fail; + end; + exception + when Constraint_Error => null; + end; + begin + declare + Ref : Graphs.Edge_Label_Constant_Reference := + Copy_Graph.Constant_Label_Reference ((5, 11, 2)); + begin + return Fail; + end; + exception + when Constraint_Error => null; + end; + if Copy_Graph.Constant_Label_Reference (2) /= Node_Label (+"A") or + Copy_Graph.Constant_Label_Reference ((7, 2, 5)) /= Edge_Label (+"B") + then + return Fail; + end if; + return Pass; + end Const_Ref_Check; + + + function Ref_Check + return Test_Result + is + Copy_Graph : Graphs.Graph := My_Nonempty_Graph; + begin + Copy_Graph.Append_Label (2, Node_Label (+"A")); + Copy_Graph.Append_Label ((7, 2, 5), Edge_Label (+"B")); + begin + declare + Ref : Graphs.Node_Label_Reference := + Copy_Graph.Label_Reference (11); + begin + return Fail; + end; + exception + when Constraint_Error => null; + end; + begin + declare + Ref : Graphs.Edge_Label_Reference := + Copy_Graph.Label_Reference ((5, 11, 2)); + begin + return Fail; + end; + exception + when Constraint_Error => null; + end; + if Copy_Graph.Label_Reference (2) /= Node_Label (+"A") or + Copy_Graph.Label_Reference ((7, 2, 5)) /= Edge_Label (+"B") + then + return Fail; + end if; + Copy_Graph.Label_Reference (2) := Node_Label (+"C"); + Copy_Graph.Label_Reference ((7, 2, 5)) := Edge_Label (+"D"); + if Copy_Graph.Label_Reference (2) /= Node_Label (+"C") or + Copy_Graph.Label_Reference ((7, 2, 5)) /= Edge_Label (+"D") + then + return Fail; + end if; + return Pass; + end Ref_Check; + + + function Has_Labeled_Edge_Check + return Test_Result + is + Copy_Graph : Graphs.Graph := My_Nonempty_Graph; + begin + Copy_Graph.Append_Label ((5, 11, 2), Edge_Label (+"BLAH")); + if not Copy_Graph.Has_Labeled_Edge (11, 2) or + Copy_Graph.Has_Labeled_Edge (2, 5) or + Copy_Graph.Has_Labeled_Edge (2, 11) + then + return Fail; + end if; + return Pass; + end Has_Labeled_Edge_Check; + + + function Clear_Labels_Check + return Test_Result + is + Copy_Graph : Graphs.Graph := My_Nonempty_Graph; + begin + Copy_Graph.Append_Label (2, Node_Label (+"A")); + Copy_Graph.Append_Label (11, Node_Label (+"B")); + Copy_Graph.Append_Label ((7, 2, 5), Edge_Label (+"C")); + Copy_Graph.Append_Label ((5, 11, 2), Edge_Label (+"D")); + Copy_Graph.Clear_Labels; + if Copy_Graph.Has_Label (2) or + Copy_Graph.Has_Label (11) or + Copy_Graph.Has_Label ((7, 2, 5)) or + Copy_Graph.Has_Label ((5, 11, 2)) + then + return Fail; + end if; + return Pass; + end Clear_Labels_Check; + + +end Graph_Tests.Labels; + + diff --git a/test/graph_tests-labels.ads b/test/graph_tests-labels.ads new file mode 100644 index 0000000..2702896 --- /dev/null +++ b/test/graph_tests-labels.ads @@ -0,0 +1,31 @@ + + +with Unit_Tests; +use Unit_Tests; + + +package Graph_Tests.Labels is + + + function Getter_Setter_Check return Test_Result; + function Replace_Label_Check return Test_Result; + function Delete_Label_Check return Test_Result; + function Const_Ref_Check return Test_Result; + function Ref_Check return Test_Result; + function Has_Labeled_Edge_Check return Test_Result; + function Clear_Labels_Check return Test_Result; + + + Tests : Test_Array := + ((+"Append_Label, Has_Label, Label", Getter_Setter_Check'Access), + (+"Replace_Label", Replace_Label_Check'Access), + (+"Delete_Label", Delete_Label_Check'Access), + (+"Constant_Label_Reference", Const_Ref_Check'Access), + (+"Label_Reference", Ref_Check'Access), + (+"Has_Labeled_Edge", Has_Labeled_Edge_Check'Access), + (+"Clear_Labels", Clear_Labels_Check'Access)); + + +end Graph_Tests.Labels; + + diff --git a/test/graph_tests-modify.adb b/test/graph_tests-modify.adb new file mode 100644 index 0000000..0c1d5d9 --- /dev/null +++ b/test/graph_tests-modify.adb @@ -0,0 +1,160 @@ + + +with Ada.Containers; + + +package body Graph_Tests.Modify is + + + function Insert_Check + return Test_Result + is + use type Graphs.Cursor; + To_Insert : Node_ID; + To_Edge : Edge_ID; + Copy_Graph : Graphs.Graph := My_Nonempty_Graph; + begin + To_Insert := Copy_Graph.Unused; + if Copy_Graph.To_Cursor (To_Insert) /= Graphs.No_Element then + return Fail; + end if; + Copy_Graph.Insert (To_Insert); + if Copy_Graph.To_Cursor (To_Insert) = Graphs.No_Element then + return Fail; + end if; + To_Insert := Copy_Graph.Unused; + if Copy_Graph.To_Cursor (To_Insert) /= Graphs.No_Element then + return Fail; + end if; + Copy_Graph.Insert (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") + then + return Fail; + end if; + declare + Insert_Nodes : Graphs.Node_Array := Copy_Graph.Unused (5); + begin + for N of Insert_Nodes loop + if Copy_Graph.To_Cursor (N) /= Graphs.No_Element then + return Fail; + end if; + end loop; + Copy_Graph.Insert (Insert_Nodes); + for N of Insert_Nodes loop + if Copy_Graph.To_Cursor (N) = Graphs.No_Element then + return Fail; + end if; + end loop; + end; + if Copy_Graph.Has_Edge (5, 9) then + return Fail; + end if; + To_Edge := Copy_Graph.Unused; + Copy_Graph.Insert (Graphs.Edge_Type'(To_Edge, 5, 9)); + if not Copy_Graph.Has_Edge (5, 9) then + return Fail; + end if; + if Copy_Graph.Has_Edge (5, 11) then + return Fail; + end if; + To_Edge := Copy_Graph.Unused; + Copy_Graph.Insert ((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") + then + return Fail; + end if; + return Pass; + end Insert_Check; + + + function Delete_Check + return Test_Result + is + use type Graphs.Cursor; + use type Ada.Containers.Count_Type; + Copy_Graph : Graphs.Graph := My_Nonempty_Graph; + begin + if Copy_Graph.To_Cursor (2) = Graphs.No_Element then + return Fail; + end if; + Copy_Graph.Delete (2); + if Copy_Graph.To_Cursor (2) /= Graphs.No_Element or + Copy_Graph.Node_Count /= 3 or + Copy_Graph.Edge_Count /= 1 + then + return Fail; + end if; + if not Copy_Graph.Has_Edge (9, 11) then + return Fail; + end if; + Copy_Graph.Delete (Graphs.Edge_Type'(2, 9, 11)); + if Copy_Graph.Has_Edge (9, 11) or + Copy_Graph.Edge_Count /= 0 + then + return Fail; + end if; + return Pass; + end Delete_Check; + + + function Delete_Subgraph_Check + return Test_Result + is + use type Graphs.Cursor; + use type Ada.Containers.Count_Type; + Copy_Graph : Graphs.Graph := My_Complex_Graph; + Position : Graphs.Cursor := Copy_Graph.To_Cursor (2); + begin + Graphs.Delete_Subgraph (Position); + if Copy_Graph.To_Cursor (2) /= Graphs.No_Element or + Copy_Graph.Node_Count /= 7 or + Copy_Graph.Edge_Count /= 9 + then + return Fail; + end if; + return Pass; + end Delete_Subgraph_Check; + + + function Swap_Check + return Test_Result + is + use type Ada.Containers.Count_Type; + function Perm is new Is_Permutation (Node_ID, Positive, Graphs.Node_Array); + Copy_Graph : Graphs.Graph := My_Complex_Graph; + Left_Parents : Graphs.Node_Array := Copy_Graph.Parents (2); + Left_Children : Graphs.Node_Array := Copy_Graph.Children (2); + Left_Indegree : Ada.Containers.Count_Type := Copy_Graph.Indegree (2); + Left_Outdegree : Ada.Containers.Count_Type := Copy_Graph.Outdegree (2); + Right_Parents : Graphs.Node_Array := Copy_Graph.Parents (5); + Right_Children : Graphs.Node_Array := Copy_Graph.Children (5); + Right_Indegree : Ada.Containers.Count_Type := Copy_Graph.Indegree (5); + Right_Outdegree : Ada.Containers.Count_Type := Copy_Graph.Outdegree (5); + begin + Copy_Graph.Append_Label (2, Node_Label (+"ABC")); + Copy_Graph.Append_Label (5, Node_Label (+"DEF")); + Copy_Graph.Swap (2, 5); + if not Perm (Copy_Graph.Parents (2), Right_Parents) or + not Perm (Copy_Graph.Children (2), Right_Children) or + not Perm (Copy_Graph.Parents (5), Left_Parents) or + not Perm (Copy_Graph.Children (5), Left_Children) or + Copy_Graph.Label (2) /= Node_Label (+"ABC") or + Copy_Graph.Label (5) /= Node_Label (+"DEF") or + Copy_Graph.Indegree (2) /= Right_Indegree or + Copy_Graph.Outdegree (2) /= Right_Outdegree or + Copy_Graph.Indegree (5) /= Left_Indegree or + Copy_Graph.Outdegree (5) /= Left_Outdegree + then + return Fail; + end if; + return Pass; + end Swap_Check; + + +end Graph_Tests.Modify; + + diff --git a/test/graph_tests-modify.ads b/test/graph_tests-modify.ads new file mode 100644 index 0000000..ed896b1 --- /dev/null +++ b/test/graph_tests-modify.ads @@ -0,0 +1,25 @@ + + +with Unit_Tests; +use Unit_Tests; + + +package Graph_Tests.Modify is + + + function Insert_Check return Test_Result; + function Delete_Check return Test_Result; + function Delete_Subgraph_Check return Test_Result; + function Swap_Check return Test_Result; + + + Tests : Test_Array := + ((+"Insert", Insert_Check'Access), + (+"Delete", Delete_Check'Access), + (+"Delete_Subgraph", Delete_Subgraph_Check'Access), + (+"Swap", Swap_Check'Access)); + + +end Graph_Tests.Modify; + + diff --git a/test/graph_tests-search.adb b/test/graph_tests-search.adb new file mode 100644 index 0000000..54b51a4 --- /dev/null +++ b/test/graph_tests-search.adb @@ -0,0 +1,231 @@ + + +package body Graph_Tests.Search is + + + function Find_Check + return Test_Result + is + function Node_Perm is new Is_Permutation (Node_ID, Positive, Graphs.Node_Array); + function Edge_Perm is new Is_Permutation (Graphs.Edge_Type, Positive, Graphs.Edge_Array); + Copy_Graph : Graphs.Graph := My_Complex_Graph; + begin + if not Node_Perm (Copy_Graph.Find (Node_Label (+"LOL")), No_Nodes) or + not Edge_Perm (Copy_Graph.Find (Edge_Label (+"KEK")), No_Edges) + then + return Fail; + end if; + Copy_Graph.Append_Label (2, Node_Label (+"LOL")); + Copy_Graph.Append_Label (5, Node_Label (+"LOL")); + Copy_Graph.Append_Label ((6, 5, 6), Edge_Label (+"KEK")); + Copy_Graph.Append_Label ((7, 5, 7), Edge_Label (+"KEK")); + Copy_Graph.Append_Label (10, Node_Label (+"KEK")); + Copy_Graph.Append_Label ((4, 2, 4), Edge_Label (+"LOL")); + if not Node_Perm (Copy_Graph.Find (Node_Label (+"LOL")), (2, 5)) or + not Edge_Perm (Copy_Graph.Find (Edge_Label (+"KEK")), ((6, 5, 6), (7, 5, 7))) + then + return Fail; + end if; + return Pass; + end Find_Check; + + + function Find_Subgraph_Check + return Test_Result + is + function Node_Perm is new Is_Permutation (Node_ID, Positive, Graphs.Node_Array); + function Edge_Perm is new Is_Permutation (Graphs.Edge_Type, Positive, Graphs.Edge_Array); + Copy_Graph : Graphs.Graph := My_Complex_Graph; + Position : Graphs.Cursor := Copy_Graph.To_Cursor (7); + begin + if not Node_Perm (Graphs.Find_In_Subgraph (Position, Node_Label (+"LOL")), No_Nodes) or + not Edge_Perm (Graphs.Find_In_Subgraph (Position, Edge_Label (+"KEK")), No_Edges) + then + return Fail; + end if; + Copy_Graph.Append_Label (2, Node_Label (+"LOL")); + Copy_Graph.Append_Label (5, Node_Label (+"LOL")); + Copy_Graph.Append_Label ((6, 5, 6), Edge_Label (+"KEK")); + Copy_Graph.Append_Label ((7, 5, 7), Edge_Label (+"KEK")); + Copy_Graph.Append_Label (10, Node_Label (+"KEK")); + Copy_Graph.Append_Label ((4, 2, 4), Edge_Label (+"LOL")); + if not Node_Perm (Graphs.Find_In_Subgraph (Position, Node_Label (+"LOL")), (1 => 5)) or + not Edge_Perm (Graphs.Find_In_Subgraph (Position, Edge_Label (+"KEK")), + ((6, 5, 6), (7, 5, 7))) + then + return Fail; + end if; + return Pass; + end Find_Subgraph_Check; + + + function Contains_Check + return Test_Result + is + Copy_Graph : Graphs.Graph := My_Nonempty_Graph; + begin + 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")) + 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")) + then + return Fail; + end if; + return Pass; + end Contains_Check; + + + function Contains_Label_Check + return Test_Result + is + Copy_Graph : Graphs.Graph := My_Nonempty_Graph; + begin + if Copy_Graph.Contains_Label (Node_Label (+"ABC")) or + Copy_Graph.Contains_Label (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_Label (Node_Label (+"ABC")) or + not Copy_Graph.Contains_Label (Edge_Label (+"DEF")) + then + return Fail; + end if; + return Pass; + end Contains_Label_Check; + + + function Contains_Subgraph_Check + return Test_Result + is + Copy_Graph : Graphs.Graph := My_Complex_Graph; + 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, 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_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")) + 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")) + then + return Fail; + end if; + return Pass; + end Contains_Subgraph_Check; + + + function Contains_Label_Subgraph_Check + return Test_Result + is + Copy_Graph : Graphs.Graph := My_Complex_Graph; + Branch_1 : Graphs.Cursor := Copy_Graph.To_Cursor (5); + Branch_2 : Graphs.Cursor := Copy_Graph.To_Cursor (2); + begin + if Graphs.Contains_Label_In_Subgraph (Branch_1, Node_Label (+"ABC")) or + Graphs.Contains_Label_In_Subgraph (Branch_1, Edge_Label (+"DEF")) or + Graphs.Contains_Label_In_Subgraph (Branch_2, Node_Label (+"ABC")) or + Graphs.Contains_Label_In_Subgraph (Branch_2, Edge_Label (+"DEF")) + then + return Fail; + end if; + Copy_Graph.Append_Label (5, Node_Label (+"ABC")); + Copy_Graph.Append_Label ((8, 6, 8), Edge_Label (+"DEF")); + if not Graphs.Contains_Label_In_Subgraph (Branch_1, Node_Label (+"ABC")) or + not Graphs.Contains_Label_In_Subgraph (Branch_1, Edge_Label (+"DEF")) or + Graphs.Contains_Label_In_Subgraph (Branch_2, Node_Label (+"ABC")) or + Graphs.Contains_Label_In_Subgraph (Branch_2, Edge_Label (+"DEF")) + then + return Fail; + end if; + return Pass; + end Contains_Label_Subgraph_Check; + + + function Iterate_Check + return Test_Result + is + Index : Positive := 1; + Check_1 : Graphs.Node_Array := (2, 5, 9, 11); + Check_2 : Graphs.Node_Array := (1, 2, 3, 4, 5, 6, 7, 8, 9, 10); + begin + for C in My_Nonempty_Graph.Iterate loop + if Index not in Check_1'Range or else + Graphs.Element (C) /= Check_1 (Index) + then + return Fail; + else + Index := Index + 1; + end if; + end loop; + Index := 1; + for C in My_Complex_Graph.Iterate loop + if Index not in Check_2'Range or else + Graphs.Element (C) /= Check_2 (Index) + then + return Fail; + else + Index := Index + 1; + end if; + end loop; + return Pass; + end Iterate_Check; + + + function Iterate_Subgraph_Check + return Test_Result + is + Index : Positive := 1; + Check : Graphs.Node_Array := (5, 6, 7, 8, 9, 10); + Position_1 : Graphs.Cursor := My_Complex_Graph.To_Cursor (5); + Position_2 : Graphs.Cursor := My_Complex_Graph.To_Cursor (7); + begin + for C in My_Complex_Graph.Iterate_Subgraph (Position_1) loop + if Index not in Check'Range or else + Graphs.Element (C) /= Check (Index) + then + return Fail; + else + Index := Index + 1; + end if; + end loop; + Index := 1; + for C in My_Complex_Graph.Iterate_Subgraph (Position_2) loop + if Index not in Check'Range or else + Graphs.Element (C) /= Check (Index) + then + return Fail; + else + Index := Index + 1; + end if; + end loop; + return Pass; + end Iterate_Subgraph_Check; + + +end Graph_Tests.Search; + + diff --git a/test/graph_tests-search.ads b/test/graph_tests-search.ads new file mode 100644 index 0000000..d0ea2bb --- /dev/null +++ b/test/graph_tests-search.ads @@ -0,0 +1,33 @@ + + +with Unit_Tests; +use Unit_Tests; + + +package Graph_Tests.Search is + + + function Find_Check return Test_Result; + function Find_Subgraph_Check return Test_Result; + function Contains_Check return Test_Result; + function Contains_Label_Check return Test_Result; + function Contains_Subgraph_Check return Test_Result; + function Contains_Label_Subgraph_Check return Test_Result; + function Iterate_Check return Test_Result; + function Iterate_Subgraph_Check return Test_Result; + + + Tests : Test_Array := + ((+"Find", Find_Check'Access), + (+"Find_In_Subgraph", Find_Subgraph_Check'Access), + (+"Contains", Contains_Check'Access), + (+"Contains_Label", Contains_Label_Check'Access), + (+"Contains_In_Subgraph", Contains_Subgraph_Check'Access), + (+"Contains_Label_In_Subgraph", Contains_Label_Subgraph_Check'Access), + (+"Iterate", Iterate_Check'Access), + (+"Iterate_Subgraph", Iterate_Subgraph_Check'Access)); + + +end Graph_Tests.Search; + + diff --git a/test/graph_tests.adb b/test/graph_tests.adb new file mode 100644 index 0000000..321313f --- /dev/null +++ b/test/graph_tests.adb @@ -0,0 +1,34 @@ + + +package body Graph_Tests is + + + function Is_Permutation + (Left, Right : in Array_Type) + return Boolean + is + Marked_Off : array (Right'Range) of Boolean := (others => False); + Same_Count : Natural := 0; + begin + if Left'Length = 0 and Right'Length = 0 then + return True; + end if; + if Left'Length /= Right'Length then + return False; + end if; + for L in Left'Range loop + for R in Right'Range loop + if Left (L) = Right (R) and not Marked_Off (R) then + Marked_Off (R) := True; + Same_Count := Same_Count + 1; + exit; + end if; + end loop; + end loop; + return Same_Count = Left'Length; + end Is_Permutation; + + +end Graph_Tests; + + diff --git a/test/graph_tests.ads b/test/graph_tests.ads index 18ea321..c2dddfe 100644 --- a/test/graph_tests.ads +++ b/test/graph_tests.ads @@ -25,6 +25,44 @@ package Graph_Tests is Edge_Label_Type => Edge_Label); + No_Nodes : Graphs.Node_Array (1 .. 0); + No_Edges : Graphs.Edge_Array (1 .. 0); + + Dup_Nodes : constant Graphs.Node_Array := (1, 2, 2, 3, 5, 9, 9, 9); + + Some_Nodes : constant Graphs.Node_Array := (2, 5, 9, 11); + Some_Edges : constant Graphs.Edge_Array := ((7, 2, 5), (2, 9, 11), (5, 11, 2)); + + My_Empty_Graph : constant Graphs.Graph := Graphs.To_Graph (No_Nodes, No_Edges); + My_Nonempty_Graph : constant Graphs.Graph := Graphs.To_Graph (Some_Nodes, Some_Edges); + + Complex_Nodes : constant Graphs.Node_Array := (1, 2, 3, 4, 5, 6, 7, 8, 9, 10); + Complex_Edges : constant Graphs.Edge_Array := + ((1, 1, 2), (2, 2, 3), (3, 2, 4), (4, 2, 4), + (5, 1, 5), (6, 5, 6), (7, 5, 7), (8, 6, 8), (9, 6, 9), (10, 7, 9), (11, 7, 10), + (12, 7, 7), (13, 7, 5)); + + My_Complex_Graph : constant Graphs.Graph := Graphs.To_Graph (Complex_Nodes, Complex_Edges); + + Neigh_Nodes : constant Graphs.Node_Array := (2, 3, 4, 5); + Neigh_Edges : constant Graphs.Edge_Array := + ((1, 2, 3), (2, 3, 2), (3, 3, 4), (4, 4, 5), (5, 5, 4), (6, 4, 3)); + + My_Neigh_Graph : Graphs.Graph := Graphs.To_Graph (Neigh_Nodes, Neigh_Edges); + + +private + + + generic + type Element_Type is private; + type Index_Type is (<>); + type Array_Type is array (Index_Type range <>) of Element_Type; + function Is_Permutation + (Left, Right : in Array_Type) + return Boolean; + + end Graph_Tests; diff --git a/test/test_main.adb b/test/test_main.adb index e116720..fc77c15 100644 --- a/test/test_main.adb +++ b/test/test_main.adb @@ -6,7 +6,13 @@ with Ada.Command_Line, Ada.Characters.Latin_1, Unit_Tests, - Graph_Tests.Basic; + Graph_Tests.Basic, + Graph_Tests.Inspection, + Graph_Tests.Context, + Graph_Tests.Curses, + Graph_Tests.Labels, + Graph_Tests.Modify, + Graph_Tests.Search; use @@ -45,7 +51,6 @@ begin end if; end loop; - for N in 1 .. Ada.Command_Line.Argument_Count loop if Ada.Command_Line.Argument (N) = "--verbose" then How_Verbose := Strong; @@ -54,9 +59,32 @@ begin end loop; - Put_Line ("Running basic construction and inspection tests..."); + Put_Line ("Running basic tests..."); Run_Tests (Graph_Tests.Basic.Tests, How_Verbose); - -- New_Line; + New_Line; + + Put_Line ("Running inspection tests..."); + Run_Tests (Graph_Tests.Inspection.Tests, How_Verbose); + New_Line; + + Put_Line ("Running context tests..."); + Run_Tests (Graph_Tests.Context.Tests, How_Verbose); + New_Line; + + Put_Line ("Running cursor tests..."); + Run_Tests (Graph_Tests.Curses.Tests, How_Verbose); + New_Line; + + Put_Line ("Running label tests..."); + Run_Tests (Graph_Tests.Labels.Tests, How_Verbose); + New_Line; + + Put_Line ("Running modify tests..."); + Run_Tests (Graph_Tests.Modify.Tests, How_Verbose); + New_Line; + + Put_Line ("Running search tests..."); + Run_Tests (Graph_Tests.Search.Tests, How_Verbose); end Test_Main; |