1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
# -*- tcl -*-
# Graph ops tests - Maximal matchings from bi-partitions.
# Copyright (c) 2008 Andreas Kupries <andreas_kupries@users.sourceforge.net>
# All rights reserved.
# RCS: @(#) $Id: maxmatching.test,v 1.3 2009/09/15 19:24:12 andreas_kupries Exp $
# Syntax: struct::graph::op::isBipartite? G ?partitionvar?
# -------------------------------------------------------------------------
# Wrong # args: Missing, Too many
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-1.0 {max matching, wrong args, missing} {
catch {struct::graph::op::maxMatching} msg
set msg
} [tcltest::wrongNumArgs struct::graph::op::maxMatching {g X Y} 0]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-1.1 {max matching, wrong args, missing} {
catch {struct::graph::op::maxMatching g} msg
set msg
} [tcltest::wrongNumArgs struct::graph::op::maxMatching {g X Y} 1]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-1.2 {max matching, wrong args, missing} {
catch {struct::graph::op::maxMatching g x} msg
set msg
} [tcltest::wrongNumArgs struct::graph::op::maxMatching {g X Y} 2]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-1.3 {max matching, wrong args, too many} {
catch {struct::graph::op::maxMatching g x y z} msg
set msg
} [tcltest::tooManyArgs struct::graph::op::maxMatching {g X Y}]
# -------------------------------------------------------------------------
# Logical arguments checks and failures
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-2.0 {max matching, bad bi-partition} knownBug {
SETUP_E
set result {}
struct::graph::op::isBipartite? mygraph result
foreach {A B} $result break
lappend A [lindex $B 0] ; # force intersection
catch {struct::graph::op::maxMatching mygraph $A $B} result
mygraph destroy
set result
} {Not a bi-partition}
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-2.1 {max matching, bad bi-partition} knownBug {
SETUP_E
set result {}
struct::graph::op::isBipartite? mygraph result
foreach {A B} $result break
set A [lreplace $A end end] ; # force partial coverage
catch {struct::graph::op::maxMatching mygraph $A $B} result
mygraph destroy
set result
} {Not a bi-partition}
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-2.2 {max matching, bad bi-partition} knownBug {
SETUP_E
set result {}
struct::graph::op::isBipartite? mygraph result
foreach {A B} $result break
lappend A bogus ; # force bogus node outside of graph
catch {struct::graph::op::maxMatching mygraph $A $B} result
mygraph destroy
set result
} {Not a bi-partition}
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-2.3 {max matching, bad bi-partition} knownBug {
SETUP_E
set result {}
struct::graph::op::isBipartite? mygraph result
foreach {A B} $result break
mygraph arc insert [lindex $A 0] [lindex $A 1] ; # force arc violating bipart condition
catch {struct::graph::op::maxMatching mygraph $A $B} result
mygraph destroy
set result
} {Not a bi-partition}
# -------------------------------------------------------------------------
# Ok arguments.
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-3.0 {max matching, empty graph} knownBug {
SETUP
set result {}
struct::graph::op::isBipartite? mygraph result
set result [lsort -dict [struct::graph::op::maxMatching mygraph [lindex $result 0] [lindex $result 1]]]
mygraph destroy
set result
} {}
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-3.1 {max matching, nodes, no arcs} knownBug {
SETUP
set result {}
mygraph node insert 0 1 2 3 4 5
struct::graph::op::isBipartite? mygraph result
set result [lsort -dict [struct::graph::op::maxMatching mygraph [lindex $result 0] [lindex $result 1]]]
mygraph destroy
set result
} {}
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-3.3 {max matching} knownBug {
SETUP_E
set result {}
struct::graph::op::isBipartite? mygraph result
set result [lsort -dict [struct::graph::op::maxMatching mygraph [lindex $result 0] [lindex $result 1]]]
mygraph destroy
set result
} {}
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-3.4 {max matching} knownBug {
SETUP_F
set result {}
struct::graph::op::isBipartite? mygraph result
set result [lsort -dict [struct::graph::op::maxMatching mygraph [lindex $result 0] [lindex $result 1]]]
mygraph destroy
set result
} {}
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-3.5 {max matching} knownBug {
SETUP_G
set result {}
struct::graph::op::isBipartite? mygraph result
set result [lsort -dict [struct::graph::op::maxMatching mygraph [lindex $result 0] [lindex $result 1]]]
mygraph destroy
set result
} {}
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-maxmatch-3.6 {max matching} knownBug {
SETUP_C
set result {}
struct::graph::op::isBipartite? mygraph result
set result [lsort -dict [struct::graph::op::maxMatching mygraph [lindex $result 0] [lindex $result 1]]]
mygraph destroy
set result
} {}
# ---------------------------------------------------
|
