Parse_Graph behavioural unit tests implemented

1 files changed, 586 insertions, 161 deletions

diff --git a/test/rat_tests-parse_graphs.adb b/test/rat_tests-parse_graphs.adb
index 981bb2c..dce8637 100644
--- a/test/rat_tests-parse_graphs.adb
+++ b/test/rat_tests-parse_graphs.adb
@@ -1,7 +1,8 @@
 
-
+with Ada.Text_IO;
 with
 
+    Ada.Containers,
     Packrat.Traits,
     Packrat.Parse_Graphs;
 
@@ -48,11 +49,45 @@ package body Rat_Tests.Parse_Graphs is
 
 
     --  This should be set up to be identical to the example parse in the paper
-    --  on pages 168-169.
+    --  on pages 168-169, covering the sentence "i saw a man in the park with a bat".
 
     Paper_Graph : Graphs.Parse_Graph;
 
 
+    --  A simple subgraph of the above, covering the phrase "saw a man".
+
+    Small_Graph : Graphs.Parse_Graph;
+
+
+    --  A simple subgraph of the above, slid to start at position 1,
+    --  covering the phrase "in the park".
+
+    Prep_1 : My_Traits.Tokens.Token := My_Traits.Tokens.Create (Preposition, 1, "in");
+    Det_2 : My_Traits.Tokens.Token := My_Traits.Tokens.Create (Determiner, 2, "the");
+    Noun_3 : My_Traits.Tokens.Token := My_Traits.Tokens.Create (Noun, 3, "park");
+
+    NP_2 : My_Traits.Tokens.Token := My_Traits.Tokens.Create (Noun_Phrase, 2, "");
+
+    PP_1 : My_Traits.Tokens.Token := My_Traits.Tokens.Create (Prepositional_Phrase, 1, "");
+
+
+    Slide_Graph : Graphs.Parse_Graph;
+
+
+    --  A slid version of Small_Graph, covering the same "saw a man" phrase.
+
+    Verb_1 : My_Traits.Tokens.Token := My_Traits.Tokens.Create (Verb, 1, "saw");
+    Det_2a : My_Traits.Tokens.Token := My_Traits.Tokens.Create (Determiner, 2, "a");
+    Noun_3a : My_Traits.Tokens.Token := My_Traits.Tokens.Create (Noun, 3, "man");
+
+    --  NP_2 as above is fine
+
+    VP_1 : My_Traits.Tokens.Token := My_Traits.Tokens.Create (Verb_Phrase, 1, "");
+
+
+    Slid_Small_Graph : Graphs.Parse_Graph;
+
+
 
 
     function Debug_String_Check
@@ -67,27 +102,58 @@ package body Rat_Tests.Parse_Graphs is
     function Assign_Check
         return Test_Result
     is
-    begin
-        --  to-do
-        return Fail;
+        use type Graphs.Parse_Graph;
+        Copy_Graph : Graphs.Parse_Graph := Paper_Graph;
+        Assign_Graph : Graphs.Parse_Graph;
+    begin
+        if Assign_Graph = Paper_Graph or
+            Copy_Graph /= Paper_Graph
+        then
+            return Fail;
+        end if;
+        Assign_Graph.Assign (Paper_Graph);
+        if Assign_Graph /= Paper_Graph or
+            Copy_Graph /= Paper_Graph
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Assign_Check;
 
 
     function Copy_Check
         return Test_Result
     is
+        use type Graphs.Parse_Graph;
+        Copy_Graph : Graphs.Parse_Graph := Paper_Graph.Copy;
     begin
-        --  to-do
-        return Fail;
+        if Copy_Graph /= Paper_Graph then
+            return Fail;
+        end if;
+        return Pass;
     end Copy_Check;
 
 
     function Move_Check
         return Test_Result
     is
-    begin
-        --  to-do
-        return Fail;
+        use type Graphs.Parse_Graph;
+        Copy_Graph : Graphs.Parse_Graph := Paper_Graph;
+        Target_Graph : Graphs.Parse_Graph;
+    begin
+        if Target_Graph = Paper_Graph or
+            Copy_Graph /= Paper_Graph
+        then
+            return Fail;
+        end if;
+        Target_Graph.Move (Copy_Graph);
+        if Target_Graph /= Paper_Graph or
+            Copy_Graph = Paper_Graph or
+            not Copy_Graph.Is_Empty
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Move_Check;
 
 
@@ -95,20 +161,34 @@ package body Rat_Tests.Parse_Graphs is
 
 
     function Is_Empty_Check
