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