1# -*- tcl -*- 2#Vertices Cover, 2 approximation algorithm - Tests 3# 4#Algorithm searches for the minimum set of vertices such that each edge of the graph 5#is incident to at least one vertex of the set. 6# 7#------------------------------------------------------------------------------------ 8#Tests concerning returning right values by algorithm 9 10#Test 1.0 - case when graph is complete - the same degrees and even number of nodes 11test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-VerticesCover-1.0 { VerticesCover, complete K4 } { 12 SETUP_UNDIRECTED_K4 13 set result [lsort -dict [struct::graph::op::VerticesCover mygraph]] 14 mygraph destroy 15 set result 16} {node1 node2 node3 node4} 17 18#Test 1.1 - case with big degree differences at nodes 19test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-VerticesCover-1.1 { VerticesCover, graph simulation } { 20 SETUP_VC_1 21 set result [lsort -dict [struct::graph::op::VerticesCover mygraph]] 22 mygraph destroy 23 set result 24} [tmE {node1 node3} {node2 node3}] 25 26#Test 1.2 - another test case testing the improvement given by degree conditions 27test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-VerticesCover-1.2 { VerticesCover, graph simulation } { 28 SETUP_VC_2 29 set result [lsort -dict [struct::graph::op::VerticesCover mygraph]] 30 mygraph destroy 31 set result 32} {node2 node3 node4 node5} 33 34#Test 1.3 - case when graph is a cycle - degrees are the same for all nodes 35test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-VerticesCover-1.3 { VerticesCover, cycle C5 } { 36 SETUP_C5 37 set result [lsort -dict [struct::graph::op::VerticesCover mygraph]] 38 mygraph destroy 39 set result 40} [tmE {node2 node3 node4 node5} {node1 node3 node4 node5}] 41# should custom match code verifying that result is a cover. 42 43#Test 1.4 - case when given graph is a K4, but with doubled arcs (directed) 44test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-VerticesCover-1.4 { VerticesCover, directed K4 } { 45 SETUP_K4 46 set result [lsort -dict [struct::graph::op::VerticesCover mygraph]] 47 mygraph destroy 48 set result 49} {node1 node2 node3 node4} 50 51#Test 1.5 - graph from Test 1.1, but with doubled arcs (directed) 52test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-VerticesCover-1.5 { VerticesCover, directed, complete } { 53 SETUP_VC_1_2 54 set result [lsort -dict [struct::graph::op::VerticesCover mygraph]] 55 mygraph destroy 56 set result 57} [tmE {node1 node3} {node2 node3}] 58 59#Test 1.6 - graph from Test 1.1, but with some doubled arcs (directed) 60test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-VerticesCover-1.6 { VerticesCover, directed, uncomplete } { 61 SETUP_VC_1_3 62 set result [lsort -dict [struct::graph::op::VerticesCover mygraph]] 63 mygraph destroy 64 set result 65} [tmE {node1 node3} {node2 node3}] 66 67# ------------------------------------------------------------------------- 68# Wrong # args: Missing, Too many 69 70test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-VerticesCover-2.0 { VerticesCover, wrong args, missing } { 71 catch {struct::graph::op::VerticesCover} msg 72 set msg 73} [tcltest::wrongNumArgs struct::graph::op::VerticesCover {G} 0] 74 75test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-VerticesCover-2.1 { VerticesCover, wrong args, too many} { 76 catch {struct::graph::op::VerticesCover G y x} msg 77 set msg 78} [tcltest::tooManyArgs struct::graph::op::VerticesCover {G}] 79 80# ------------------------------------------------------------------------- 81# Logical arguments checks and failure 82