-        return Test_Result
-    is
-    begin
-        --  to-do
-        return Fail;
+        return Test_Result is
+    begin
+        if Paper_Graph.Is_Empty or
+            Small_Graph.Is_Empty or
+            Slide_Graph.Is_Empty or
+            not Graphs.Empty_Graph.Is_Empty
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Is_Empty_Check;
 
 
     function Clear_Check
         return Test_Result
     is
+        Clear_Graph : Graphs.Parse_Graph := Paper_Graph;
     begin
-        --  to-do
-        return Fail;
+        if Clear_Graph.Is_Empty then
+            return Fail;
+        end if;
+        Clear_Graph.Clear;
+        if not Clear_Graph.Is_Empty or
+            Paper_Graph.Is_Empty
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Clear_Check;
 
 
@@ -118,63 +198,131 @@ package body Rat_Tests.Parse_Graphs is
     function Contains_Check
         return Test_Result
     is
-    begin
-        --  to-do
-        return Fail;
+        Test_Array : Graphs.Token_Group_Array :=
+            Small_Graph.Subgroups ((VP_2, 4));
+    begin
+        if Graphs.Empty_Graph.Contains (Sen_1) or
+            Paper_Graph.Contains (PP_1) or
+            not Paper_Graph.Contains (Verb_2) or
+            not Paper_Graph.Contains (Noun_7) or
+            not Paper_Graph.Contains (VP_2)
+        then
+            return Fail;
+        end if;
+        if Graphs.Empty_Graph.Contains ((Sen_1, 10)) or
+            Paper_Graph.Contains ((Sen_1, 20)) or
+            not Paper_Graph.Contains ((Sen_1, 7)) or
+            not Paper_Graph.Contains ((Det_3, 3))
+        then
+            return Fail;
+        end if;
+        if Graphs.Empty_Graph.Contains (Test_Array (1)) or
+            not Paper_Graph.Contains (Test_Array (1)) or
+            not Small_Graph.Contains (Test_Array (1)) or
+            Slide_Graph.Contains (Test_Array (1))
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Contains_Check;
 
 
     function Reachable_Check
         return Test_Result
     is
+        My_Graph : Graphs.Parse_Graph := Paper_Graph;
     begin
-        --  to-do
-        return Fail;
+        if My_Graph.Reachable ((Verb_1, 1)) or
+            My_Graph.Reachable ((Verb_2, 10)) or
+            not My_Graph.Reachable ((Noun_10, 10))
+        then
+            return Fail;
+        end if;
+        My_Graph.Set_Root (VP_2, (1 => 4));
+        if My_Graph.Reachable ((Noun_10, 10)) then
+            return Fail;
+        end if;
+        return Pass;
     end Reachable_Check;
 
 
     function All_Reachable_Check
         return Test_Result
     is
+        My_Graph : Graphs.Parse_Graph := Paper_Graph;
     begin
-        --  to-do
-        return Fail;
+        if not My_Graph.All_Reachable then
+            return Fail;
+        end if;
+        My_Graph.Set_Root (VP_2, (1 => 4));
+        if My_Graph.All_Reachable then
+            return Fail;
+        end if;
+        return Pass;
     end All_Reachable_Check;
 
 
     function Valid_Starts_Finishes_Check
-        return Test_Result
-    is
-    begin
-        --  to-do
-        return Fail;
+        return Test_Result is
+    begin
+        if Graphs.Valid_Starts_Finishes ((NP_3, 4),
+               ((Noun_1, 1), (Noun_4, 4), (Noun_10, 10))) or
+            Graphs.Valid_Starts_Finishes ((VP_2, 8),
+               ((NP_3, 4), (Det_3, 3))) or
+            not Graphs.Valid_Starts_Finishes ((NP_1, 1),
+               (1 => (Noun_1, 1)))
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Valid_Starts_Finishes_Check;
 
 
     function No_Loops_Introduced_Check
         return Test_Result
     is
