note description: "Basic tests for GRAPH[V]" author: "JSO" date: "$Date$" revision: "$Revision$" class TEST_GRAPH_BASIC create make feature {NONE} -- Initialization default_create -- Process instances of classes with no creation clause. -- (Default: do nothing.) -- (from ANY) do end make -- initialize tests do add_boolean_case (agent t0) add_boolean_case (agent t1) add_boolean_case (agent t2) add_boolean_case (agent t3) add_boolean_case (agent t4) add_boolean_case (agent t5) add_boolean_case (agent t6) add_boolean_case (agent t7) add_boolean_case (agent t8) add_boolean_case (agent t9) add_boolean_case (agent t10) add_boolean_case (agent t11) add_boolean_case (agent t12) add_boolean_case (agent t13) add_boolean_case (agent t14) add_boolean_case (agent t15a) add_boolean_case (agent t15b) add_boolean_case (agent t16) add_boolean_case (agent t17) add_boolean_case (agent t18) add_boolean_case (agent t19) add_boolean_case (agent t20) add_boolean_case (agent t21a) add_boolean_case (agent t21b) add_boolean_case (agent t21c) end feature {NONE} -- Access Execution_environment: EXECUTION_ENVIRONMENT -- An execution environment object. -- (from SHARED_EXECUTION_ENVIRONMENT) once create Result end feature -- Access generating_type: TYPE [detachable TEST_GRAPH_BASIC] -- Type of current object -- (type of which it is a direct instance) -- (from ANY) external "built_in" ensure -- from ANY generating_type_not_void: Result /= Void end generator: STRING_8 -- Name of current object's generating class -- (base class of the type of which it is a direct instance) -- (from ANY) external "built_in" ensure -- from ANY generator_not_void: Result /= Void generator_not_empty: not Result.is_empty end feature -- Comparison frozen deep_equal (a: detachable ANY; b: like arg #1): BOOLEAN -- Are a and b either both void -- or attached to isomorphic object structures? -- (from ANY) do if a = Void then Result := b = Void else Result := b /= Void and then a.is_deep_equal (b) end ensure -- from ANY instance_free: class shallow_implies_deep: standard_equal (a, b) implies Result both_or_none_void: (a = Void) implies (Result = (b = Void)) same_type: (Result and (a /= Void)) implies (b /= Void and then a.same_type (b)) symmetric: Result implies deep_equal (b, a) end frozen equal (a: detachable ANY; b: like arg #1): BOOLEAN -- Are a and b either both void or attached -- to objects considered equal? -- (from ANY) do if a = Void then Result := b = Void else Result := b /= Void and then a.is_equal (b) end ensure -- from ANY instance_free: class definition: Result = (a = Void and b = Void) or else ((a /= Void and b /= Void) and then a.is_equal (b)) end frozen is_deep_equal (other: TEST_GRAPH_BASIC): BOOLEAN -- Are Current and other attached to isomorphic object structures? -- (from ANY) require -- from ANY other_not_void: other /= Void external "built_in" ensure -- from ANY shallow_implies_deep: standard_is_equal (other) implies Result same_type: Result implies same_type (other) symmetric: Result implies other.is_deep_equal (Current) end is_equal (other: TEST_GRAPH_BASIC): BOOLEAN -- Is other attached to an object considered -- equal to current object? -- (from ANY) require -- from ANY other_not_void: other /= Void external "built_in" ensure -- from ANY symmetric: Result implies other ~ Current consistent: standard_is_equal (other) implies Result end frozen standard_equal (a: detachable ANY; b: like arg #1): BOOLEAN -- Are a and b either both void or attached to -- field-by-field identical objects of the same type? -- Always uses default object comparison criterion. -- (from ANY) do if a = Void then Result := b = Void else Result := b /= Void and then a.standard_is_equal (b) end ensure -- from ANY instance_free: class definition: Result = (a = Void and b = Void) or else ((a /= Void and b /= Void) and then a.standard_is_equal (b)) end frozen standard_is_equal (other: TEST_GRAPH_BASIC): BOOLEAN -- Is other attached to an object of the same type -- as current object, and field-by-field identical to it? -- (from ANY) require -- from ANY other_not_void: other /= Void external "built_in" ensure -- from ANY same_type: Result implies same_type (other) symmetric: Result implies other.standard_is_equal (Current) end feature -- Status report conforms_to (other: ANY): BOOLEAN -- Does type of current object conform to type -- of other (as per Eiffel: The Language, chapter 13)? -- (from ANY) require -- from ANY other_not_void: other /= Void external "built_in" end same_type (other: ANY): BOOLEAN -- Is type of current object identical to type of other? -- (from ANY) require -- from ANY other_not_void: other /= Void external "built_in" ensure -- from ANY definition: Result = (conforms_to (other) and other.conforms_to (Current)) end feature -- Duplication frozen clone (other: detachable ANY): like other obsolete "Use `twin' instead. [2017-05-31]" -- Void if other is void; otherwise new object -- equal to other -- -- For non-void other, clone calls copy; -- to change copying/cloning semantics, redefine copy. -- (from ANY) do if other /= Void then Result := other.twin end ensure -- from ANY instance_free: class equal: Result ~ other end copy (other: TEST_GRAPH_BASIC) -- Update current object using fields of object attached -- to other, so as to yield equal objects. -- (from ANY) require -- from ANY other_not_void: other /= Void type_identity: same_type (other) external "built_in" ensure -- from ANY is_equal: Current ~ other end frozen deep_clone (other: detachable ANY): like other obsolete "Use `deep_twin' instead. [2017-05-31]" -- Void if other is void: otherwise, new object structure -- recursively duplicated from the one attached to other -- (from ANY) do if other /= Void then Result := other.deep_twin end ensure -- from ANY instance_free: class deep_equal: deep_equal (other, Result) end frozen deep_copy (other: TEST_GRAPH_BASIC) -- Effect equivalent to that of: -- copy (other . deep_twin) -- (from ANY) require -- from ANY other_not_void: other /= Void do copy (other.deep_twin) ensure -- from ANY deep_equal: deep_equal (Current, other) end frozen deep_twin: TEST_GRAPH_BASIC -- New object structure recursively duplicated from Current. -- (from ANY) external "built_in" ensure -- from ANY deep_twin_not_void: Result /= Void deep_equal: deep_equal (Current, Result) end frozen standard_clone (other: detachable ANY): like other obsolete "Use `standard_twin' instead. [2017-05-31]" -- Void if other is void; otherwise new object -- field-by-field identical to other. -- Always uses default copying semantics. -- (from ANY) do if other /= Void then Result := other.standard_twin end ensure -- from ANY instance_free: class equal: standard_equal (Result, other) end frozen standard_copy (other: TEST_GRAPH_BASIC) -- Copy every field of other onto corresponding field -- of current object. -- (from ANY) require -- from ANY other_not_void: other /= Void type_identity: same_type (other) external "built_in" ensure -- from ANY is_standard_equal: standard_is_equal (other) end frozen standard_twin: TEST_GRAPH_BASIC -- New object field-by-field identical to other. -- Always uses default copying semantics. -- (from ANY) external "built_in" ensure -- from ANY standard_twin_not_void: Result /= Void equal: standard_equal (Result, Current) end frozen twin: TEST_GRAPH_BASIC -- New object equal to Current -- twin calls copy; to change copying/twinning semantics, redefine copy. -- (from ANY) external "built_in" ensure -- from ANY twin_not_void: Result /= Void is_equal: Result ~ Current end feature -- Basic operations add_boolean_case (v: PREDICATE) -- Add boolean function v. -- (from ES_TEST) require -- from ES_TEST v_valid: v /= Void do if cases = Void then initialize end if attached cases as cases1 then cases1.extend (create {ES_BOOLEAN_TEST_CASE}.make ("", v)) end end add_violation_case (v: PROCEDURE) -- Add boolean function v. -- (from ES_TEST) require -- from ES_TEST v_valid: v /= Void do if cases = Void then initialize end if attached cases as cases1 then cases1.extend (create {ES_VIOLATION_CASE}.make ("", v)) end end add_violation_case_with_tag (expected_tag: STRING_8; v: PROCEDURE) -- Add boolean function v. -- (from ES_TEST) require -- from ES_TEST v_valid: v /= Void do if cases = Void then initialize end if attached cases as cases1 then cases1.extend (create {ES_VIOLATION_CASE}.make_with_tag ("", v, expected_tag)) end end frozen as_attached: attached TEST_GRAPH_BASIC obsolete "Remove calls to this feature. [2017-05-31]" -- Attached version of Current. -- (Can be used during transitional period to convert -- non-void-safe classes to void-safe ones.) -- (from ANY) do Result := Current end frozen default: detachable TEST_GRAPH_BASIC -- Default value of object's type -- (from ANY) do end frozen default_pointer: POINTER -- Default value of type POINTER -- (Avoid the need to write p.default for -- some p of type POINTER.) -- (from ANY) do ensure -- from ANY instance_free: class end default_rescue -- Process exception for routines with no Rescue clause. -- (Default: do nothing.) -- (from ANY) do end frozen do_nothing -- Execute a null action. -- (from ANY) do ensure -- from ANY instance_free: class end feature {ES_SUITE} case_name: STRING_8 -- (from ES_TEST) attribute Result := "" end count: INTEGER_32 -- Number of test cases in Current. -- (from ES_TEST) do check attached cases as cases1 then Result := cases1.count end end create_case_name (case: ES_TEST_CASE; unkn: CELL [INTEGER_32]) -- (from ES_TEST) local ls: LIST [STRING_8] do ls := case.case_name.split (':'.to_character_32) if not case.case_name.has (':') or ls.is_empty then unkn.put (unkn.item + 1) case_name := "unknown_" + unkn.item.out + " -- use ':' in a `comment' in the test case" else case_name := ls.first end if attached name as n then case_name := n + "." + case_name end end failed_cases: LIST [STRING_8] -- List of the name of all the failed test cases. -- (from ES_TEST) local failed: ARRAYED_LIST [STRING_8] unkn: CELL [INTEGER_32] do create failed.make (10) create unkn.put (0) if attached cases as cases1 then across cases1 as it loop create_case_name (it.item, unkn) if not it.item.passed then failed.extend (case_name) end end end Result := failed end get_test_name: STRING_8 -- Get unit test name. -- (from ES_TEST) do if name /= Void then check attached name as n then Result := n end else Result := "default_name" end end initialize -- Initialize Current. -- (from ES_TEST) do create cases.make name := generating_type.name.as_string_8 create descriptions.make end passed_cases: LIST [STRING_8] -- List of the name of all the successful test cases. -- (from ES_TEST) local success: ARRAYED_LIST [STRING_8] unkn: CELL [INTEGER_32] do create success.make (10) create unkn.put (0) if attached cases as cases1 then across cases1 as it loop create_case_name (it.item, unkn) if it.item.passed then success.extend (case_name) end end end Result := success end run_es_test -- Run tests in cases. -- (from ES_TEST) local problem: BOOLEAN last_index: INTEGER_32 do if attached cases as cases1 then if not problem then number_of_tests := 0 number_passed_tests := 0 check attached get_test_name as test_name then safe_put_string (test_name + "%N") end else safe_put_string ("***FAILED Problem in 'setup' or 'teardown' features%N") if show_err then check attached cases1.item as item1 attached item1.exception_trace as et then safe_put_string ("%N" + et + "%N") end end end from if not problem then cases1.start else if cases1.valid_cursor_index (last_index) then cases1.go_i_th (last_index) end end until cases1.after loop class_variable_comment_string := "no comment" setup check attached cases1.item as item1 then item1.run teardown check attached class_variable_comment_string as cvc then item1.set_case_name (cvc) end check attached to_message_string (item1) as ms then safe_put_string (ms + "%N") end number_of_tests := number_of_tests + 1 if item1.passed then number_passed_tests := number_passed_tests + 1 end end cases1.forth end end to_html (get_html_name) check_browser rescue check attached cases as cases1 then problem := True cases1.forth last_index := cases1.index retry end end to_html (output_file_name: STRING_8) -- Generate HTML report with details. -- (from ES_TEST) require -- from ES_TEST output_file_name_valid: output_file_name /= Void local gen: ES_SUITE do create gen gen.add_test (Current) gen.pass_values (show_err, browser, name) gen.to_html (output_file_name) end to_message_string (item: ES_TEST_CASE): STRING_8 -- Text represenation of a test case. -- (from ES_TEST) require -- from ES_TEST arg_not_void: item /= Void do check attached cases as cases1 then create Result.make_empty if item.passed then Result.append_string (" PASSED ") else Result.append_string ("***FAILED ") end check attached cases1.item as item1 then if item.contract_violated then check attached item1.meaning (item1.violation_type) as meaning then Result.append_string ("VIOL " + "#" + meaning + "#") end else Result.append_string ("NO VIOL ") end Result.append_string (item1.case_name) if show_err then check attached item1.violation_tag as tag then Result.append_string ("%N" + tag) end end end end ensure -- from ES_TEST result_not_void: Result /= Void result_not_empty: not Result.is_empty end feature browser: BOOLEAN -- (from ES_TESTABLE) check_browser -- Run the browser on the generated HTML. -- (from ES_TESTABLE) do check attached get_html_name end if browser then if {PLATFORM}.is_windows then Execution_environment.launch ("%"explorer%" " + get_html_name + "%"") elseif {PLATFORM}.is_mac then Execution_environment.launch ("open" + " '" + get_html_name + "'") else check {PLATFORM}.is_unix end Execution_environment.launch ("xdg-open" + " '" + get_html_name + "'") end end end curr_os_dir_separator: CHARACTER_8 -- Return path separator for current OS. -- (from ES_TESTABLE) do Result := (create {OPERATING_ENVIRONMENT}).Directory_separator ensure -- from ES_TESTABLE separator_is_a_slash: Result = '/' or Result = '\' end default_html_name: detachable STRING_8 -- (from ES_TESTABLE) get_html_name: STRING_8 -- Return the name of the default html for this unit test. -- (from ES_TESTABLE) do if default_html_name /= Void then check attached default_html_name as d then Result := d.twin end else Result := (generating_type.name + ".html").as_string_8 end end number_of_tests: INTEGER_32 -- (from ES_TESTABLE) number_passed_tests: INTEGER_32 -- (from ES_TESTABLE) print_console_report -- Print a summary of all the test case results to the console. -- (from ES_TESTABLE) local failed: LIST [STRING_8] success: LIST [STRING_8] passed, total: INTEGER_32 do failed := failed_cases success := passed_cases passed := success.count total := success.count + failed.count Io.put_string (create {STRING_8}.make_filled ('=', 60)) Io.put_new_line safe_put_string ("passing tests%N") across success as it loop safe_put_string ("> " + it.item + "%N") end safe_put_string ("failing tests%N") across failed as it loop safe_put_string ("> " + it.item + "%N") end safe_put_string (passed.out + "/" + total.out + " passed%N") if number_of_tests = number_passed_tests then safe_put_string ("passed%N") else safe_put_string ("failed%N") end end print_to_screen (message: STRING_8) -- Prints the message to the screen, handles both GUI and standard output. -- (from ES_TESTABLE) do safe_put_string (message) end run_espec -- New feature instead of run_all. -- (from ES_TESTABLE) local problem: BOOLEAN do if not problem then run_es_test print_console_report end rescue problem := True print_to_screen ("Error: No test cases found, Please add ES_TEST classes to the class that inherits from ES_SUITE%N") retry end safe_put_string (message: STRING_8) -- Socket.putstring with exception handling. -- (from ES_TESTABLE) do print (message) end set_error_report (v: BOOLEAN) -- Show the contract violations if set to true. -- (from ES_TESTABLE) do show_err := v end set_html_name (s: STRING_8) -- Set the output html name. -- (from ES_TESTABLE) do default_html_name := s end show_browser -- Show the default browser. -- (from ES_TESTABLE) do browser := True end show_err: BOOLEAN -- (from ES_TESTABLE) show_errors -- Print error traces to the output. -- (from ES_TESTABLE) do show_err := True end feature -- Output Io: STD_FILES -- Handle to standard file setup -- (from ANY) once create Result Result.set_output_default ensure -- from ANY instance_free: class io_not_void: Result /= Void end out: STRING_8 -- New string containing terse printable representation -- of current object -- (from ANY) do Result := tagged_out ensure -- from ANY out_not_void: Result /= Void end print (o: detachable ANY) -- Write terse external representation of o -- on standard output. -- (from ANY) do if o /= Void then Io.put_string (o.out) end ensure -- from ANY instance_free: class end frozen tagged_out: STRING_8 -- New string containing terse printable representation -- of current object -- (from ANY) external "built_in" ensure -- from ANY tagged_out_not_void: Result /= Void end feature -- Platform Operating_environment: OPERATING_ENVIRONMENT -- Objects available from the operating system -- (from ANY) once create Result ensure -- from ANY instance_free: class operating_environment_not_void: Result /= Void end feature {NONE} -- Retrieval frozen internal_correct_mismatch -- Called from runtime to perform a proper dynamic dispatch on correct_mismatch -- from MISMATCH_CORRECTOR. -- (from ANY) local l_msg: STRING_8 l_exc: EXCEPTIONS do if attached {MISMATCH_CORRECTOR} Current as l_corrector then l_corrector.correct_mismatch else create l_msg.make_from_string ("Mismatch: ") create l_exc l_msg.append (generating_type.name) l_exc.raise_retrieval_exception (l_msg) end end feature {NONE} -- setup and teardown assert (a_name: STRING_8; condition: BOOLEAN; actual: detachable ANY) -- (from ES_TEST) local l_line1, l_line2: attached STRING_8 actual_out: STRING_8 cv: CHECK_VIOLATION do if not condition then if actual /= Void then actual_out := actual.out else actual_out := "Void" end l_line1 := Html_start_code + "Assert Violation: " + a_name + Html_end_code l_line2 := Html_start_code + "Object:   " + actual_out + Html_end_code class_variable_comment_string.append (l_line1 + l_line2) create cv cv.set_description (a_name) cv.raise end end assert_equal (a_name: STRING_8; expected, actual: detachable ANY) -- (from ES_TEST) local l_line1, l_line2, l_line3: STRING_8 expected_out, actual_out: STRING_8 cv: CHECK_VIOLATION do if expected /~ actual then if expected /= Void then expected_out := expected.out else expected_out := "Void" end if actual /= Void then actual_out := actual.out else actual_out := "Void" end l_line1 := Html_start_code + "Assert Equal Violation: " + a_name + Html_end_code l_line2 := Html_start_code + "Expected: " + expected_out + Html_end_code l_line3 := Html_start_code + "Actual:   " + actual_out + Html_end_code class_variable_comment_string.append (l_line1 + l_line2 + l_line3) create cv cv.set_description (a_name) cv.raise end end assert_not_equal (a_name: STRING_8; expected, actual: detachable ANY) -- (from ES_TEST) local l_line1, l_line2, l_line3: attached STRING_8 expected_out, actual_out: STRING_8 cv: CHECK_VIOLATION do if expected ~ actual then if expected /= Void then expected_out := expected.out else expected_out := "Void" end if actual /= Void then actual_out := actual.out else actual_out := "Void" end l_line1 := Html_start_code + "Assert NOT Equal Violation: " + a_name + Html_end_code l_line2 := Html_start_code + "Expected: " + expected_out + Html_end_code l_line3 := Html_start_code + "Actual:   " + actual_out + Html_end_code class_variable_comment_string.append (l_line1 + l_line2 + l_line3) create cv cv.set_description (a_name) cv.raise end end comment (s: STRING_8) -- Adds s to descriptions. -- (from ES_TEST) do class_variable_comment_string := s end Html_end_code: STRING_8 = "</code>" -- (from ES_TEST) Html_start_code: STRING_8 = "<br><code>" -- (from ES_TEST) setup -- Will be executed at the beginning of "run" in a test case. -- (from ES_TEST) do end Space: STRING_8 = " " -- (from ES_TEST) sub_comment (s: STRING_8) -- Adds s to comments. -- (from ES_TEST) do class_variable_comment_string.append ("%N" + s) end teardown -- Will be executed at the end of "run" in a test case. -- (from ES_TEST) do end feature -- tests t0: BOOLEAN local g: GRAPH [INTEGER_32] do comment ("t0: infinity and zero") create g.make_empty Result := g.Infinity = {INTEGER_64}.max_value end t1: BOOLEAN local a, b: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] g: GRAPH [INTEGER_32] do comment ("t1: test array of integers") a := <<[1, 2], [1, 3], [3, 4]>> create g.make_from_tuple_array (a) b := g.as_array Result := g.array_compare (g.as_array, a) check Result end Result := g.edge_count = 3 and g.vertex_count = 4 and g.vertices ~ create {SET [INTEGER_32]}.make_from_array (<<1, 2, 3, 4>>) end t10: BOOLEAN local a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] g: GRAPH [INTEGER_32] vertices: ARRAY [INTEGER_32] edges: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] v, x: INTEGER_32 do comment ("t10: iterable graph") a := <<[0, 1], [1, 2], [0, 3], [7, 3], [7, 6], [3, 4], [4, 7], [5, 7], [5, 4], [6, 5], [2, 0], [2, 2]>> create g.make_from_tuple_array (a) create vertices.make_empty vertices.compare_objects create edges.make_empty edges.compare_objects across g as v_cursor loop v := v_cursor.item vertices.force (v, vertices.count + 1) across g.adjacent (v) as adj_cursor loop x := adj_cursor.item edges.force ([v, x], edges.count + 1) end end Result := vertices.count = 8 and vertices ~ g.vertices.as_array check Result end Result := edges.count = 12 and create {REL [INTEGER_32, INTEGER_32]}.make_from_tuple_array (edges) ~ g.edges end t11: BOOLEAN local a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] g: GRAPH [INTEGER_32] paths: SET [SEQ [INTEGER_32]] do comment ("t11: all paths on a simple graph (no self-loop)") a := <<[1, 2], [3, 2], [1, 3]>> create g.make_from_tuple_array (a) create paths.make_empty paths.extend (create {SEQ [INTEGER_32]}.make_from_array (<<1, 2>>)) paths.extend (create {SEQ [INTEGER_32]}.make_from_array (<<1, 3, 2>>)) Result := g.paths (1, 2) ~ paths check Result end end t12: BOOLEAN local a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] g: GRAPH [INTEGER_32] paths: SET [SEQ [INTEGER_32]] do comment ("t12: all paths on a simple graph (with self-loop)") a := <<[1, 2], [3, 2], [1, 3], [2, 2]>> create g.make_from_tuple_array (a) create paths.make_empty paths.extend (create {SEQ [INTEGER_32]}.make_from_array (<<1, 2>>)) paths.extend (create {SEQ [INTEGER_32]}.make_from_array (<<1, 3, 2>>)) Result := g.paths (1, 2) ~ paths check Result end end t13: BOOLEAN local a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] g: GRAPH [INTEGER_32] paths: SET [SEQ [INTEGER_32]] do comment ("t13: all paths on a graph (with no self-loop)") a := <<[1, 2], [3, 2], [1, 3], [2, 4], [2, 5], [5, 4]>> create g.make_from_tuple_array (a) create paths.make_empty paths.extend (create {SEQ [INTEGER_32]}.make_from_array (<<1, 2, 4>>)) paths.extend (create {SEQ [INTEGER_32]}.make_from_array (<<1, 2, 5, 4>>)) paths.extend (create {SEQ [INTEGER_32]}.make_from_array (<<1, 3, 2, 4>>)) paths.extend (create {SEQ [INTEGER_32]}.make_from_array (<<1, 3, 2, 5, 4>>)) Result := g.paths (1, 4) ~ paths check Result end end t14: BOOLEAN local a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] g: GRAPH [INTEGER_32] paths: SET [SEQ [INTEGER_32]] do comment ("t14: all paths on a graph (with a cycle)") a := <<[1, 2], [2, 4], [4, 5], [5, 2], [2, 3]>> create g.make_from_tuple_array (a) create paths.make_empty paths.extend (create {SEQ [INTEGER_32]}.make_from_array (<<1, 2, 3>>)) Result := g.paths (1, 3) ~ paths check Result end end t15a: BOOLEAN local a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] g: GRAPH [INTEGER_32] expected: SEQ [INTEGER_32] do comment ("t15a: find all reachable vertices from a given vertex (generic graph)") a := <<[1, 4], [2, 1], [1, 3], [4, 2], [3, 2], [6, 4], [2, 6], [2, 5], [5, 8], [5, 9], [5, 7], [10, 9]>> create g.make_from_tuple_array (a) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<1, 4, 3, 2, 6, 5, 8, 9, 7>>) Result := g.reachable (1) ~ expected end t15b: BOOLEAN local a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] g: COMPARABLE_GRAPH [INTEGER_32] expected: SEQ [INTEGER_32] do comment ("t15b: find all reachable vertices from a given vertex (comparable graph)") a := <<[1, 4], [2, 1], [1, 3], [4, 2], [3, 2], [6, 4], [2, 6], [2, 5], [5, 8], [5, 9], [5, 7], [10, 9]>> create g.make_from_tuple_array (a) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<1, 3, 4, 2, 5, 6, 7, 8, 9>>) Result := g.reachable (1) ~ expected end t16: BOOLEAN local a: ARRAY [TUPLE [STRING_8, STRING_8]] g: GRAPH [STRING_8] do comment ("t16: topological sort") a := <<["C", "E"], ["E", "F"], ["C", "G"], ["G", "J"], ["J", "K"], ["D", "H"], ["H", "J"], ["H", "I"]>> create g.make_from_tuple_array (a) g.vertex_extend ("B") g.vertex_extend ("A") Result := g.topologically_sorted.out ~ "< C, D, B, A, E, G, H, F, J, I, K >" end t17: BOOLEAN local a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] g: GRAPH [INTEGER_32] sp: SEQ [INTEGER_32] do comment ("t17: shortest path (when there are multiple ones)") a := <<[1, 3], [3, 6], [1, 2], [2, 6], [1, 4], [4, 5], [5, 6]>> create g.make_from_tuple_array (a) create sp.make_from_array (<<1, 2, 6>>) Result := g.shortest_path_via_dijkstra (1, 6) ~ sp end t18: BOOLEAN local a: ARRAY [TUPLE [STRING_8, STRING_8]] g: GRAPH [STRING_8] seq: SEQ [STRING_8] do comment ("t18: check if a seqence is topologically sorted") a := <<["C", "E"], ["E", "F"], ["C", "G"], ["G", "J"], ["J", "K"], ["D", "H"], ["H", "J"], ["H", "I"]>> create g.make_from_tuple_array (a) g.vertex_extend ("B") g.vertex_extend ("A") g.vertex_extend ("Z") seq := create {attached SEQ [STRING_8]}.make_from_array (<<"C", "D", "B", "A", "E", "G", "H", "F", "J", "I", "K", "Z">>) Result := g.is_topologically_sorted (seq) check Result end seq := create {attached SEQ [STRING_8]}.make_from_array (<<"Z", "D", "H", "C", "E", "F", "G", "J", "I", "K", "A", "B">>) Result := g.is_topologically_sorted (seq) check Result end seq := create {attached SEQ [STRING_8]}.make_from_array (<<"Z", "D", "J", "I", "K", "A", "B", "H", "C", "E", "F", "G">>) Result := not g.is_topologically_sorted (seq) check Result end end t19: BOOLEAN local g: COMPARABLE_GRAPH [INTEGER_32] a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] do comment ("t19: testing breadth first search of GRAPH_ALGORITHMS") a := <<[1, 1], [1, 4], [1, 2], [2, 5], [5, 2], [2, 1], [5, 5], [5, 6]>> a.compare_objects create g.make_from_tuple_array (a) g.vertex_extend (3) Result := g.vertex_count = 6 check Result end assert_equal ("graph correct", "[1:1,2,4][2:1,5][3][4][5:2,5,6][6]", g.debug_output) end t2: BOOLEAN local a, b: ARRAY [TUPLE [STRING_8, STRING_8]] g, g2: GRAPH [STRING_8] do comment ("t2: test array of strings") a := <<["1", "2"], ["1", "3"], ["3", "4"]>> create g.make_from_tuple_array (a) b := g.as_array Result := g.array_compare (g.as_array, a) check Result end Result := g.edge_count = 3 and g.vertex_count = 4 and g.vertices ~ create {SET [STRING_8]}.make_from_array (<<"1", "2", "3", "4">>) check Result end g2 := g.vertex_extended ("5") Result := g2.edge_count = 3 and g2.vertex_count = 5 and g2.vertices ~ create {SET [STRING_8]}.make_from_array (<<"1", "2", "3", "4", "5">>) check Result end end t20: BOOLEAN local g: COMPARABLE_GRAPH [INTEGER_32] a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] expected: SEQ [INTEGER_32] actual: detachable SEQ [INTEGER_32] do comment ("t20: testing cycles in graph") a := <<[1, 4], [1, 2], [2, 5], [5, 2], [2, 1], [5, 6], [2, 2]>> a.compare_objects create g.make_from_tuple_array (a) g.vertex_extend (3) actual := g.cycle (1) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<1, 2, 1>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 1", "< 1, 2, 1 >", cycle.out) end actual := g.cycle (2) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<2, 1, 2>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 2", "< 2, 1, 2 >", cycle.out) end actual := g.cycle (3) Result := not attached actual check Result end actual := g.cycle (4) Result := not attached actual check Result end actual := g.cycle (5) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<5, 2, 1, 2>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 5", "< 5, 2, 1, 2 >", cycle.out) end actual := g.cycle (6) Result := not attached actual check Result end Result := not g.is_acyclic check Result end g.edge_remove (create {PAIR [INTEGER_32, INTEGER_32]}.make_from_tuple ([5, 2])) g.edge_remove (create {PAIR [INTEGER_32, INTEGER_32]}.make_from_tuple ([2, 1])) g.edge_remove (create {PAIR [INTEGER_32, INTEGER_32]}.make_from_tuple ([2, 2])) Result := g.is_acyclic check Result end end t21a: BOOLEAN local g: COMPARABLE_GRAPH [INTEGER_32] a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] expected: SEQ [INTEGER_32] actual: detachable SEQ [INTEGER_32] do comment ("t21a: testing cycles in (more complicated) graph 1") a := <<[1, 7], [1, 3], [3, 5], [3, 3], [3, 4], [4, 5], [4, 3], [5, 1], [7, 8], [7, 7], [7, 6], [6, 7], [8, 1]>> a.compare_objects create g.make_from_tuple_array (a) actual := g.cycle (1) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<1, 3, 3>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 1", "< 1, 3, 3 >", cycle.out) end actual := g.cycle (3) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<3, 3>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 3", "< 3, 3 >", cycle.out) end actual := g.cycle (4) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<4, 3, 3>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 4", "< 4, 3, 3 >", cycle.out) end actual := g.cycle (5) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<5, 1, 3, 3>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 5", "< 5, 1, 3, 3 >", cycle.out) end actual := g.cycle (7) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<7, 6, 7>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 7", "< 7, 6, 7 >", cycle.out) end actual := g.cycle (8) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<8, 1, 3, 3>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 8", "< 8, 1, 3, 3 >", cycle.out) end actual := g.cycle (6) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<6, 7, 6>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 6", "< 6, 7, 6 >", cycle.out) end end t21b: BOOLEAN local g: COMPARABLE_GRAPH [INTEGER_32] a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] expected: SEQ [INTEGER_32] actual: detachable SEQ [INTEGER_32] do comment ("t21a: testing cycles in (more complicated) graph 2") a := <<[1, 8], [1, 5], [8, 8], [8, 7], [8, 6], [6, 8], [6, 7], [7, 1], [5, 5], [5, 4], [5, 3], [4, 5], [3, 1]>> a.compare_objects create g.make_from_tuple_array (a) actual := g.cycle (1) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<1, 5, 3, 1>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 1", "< 1, 5, 3, 1 >", cycle.out) end actual := g.cycle (3) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<3, 1, 5, 3>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 3", "< 3, 1, 5, 3 >", cycle.out) end actual := g.cycle (4) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<4, 5, 3, 1, 5>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 4", "< 4, 5, 3, 1, 5 >", cycle.out) end actual := g.cycle (5) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<5, 3, 1, 5>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 5", "< 5, 3, 1, 5 >", cycle.out) end actual := g.cycle (7) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<7, 1, 5, 3, 1>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 7", "< 7, 1, 5, 3, 1 >", cycle.out) end actual := g.cycle (8) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<8, 6, 7, 1, 5, 3, 1>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 8", "< 8, 6, 7, 1, 5, 3, 1 >", cycle.out) end actual := g.cycle (6) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<6, 7, 1, 5, 3, 1>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 6", "< 6, 7, 1, 5, 3, 1 >", cycle.out) end end t21c: BOOLEAN local g: COMPARABLE_GRAPH [INTEGER_32] a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] expected: SEQ [INTEGER_32] actual: detachable SEQ [INTEGER_32] do comment ("t21c: testing cycles in (very basic) graph") create g.make_from_tuple_array (<<>>) actual := g.cycle (3) Result := not attached actual check Result end create g.make_from_tuple_array (<<[3, 5], [3, 3], [5, 5], [5, 3]>>) actual := g.cycle (3) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<3, 3>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 3", "< 3, 3 >", cycle.out) end actual := g.cycle (5) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<5, 3, 3>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 5", "< 5, 3, 3 >", cycle.out) end create g.make_from_tuple_array (<<[5, 3], [5, 5], [3, 3], [3, 5]>>) actual := g.cycle (3) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<3, 3>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 3", "< 3, 3 >", cycle.out) end actual := g.cycle (5) expected := create {attached SEQ [INTEGER_32]}.make_from_array (<<5, 3, 3>>) Result := expected ~ actual check Result end check attached actual as cycle then assert_equal ("cycle starting from 5", "< 5, 3, 3 >", cycle.out) end end t3: BOOLEAN local a1, a2, a3: ARRAY [TUPLE [STRING_8, STRING_8]] g1, g2, g3, g4: GRAPH [STRING_8] do comment ("t3: check subgraph and graph equality") a1 := <<["1", "2"]>> a2 := <<["2", "1"]>> a3 := <<["1", "2"], ["1", "3"]>> create g1.make_from_tuple_array (a1) create g2.make_from_tuple_array (a2) create g3.make_from_tuple_array (a3) Result := g1 |<: g3 check Result end Result := not (g3 |<: g1) check Result end Result := g1 /~ g3 Result := not (g2 |<: g3) check Result end Result := not (g1 |<: g2) check Result end create g4.make_empty g4.vertex_extend ("1") g4.vertex_extend ("2") g4.vertex_extend ("3") g4 := g4 |\/| create {PAIR [STRING_8, STRING_8]}.make_from_tuple (["1", "3"]) g4 := g4 |\/| create {PAIR [STRING_8, STRING_8]}.make_from_tuple (["1", "2"]) Result := g3 ~ g4 and g3 |<: g4 and g4 |<: g3 end t4: BOOLEAN local a1, a2, a3: ARRAY [TUPLE [STRING_8, STRING_8]] g1, g2, g3: GRAPH [STRING_8] do comment ("t4: vertex removal") a1 := <<["1", "2"]>> a2 := <<["2", "1"]>> a3 := <<["1", "2"], ["1", "3"]>> create g1.make_from_tuple_array (a1) create g2.make_from_tuple_array (a2) create g3.make_from_tuple_array (a3) g3 := g3 - "3" Result := g1 ~ g3 and g2 /~ g3 end t5: BOOLEAN local a1, a2, a3: ARRAY [TUPLE [STRING_8, STRING_8]] g1, g2, g3: GRAPH [STRING_8] do comment ("t5: edge removal") a1 := <<["1", "2"]>> a2 := <<["2", "1"]>> a3 := <<["1", "2"], ["1", "3"]>> create g1.make_from_tuple_array (a1) create g2.make_from_tuple_array (a2) create g3.make_from_tuple_array (a3) g3 := g3 |\ create {PAIR [STRING_8, STRING_8]}.make_from_tuple (["1", "3"]) Result := g1 /~ g3 and g2 /~ g3 check Result end g3 := g3 - "3" Result := g1 ~ g3 and g2 /~ g3 check Result end end t6: BOOLEAN local a: ARRAY [TUPLE [STRING_8, STRING_8]] g: GRAPH [STRING_8] path: detachable SEQ [STRING_8] do comment ("t6: shortest path (using BFS) on a simple, acyclic graph") a := <<["A", "B"], ["B", "E"], ["A", "C"], ["C", "D"]>> create g.make_from_tuple_array (a) path := g.shortest_path ("A", "B") Result := attached path as p and then (p.count = 2 and p [1] ~ "A" and p [2] ~ "B") check Result end path := g.shortest_path ("A", "C") Result := attached path as p and then (p.count = 2 and p [1] ~ "A" and p [2] ~ "C") check Result end path := g.shortest_path ("A", "D") Result := attached path as p and then (p.count = 3 and p [1] ~ "A" and p [2] ~ "C" and p [3] ~ "D") check Result end path := g.shortest_path ("A", "E") Result := attached path as p and then (p.count = 3 and p [1] ~ "A" and p [2] ~ "B" and p [3] ~ "E") check Result end path := g.shortest_path ("A", "A") Result := attached path as p and then (p.count = 1 and p [1] ~ "A") check Result end path := g.shortest_path ("B", "C") Result := not attached path check Result end end t7: BOOLEAN local a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] g: GRAPH [INTEGER_32] path: SEQ [INTEGER_32] do comment ("t7: shortest path (using BFS) on a simple, cyclic graph (with self-loops)") a := <<[0, 1], [1, 2], [0, 3], [7, 3], [7, 6], [3, 4], [4, 7], [5, 7], [5, 4], [6, 5], [2, 0], [2, 2]>> create g.make_from_tuple_array (a) path := g.shortest_path (0, 2) Result := attached path as p and then (p.count = 3 and p ~ create {attached SEQ [INTEGER_32]}.make_from_array (<<0, 1, 2>>)) check Result end path := g.shortest_path (0, 7) Result := attached path as p and then (p.count = 4 and p ~ create {attached SEQ [INTEGER_32]}.make_from_array (<<0, 3, 4, 7>>)) check Result end path := g.shortest_path (0, 6) Result := attached path as p and then (p.count = 5 and p ~ create {attached SEQ [INTEGER_32]}.make_from_array (<<0, 3, 4, 7, 6>>)) check Result end path := g.shortest_path (0, 5) Result := attached path as p and then (p.count = 6 and p ~ create {attached SEQ [INTEGER_32]}.make_from_array (<<0, 3, 4, 7, 6, 5>>)) check Result end path := g.shortest_path (7, 0) Result := not attached path check Result end path := g.shortest_path (2, 0) Result := attached path as p and then (p.count = 2 and p ~ create {attached SEQ [INTEGER_32]}.make_from_array (<<2, 0>>)) check Result end path := g.shortest_path (2, 2) Result := attached path as p and then (p.count = 1 and p ~ create {attached SEQ [INTEGER_32]}.make_from_array (<<2>>)) check Result end end t8: BOOLEAN local a: ARRAY [TUPLE [INTEGER_32, INTEGER_32]] g: GRAPH [INTEGER_32] path: SEQ [INTEGER_32] do comment ("t8: shortest path (using Dijkstra's algorithm) on a simple, cyclic graph (integer vertices)") a := <<[0, 1], [1, 2], [0, 3], [7, 3], [7, 6], [3, 4], [4, 7], [5, 7], [5, 4], [6, 5], [2, 0], [2, 2]>> create g.make_from_tuple_array (a) path := g.shortest_path_via_dijkstra (0, 2) Result := attached path as p and then (p.count = 3 and p ~ create {attached SEQ [INTEGER_32]}.make_from_array (<<0, 1, 2>>)) check Result end path := g.shortest_path_via_dijkstra (0, 7) Result := attached path as p and then (p.count = 4 and p ~ create {attached SEQ [INTEGER_32]}.make_from_array (<<0, 3, 4, 7>>)) check Result end path := g.shortest_path_via_dijkstra (0, 6) Result := attached path as p and then (p.count = 5 and p ~ create {attached SEQ [INTEGER_32]}.make_from_array (<<0, 3, 4, 7, 6>>)) check Result end path := g.shortest_path_via_dijkstra (0, 5) Result := attached path as p and then (p.count = 6 and p ~ create {attached SEQ [INTEGER_32]}.make_from_array (<<0, 3, 4, 7, 6, 5>>)) check Result end path := g.shortest_path_via_dijkstra (7, 0) Result := not attached path check Result end path := g.shortest_path_via_dijkstra (2, 0) Result := attached path as p and then (p.count = 2 and p ~ create {attached SEQ [INTEGER_32]}.make_from_array (<<2, 0>>)) check Result end path := g.shortest_path_via_dijkstra (7, 7) Result := attached path as p and then (p.count = 1 and p ~ create {attached SEQ [INTEGER_32]}.make_from_array (<<7>>)) check Result end path := g.shortest_path_via_dijkstra (2, 2) Result := attached path as p and then (p.count = 1 and p ~ create {attached SEQ [INTEGER_32]}.make_from_array (<<2>>)) check Result end end t9: BOOLEAN local a: ARRAY [TUPLE [STRING_8, STRING_8]] g: GRAPH [STRING_8] path: SEQ [STRING_8] do comment ("t9: shortest path (using Dijkstra's algorithm) on a simple, cyclic graph (string vertices)") a := <<["0", "1"], ["1", "2"], ["0", "3"], ["7", "3"], ["7", "6"], ["3", "4"], ["4", "7"], ["5", "7"], ["5", "4"], ["6", "5"], ["2", "0"], ["2", "2"]>> create g.make_from_tuple_array (a) path := g.shortest_path_via_dijkstra ("0", "2") Result := attached path as p and then (p.count = 3 and p ~ create {attached SEQ [STRING_8]}.make_from_array (<<"0", "1", "2">>)) check Result end path := g.shortest_path_via_dijkstra ("0", "7") Result := attached path as p and then (p.count = 4 and p ~ create {attached SEQ [STRING_8]}.make_from_array (<<"0", "3", "4", "7">>)) check Result end path := g.shortest_path_via_dijkstra ("0", "6") Result := attached path as p and then (p.count = 5 and p ~ create {attached SEQ [STRING_8]}.make_from_array (<<"0", "3", "4", "7", "6">>)) check Result end path := g.shortest_path_via_dijkstra ("0", "5") Result := attached path as p and then (p.count = 6 and p ~ create {attached SEQ [STRING_8]}.make_from_array (<<"0", "3", "4", "7", "6", "5">>)) check Result end path := g.shortest_path_via_dijkstra ("7", "0") Result := not attached path check Result end path := g.shortest_path_via_dijkstra ("2", "0") Result := attached path as p and then (p.count = 2 and p ~ create {attached SEQ [STRING_8]}.make_from_array (<<"2", "0">>)) check Result end path := g.shortest_path_via_dijkstra ("7", "7") Result := attached path as p and then (p.count = 1 and p ~ create {attached SEQ [STRING_8]}.make_from_array (<<"7">>)) check Result end path := g.shortest_path_via_dijkstra ("2", "2") Result := attached path as p and then (p.count = 1 and p ~ create {attached SEQ [STRING_8]}.make_from_array (<<"2">>)) check Result end end feature {ES_HTML_GEN_SUITE} --test cases cases: detachable LINKED_LIST [ES_TEST_CASE] -- (from ES_TEST) class_variable_comment_string: STRING_8 -- (from ES_TEST) attribute Result := "" end descriptions: detachable LINKED_LIST [STRING_8] -- (from ES_TEST) name: detachable STRING_8 -- (from ES_TEST) invariant -- from ANY reflexive_equality: standard_is_equal (Current) reflexive_conformance: conforms_to (Current) end -- class TEST_GRAPH_BASIC
Generated by ISE EiffelStudio