+        My_Graph : Graphs.Parse_Graph := Paper_Graph;
     begin
-        --  to-do
-        return Fail;
+        if My_Graph.No_Loops_Introduced ((Sen_1, 4), (1 => (Sen_1, 4))) or
+            not My_Graph.No_Loops_Introduced ((Sen_1, 4), (1 => (NP_1, 4)))
+        then
+            return Fail;
+        end if;
+        My_Graph.Connect ((Sen_1, 4), (1 => (NP_1, 4)));
+        if My_Graph.No_Loops_Introduced ((NP_1, 4), (1 => (Sen_1, 4))) then
+            return Fail;
+        end if;
+        return Pass;
     end No_Loops_Introduced_Check;
 
 
     function Is_Sorted_Check
         return Test_Result
     is
+        Test_1 : Graphs.Finish_Array := (1, 3, 5, 6, 7, 11);
+        Test_2 : Graphs.Finish_Array := (3, 5, 2, 8, 4, 10);
     begin
-        --  to-do
-        return Fail;
+        if not Graphs.Is_Sorted (Test_1) or
+            Graphs.Is_Sorted (Test_2)
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Is_Sorted_Check;
 
 
     function No_Duplicates_Check
         return Test_Result
     is
+        Test_1 : Graphs.Finish_Array := (1, 2, 3, 4, 8, 10, 5);
+        Test_2 : Graphs.Finish_Array := (5, 6, 8, 2, 4, 5, 5, 8);
     begin
-        --  to-do
-        return Fail;
+        if not Graphs.No_Duplicates (Test_1) or
+            Graphs.No_Duplicates (Test_2)
+        then
+            return Fail;
+        end if;
+        return Pass;
     end No_Duplicates_Check;
 
 
@@ -184,36 +332,87 @@ package body Rat_Tests.Parse_Graphs is
     function Include_Check
         return Test_Result
     is
+        My_Graph : Graphs.Parse_Graph := Small_Graph;
     begin
-        --  to-do
-        return Fail;
+        if My_Graph.Contains (Noun_7) then
+            return Fail;
+        end if;
+        My_Graph.Include (Noun_7);
+        if not My_Graph.Contains (Noun_7) then
+            return Fail;
+        end if;
+        return Pass;
     end Include_Check;
 
 
     function Connect_Check
         return Test_Result
     is
-    begin
-        --  to-do
-        return Fail;
+        use type Ada.Containers.Count_Type;
+        My_Graph : Graphs.Parse_Graph;
+    begin
+        My_Graph.Include (Sen_1);
+        My_Graph.Include (Noun_1);
+        My_Graph.Include (Verb_2);
+        My_Graph.Set_Root (Sen_1, (1 => 2));
+        if My_Graph.All_Reachable then
+            return Fail;
+        end if;
+        My_Graph.Connect ((Sen_1, 2), ((Noun_1, 1), (Verb_2, 2)));
+        if not My_Graph.All_Reachable or
+            Graphs.Length (My_Graph.Subgroups ((Sen_1, 2)) (1)) /= 2
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Connect_Check;
 
 
     function Prune_Check
         return Test_Result
     is
-    begin
-        --  to-do
-        return Fail;
+        use type My_Traits.Tokens.Token;
+        use type Graphs.Finish_Array;
+        Paper : Graphs.Parse_Graph := Paper_Graph;
+    begin
+        if not Paper.Contains (Prep_5) then
+            return Fail;
+        end if;
+        Paper.Prune (Prep_5);
+        if Paper.Contains (Prep_5) or
+            Graphs.Element (Paper.Subgroups ((PP_5, 7)) (1), 1).Token = Prep_5
+        then
+            return Fail;
+        end if;
+        if Paper.Root_Finish_List /= (4, 7, 10) then
+            return Fail;
+        end if;
+        Paper.Prune ((Sen_1, 7));
+        if Paper.Root_Finish_List /= (4, 10) then
+            return Fail;
+        end if;
+        Paper.Prune (Paper.Subgroups ((NP_1, 1)) (1));
+        if Paper.Subgroups ((NP_1, 1))'Length > 0 then
+            return Fail;
+        end if;
+        return Pass;
     end Prune_Check;
 
 
     function Delete_Unreachable_Check
         return Test_Result
     is
+        My_Graph : Graphs.Parse_Graph := Paper_Graph;
     begin
-        --  to-do
-        return Fail;
+        My_Graph.Set_Root (VP_2, (1 => 4));
+        if My_Graph.All_Reachable then
+            return Fail;
+        end if;
+        My_Graph.Delete_Unreachable;
+        if not My_Graph.All_Reachable then
+            return Fail;
+        end if;
+        return Pass;
     end Delete_Unreachable_Check;
 
 
@@ -221,56 +420,88 @@ package body Rat_Tests.Parse_Graphs is
 
 
     function Has_Root_Check
-        return Test_Result
-    is
-    begin
-        --  to-do
-        return Fail;
+        return Test_Result is
+    begin
+        if not Paper_Graph.Has_Root or
+            not Small_Graph.Has_Root or
+            not Slide_Graph.Has_Root or
+            Graphs.Empty_Graph.Has_Root
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Has_Root_Check;
 
 
     function Set_Root_Check
         return Test_Result
     is
+        My_Graph : Graphs.Parse_Graph := Paper_Graph;
     begin
-        --  to-do
-        return Fail;
+        My_Graph.Clear_Root;
+        My_Graph.Set_Root (Sen_1, (4, 7, 10));
+        if not My_Graph.Has_Root then
+            return Fail;
+        end if;
+        return Pass;
     end Set_Root_Check;
 
 
     function Clear_Root_Check
         return Test_Result
     is
+        My_Graph : Graphs.Parse_Graph := Paper_Graph;
     begin
-        --  to-do
-        return Fail;
+        My_Graph.Clear_Root;
+        if My_Graph.Has_Root or
+            not Paper_Graph.Has_Root
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Clear_Root_Check;
 
 
     function Root_Token_Check
         return Test_Result
     is
+        use type My_Traits.Tokens.Token;
     begin
-        --  to-do
-        return Fail;
+        if Paper_Graph.Root_Token /= Sen_1 or
+            Small_Graph.Root_Token /= VP_2 or
+            Slide_Graph.Root_Token /= PP_1
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Root_Token_Check;
 
 
     function Root_Finish_List_Check
         return Test_Result
     is
+        use type Graphs.Finish_Array;
     begin
-        --  to-do
-        return Fail;
+        if Paper_Graph.Root_Finish_List /= (4, 7, 10) or
+            Small_Graph.Root_Finish_List /= (1 => 4)
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Root_Finish_List_Check;
 
 
     function Root_Element_Check
         return Test_Result
     is
+        use type Graphs.Finished_Token;
     begin
-        --  to-do
-        return Fail;
+        if Paper_Graph.Root_Element (4) /= (Sen_1, 4) or
+            Paper_Graph.Root_Element (10) /= (Sen_1, 10)
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Root_Element_Check;
 
 
@@ -280,27 +511,44 @@ package body Rat_Tests.Parse_Graphs is
     function Finish_List_Check
         return Test_Result
     is
+        use type Graphs.Finish_Array;
     begin
-        --  to-do
-        return Fail;
+        if Paper_Graph.Finish_List (Sen_1) /= (4, 7, 10) or
+            Paper_Graph.Finish_List (NP_3) /= (4, 7, 10) or
+            Paper_Graph.Finish_List (NP_6) /= (7, 10) or
+            Paper_Graph.Finish_List (NP_1) /= (1 => 1) or
+            Paper_Graph.Finish_List (Noun_4)'Length /= 0
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Finish_List_Check;
 
 
     function Is_Leaf_Check
-        return Test_Result
-    is
-    begin
-        --  to-do
-        return Fail;
+        return Test_Result is
+    begin
+        if Paper_Graph.Is_Leaf ((NP_1, 1)) or
+            Paper_Graph.Is_Leaf ((VP_2, 7)) or
+            not Paper_Graph.Is_Leaf ((Noun_4, 4))
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Is_Leaf_Check;
 
 
     function Is_Branch_Check
-        return Test_Result
-    is
-    begin
-        --  to-do
-        return Fail;
+        return Test_Result is
+    begin
+        if Paper_Graph.Is_Branch ((Noun_7, 7)) or
+            Paper_Graph.Is_Branch ((Verb_2, 2)) or
+            not Paper_Graph.Is_Branch ((Sen_1, 7)) or
+            not Paper_Graph.Is_Branch ((NP_1, 1))
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Is_Branch_Check;
 
 
@@ -310,72 +558,174 @@ package body Rat_Tests.Parse_Graphs is
     function Subgroups_Check
         return Test_Result
     is
-    begin
-        --  to-do
-        return Fail;
+        use type Ada.Containers.Count_Type;
+        use type Graphs.Finished_Token_Array;
+        Paper : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((NP_3, 10));
+        Extra : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((NP_1, 1));
+    begin
+        if Paper'Length /= 2 or
+            Extra'Length /= 1
+        then
+            return Fail;
+        end if;
+        if Graphs.Length (Paper (1)) /= 2 or
+            Graphs.Length (Paper (2)) /= 2 or
+            Graphs.Length (Extra (1)) /= 1
+        then
+            return Fail;
+        end if;
+        if Graphs.Elements (Paper (1)) /= ((NP_3, 4), (PP_5, 10)) or
+            Graphs.Elements (Paper (2)) /= ((NP_3, 7), (PP_8, 10))
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Subgroups_Check;
 
 
     function First_Index_Check
         return Test_Result
     is
-    begin
-        --  to-do
-        return Fail;
+        Paper_1 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((Sen_1, 4));
+        Paper_2 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((NP_3, 10));
+        Small_1 : Graphs.Token_Group_Array := Small_Graph.Subgroups ((Verb_2, 2));
+        Slide_1 : Graphs.Token_Group_Array := Slide_Graph.Subgroups ((NP_2, 3));
+    begin
+        --  All Token_Group_Arrays returned from Subgroups are 1-indexed.
+        for Group of Paper_1 loop
+            if Graphs.First_Index (Group) /= 1 then
+                return Fail;
+            end if;
+        end loop;
+        for Group of Paper_2 loop
+            if Graphs.First_Index (Group) /= 1 then
+                return Fail;
+            end if;
+        end loop;
+        for Group of Small_1 loop
+            if Graphs.First_Index (Group) /= 1 then
+                return Fail;
+            end if;
+        end loop;
+        for Group of Slide_1 loop
+            if Graphs.First_Index (Group) /= 1 then
+                return Fail;
+            end if;
+        end loop;
+        return Pass;
     end First_Index_Check;
 
 
     function Last_Index_Check
         return Test_Result
     is
-    begin
-        --  to-do
-        return Fail;
+        Paper_1 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((Sen_1, 4));
+        Paper_2 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((NP_3, 10));
+        Paper_3 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((NP_1, 1));
+        Slide_1 : Graphs.Token_Group_Array := Slide_Graph.Subgroups ((NP_2, 3));
+    begin
+        if Graphs.Last_Index (Paper_1 (1)) /= 2 or
+            Graphs.Last_Index (Paper_2 (1)) /= 2 or
+            Graphs.Last_Index (Paper_2 (2)) /= 2 or
+            Graphs.Last_Index (Paper_3 (1)) /= 1 or
+            Graphs.Last_Index (Slide_1 (1)) /= 2
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Last_Index_Check;
 
 
     function Length_Check
         return Test_Result
     is
-    begin
-        --  to-do
-        return Fail;
+        Paper_1 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((Sen_1, 4));
+        Paper_2 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((NP_3, 10));
+        Paper_3 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((NP_1, 1));
+        Slide_1 : Graphs.Token_Group_Array := Slide_Graph.Subgroups ((NP_2, 3));
+    begin
+        --  Since all Token_Groups are 1-indexed the length equals the last index
+        if Graphs.Last_Index (Paper_1 (1)) /= 2 or
+            Graphs.Last_Index (Paper_2 (1)) /= 2 or
+            Graphs.Last_Index (Paper_2 (2)) /= 2 or
+            Graphs.Last_Index (Paper_3 (1)) /= 1 or
+            Graphs.Last_Index (Slide_1 (1)) /= 2
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Length_Check;
 
 
     function Element_Check
         return Test_Result
     is
+        use type Graphs.Finished_Token;
+        Paper : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((NP_3, 10));
     begin
-        --  to-do
-        return Fail;
+        if Graphs.Element (Paper (1), 1) /= (NP_3, 4) or
+            Graphs.Element (Paper (2), 2) /= (PP_8, 10)
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Element_Check;
 
 
     function Elements_Check
         return Test_Result
     is
+        use type Graphs.Finished_Token_Array;
+        Paper : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((NP_3, 10));
     begin
-        --  to-do
-        return Fail;
+        if Graphs.Elements (Paper (1)) /= ((NP_3, 4), (PP_5, 10)) or
+            Graphs.Elements (Paper (2)) /= ((NP_3, 7), (PP_8, 10))
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Elements_Check;
 
 
     function Parent_Check
         return Test_Result
     is
-    begin
-        --  to-do
-        return Fail;
+        use type Graphs.Finished_Token;
+        Paper_1 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((Sen_1, 4));
+        Paper_2 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((NP_3, 10));
+        Paper_3 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((NP_1, 1));
+        Slide_1 : Graphs.Token_Group_Array := Slide_Graph.Subgroups ((NP_2, 3));
+    begin
+        if Graphs.Parent (Paper_1 (1)) /= (Sen_1, 4) or
+            Graphs.Parent (Paper_2 (1)) /= (NP_3, 10) or
+            Graphs.Parent (Paper_2 (2)) /= (NP_3, 10) or
+            Graphs.Parent (Paper_3 (1)) /= (NP_1, 1) or
+            Graphs.Parent (Slide_1 (1)) /= (NP_2, 3)
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Parent_Check;
 
 
     function Finish_Check
         return Test_Result
     is
-    begin
-        --  to-do
-        return Fail;
+        use type Graphs.Finish_Type;
+        Paper_1 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((Sen_1, 4));
+        Paper_2 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((NP_3, 10));
+        Paper_3 : Graphs.Token_Group_Array := Paper_Graph.Subgroups ((NP_1, 1));
+        Slide_1 : Graphs.Token_Group_Array := Slide_Graph.Subgroups ((NP_2, 3));
+    begin
+        if Graphs.Finish (Paper_1 (1)) /= 4 or
+            Graphs.Finish (Paper_2 (1)) /= 10 or
+            Graphs.Finish (Paper_2 (2)) /= 10 or
+            Graphs.Finish (Paper_3 (1)) /= 1 or
+            Graphs.Finish (Slide_1 (1)) /= 3
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Finish_Check;
 
 
@@ -383,29 +733,61 @@ package body Rat_Tests.Parse_Graphs is
 
 
     function Is_Root_Ambiguous_Check
-        return Test_Result
-    is
-    begin
-        --  to-do
-        return Fail;
+        return Test_Result is
+    begin
+        if Graphs.Empty_Graph.Is_Root_Ambiguous or
+            not Paper_Graph.Is_Root_Ambiguous or
+            Small_Graph.Is_Root_Ambiguous or
+            Slide_Graph.Is_Root_Ambiguous
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Is_Root_Ambiguous_Check;
 
 
     function Is_Ambiguous_Check
-        return Test_Result
-    is
-    begin
-        --  to-do
-        return Fail;
+        return Test_Result is
+    begin
+        if Graphs.Empty_Graph.Is_Ambiguous or
+            not Paper_Graph.Is_Ambiguous or
+            Small_Graph.Is_Ambiguous or
+            Slide_Graph.Is_Ambiguous
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Is_Ambiguous_Check;
 
 
     function Ambiguities_Check
         return Test_Result
     is
+        use type Graphs.Finished_Token_Array;
+
+        Paper_Root, Small_Root, Slide_Root : Boolean;
+
+        Paper_Result : Graphs.Finished_Token_Array :=
+            Paper_Graph.Ambiguities (Paper_Root);
+        Small_Result : Graphs.Finished_Token_Array :=
+            Small_Graph.Ambiguities (Small_Root);
+        Slide_Result : Graphs.Finished_Token_Array :=
+            Slide_Graph.Ambiguities (Slide_Root);
+
+        --  Result is expected to be sorted
+        Expected_Paper_Result : Graphs.Finished_Token_Array :=
+           ((Sen_1, 7), (Sen_1, 10), (NP_3, 10));
     begin
-        --  to-do
-        return Fail;
+        if Paper_Result /= Expected_Paper_Result or
+            Small_Result'Length /= 0 or
+            Slide_Result'Length /= 0 or
+            not Paper_Root or
+            Small_Root or
+            Slide_Root
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Ambiguities_Check;
 
 
@@ -413,20 +795,29 @@ package body Rat_Tests.Parse_Graphs is
 
 
     function Isomorphic_Check
-        return Test_Result
-    is
-    begin
-        --  to-do
-        return Fail;
+        return Test_Result is
+    begin
+        if Paper_Graph.Isomorphic (Small_Graph) or
+            Small_Graph.Isomorphic (Slide_Graph) or
+            not Small_Graph.Isomorphic (Slid_Small_Graph)
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Isomorphic_Check;
 
 
     function Isomorphic_Subgraph_Check
-        return Test_Result
-    is
-    begin
-        --  to-do
-        return Fail;
+        return Test_Result is
+    begin
+        if not Graphs.Isomorphic_Subgraph (Paper_Graph, (VP_2, 4), Small_Graph, (VP_2, 4)) or
+            not Graphs.Isomorphic_Subgraph (Paper_Graph, (VP_2, 4), Slid_Small_Graph, (VP_1, 3)) or
+            not Graphs.Isomorphic_Subgraph (Paper_Graph, (PP_5, 7), Slide_Graph, (PP_1, 3)) or
+            Graphs.Isomorphic_Subgraph (Small_Graph, (VP_2, 4), Slide_Graph, (PP_1, 3))
+        then
+            return Fail;
+        end if;
+        return Pass;
     end Isomorphic_Subgraph_Check;
 
 
@@ -435,51 +826,85 @@ begin
 
     --  Constructing the various test graphs
 
-    Paper_Graph.Connect ((NP_1, 2),
-       (1 => Graphs.Finished_Token'(Noun_1, 2)));
-    Paper_Graph.Connect ((NP_3, 5),
-       ((Det_3, 4), (Noun_4, 5)));
-    Paper_Graph.Connect ((NP_3, 8),
-       ((NP_3, 5), (PP_5, 8)));
-    Paper_Graph.Connect ((NP_3, 11),
-       ((NP_3, 5), (PP_5, 11)));
-    Paper_Graph.Connect ((NP_3, 11),
-       ((NP_3, 8), (PP_8, 11)));
-    Paper_Graph.Connect ((NP_6, 8),
-       ((Det_6, 7), (Noun_7, 8)));
-    Paper_Graph.Connect ((NP_6, 11),
-       ((NP_6, 8), (PP_8, 11)));
-    Paper_Graph.Connect ((NP_9, 11),
-       ((Det_9, 10), (Noun_10, 11)));
-
-    Paper_Graph.Connect ((PP_5, 8),
-       ((Prep_5, 6), (NP_6, 8)));
-    Paper_Graph.Connect ((PP_5, 11),
-       ((Prep_5, 6), (NP_6, 11)));
-    Paper_Graph.Connect ((PP_8, 11),
-       ((Prep_8, 9), (NP_9, 11)));
-
-    Paper_Graph.Connect ((VP_2, 5),
-       ((Verb_2, 3), (NP_3, 5)));
-    Paper_Graph.Connect ((VP_2, 8),
-       ((Verb_2, 3), (NP_3, 8)));
-    Paper_Graph.Connect ((VP_2, 11),
-       ((Verb_2, 3), (NP_3, 11)));
-
-    Paper_Graph.Connect ((Sen_1, 5),
-       ((NP_1, 2), (VP_2, 5)));
-    Paper_Graph.Connect ((Sen_1, 8),
-       ((NP_1, 2), (VP_2, 8)));
-    Paper_Graph.Connect ((Sen_1, 8),
-       ((Sen_1, 5), (PP_5, 8)));
-    Paper_Graph.Connect ((Sen_1, 11),
-       ((NP_1, 2), (VP_2, 11)));
-    Paper_Graph.Connect ((Sen_1, 11),
-       ((Sen_1, 5), (PP_5, 11)));
-    Paper_Graph.Connect ((Sen_1, 11),
-       ((Sen_1, 8), (PP_8, 11)));
-
-    Paper_Graph.Set_Root (Sen_1, (5, 8, 11));
+    Paper_Graph.Connect ((NP_1, 1),
+       (1 => Graphs.Finished_Token'(Noun_1, 1)));
+    Paper_Graph.Connect ((NP_3, 4),
+       ((Det_3, 3), (Noun_4, 4)));
+    Paper_Graph.Connect ((NP_3, 7),
+       ((NP_3, 4), (PP_5, 7)));
+    Paper_Graph.Connect ((NP_3, 10),
+       ((NP_3, 4), (PP_5, 10)));
+    Paper_Graph.Connect ((NP_3, 10),
+       ((NP_3, 7), (PP_8, 10)));
+    Paper_Graph.Connect ((NP_6, 7),
+       ((Det_6, 6), (Noun_7, 7)));
+    Paper_Graph.Connect ((NP_6, 10),
+       ((NP_6, 7), (PP_8, 10)));
+    Paper_Graph.Connect ((NP_9, 10),
+       ((Det_9, 9), (Noun_10, 10)));
+
+    Paper_Graph.Connect ((PP_5, 7),
+       ((Prep_5, 5), (NP_6, 7)));
+    Paper_Graph.Connect ((PP_5, 10),
+       ((Prep_5, 5), (NP_6, 10)));
+    Paper_Graph.Connect ((PP_8, 10),
+       ((Prep_8, 8), (NP_9, 10)));
+
+    Paper_Graph.Connect ((VP_2, 4),
+       ((Verb_2, 2), (NP_3, 4)));
+    Paper_Graph.Connect ((VP_2, 7),
+       ((Verb_2, 2), (NP_3, 7)));
+    Paper_Graph.Connect ((VP_2, 10),
+       ((Verb_2, 2), (NP_3, 10)));
+
+    Paper_Graph.Connect ((Sen_1, 4),
+       ((NP_1, 1), (VP_2, 4)));
+    Paper_Graph.Connect ((Sen_1, 7),
+       ((NP_1, 1), (VP_2, 7)));
+    Paper_Graph.Connect ((Sen_1, 7),
+       ((Sen_1, 4), (PP_5, 7)));
+    Paper_Graph.Connect ((Sen_1, 10),
+       ((NP_1, 1), (VP_2, 10)));
+    Paper_Graph.Connect ((Sen_1, 10),
+       ((Sen_1, 4), (PP_5, 10)));
+    Paper_Graph.Connect ((Sen_1, 10),
+       ((Sen_1, 7), (PP_8, 10)));
+
+    --  i saw a man in the park with a bat
+    Paper_Graph.Set_Root (Sen_1, (4, 7, 10));
+
+
+
+
+    Small_Graph.Connect ((NP_3, 4),
+       ((Det_3, 3), (Noun_4, 4)));
+    Small_Graph.Connect ((VP_2, 4),
+       ((Verb_2, 2), (NP_3, 4)));
+
+    --  saw a man
+    Small_Graph.Set_Root (VP_2, (1 => 4));
+
+
+
+
+    Slide_Graph.Connect ((NP_2, 3),
+       ((Det_2, 2), (Noun_3, 3)));
+    Slide_Graph.Connect ((PP_1, 3),
+       ((Prep_1, 1), (NP_2, 3)));
+
+    --  in the park
+    Slide_Graph.Set_Root (PP_1, (1 => 3));
+
+
+
+
+    Slid_Small_Graph.Connect ((NP_2, 3),
+       ((Det_2a, 2), (Noun_3a, 3)));
+    Slid_Small_Graph.Connect ((VP_1, 3),
+       ((Verb_1, 1), (NP_2, 3)));
+
+    --  saw a man
+    Slid_Small_Graph.Set_Root (VP_1, (1 => 3));
 
 
 end Rat_Tests.Parse_Graphs;