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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
# -*- tcl -*-
#Busacker-Gowen algorithm - computing maximum flow in a flow network
#
#
# ------------------------------------------------------------------------------------
# Tests concerning returning right values by algorithm
# ------------------------------------------------------------------------------------
#Test 1.0
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.0 { graph simulation } {
SETUP_BUSACKERGOWEN_1
set result [dictsort [struct::graph::op::BusackerGowen mygraph 25 s t]]
mygraph destroy
set result
} {{a b} 8 {a c} 10 {b t} 8 {c t} 17 {s a} 18 {s c} 7}
#Test 1.1 - case considering when desired flow is equal to max flow
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.1 { graph simulation } {
SETUP_BUSACKERGOWEN_1
set result [dictsort [struct::graph::op::BusackerGowen mygraph 31 s t]]
mygraph destroy
set result
} {{a b} 14 {b t} 14 {c a} 18 {c t} 17 {s a} 18 {s c} 13}
#Test 1.2 - case considering when desired flow exceeds max flow - algorithm should end when
#there is no more paths between source and sink nodes.
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.2 { graph simulation } {
SETUP_BUSACKERGOWEN_1
set result [dictsort [struct::graph::op::BusackerGowen mygraph 40 s t]]
mygraph destroy
set result
} {{a b} 14 {b t} 14 {c a} 18 {c t} 17 {s a} 18 {s c} 13}
#Test 1.3 - case when the are no paths between source and sink from the beginning
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.3 { graph simulation } {
SETUP_SOURCESINKNOPATHS
set result [struct::graph::op::BusackerGowen mygraph 1 s t]
mygraph destroy
set result
} {}
#Test 1.4 - test for subprocedure that creates Augmenting Network
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.4 { createAugmentingNetwork, graph simulation } -setup {
SETUP_AUGMENTINGNETWORK_1 f path
set throughputs {}
set costs {}
} -body {
set result [struct::graph::op::createAugmentingNetwork mygraph $f $path]
set throughputs_arcs [$result arcs -key throughput]
set costs_arcs [$result arcs -key cost]
foreach t $throughputs_arcs c $costs_arcs {
dict set throughputs $t [$result arc set $t throughput]
dict set costs $c [$result arc set $c cost]
}
list [dictsort $throughputs] | [dictsort $costs]
} -cleanup {
unset costs throughputs f costs_arcs throughputs_arcs path t
mygraph destroy
$result destroy
} -result {{{a b} 20 {a c} 0 {a s} 15 {b t} 14 {c a} 15 {c b} 12 {c t} 2 {s a} 3 {s c} 20 {t c} 15} | {{a b} 5 {a c} Inf {a s} -3 {b t} 5 {c a} -4 {c b} 8 {c t} 3 {s a} 3 {s c} 8 {t c} -3}}
#Test 1.5 - test for subprocedure that creates Augmenting Network
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.5 { createAugmentingNetwork, graph simulation } -setup {
SETUP_AUGMENTINGNETWORK_2 f path
set throughputs {}
set costs {}
} -body {
set result [struct::graph::op::createAugmentingNetwork mygraph $f $path]
set throughputs_arcs [$result arcs -key throughput]
set costs_arcs [$result arcs -key cost]
foreach t $throughputs_arcs c $costs_arcs {
dict set throughputs $t [$result arc set $t throughput]
dict set costs $c [$result arc set $c cost]
}
list [dictsort $throughputs] | [dictsort $costs]
} -cleanup {
unset costs throughputs f costs_arcs throughputs_arcs path t
mygraph destroy
$result destroy
} -result {{{a b} 20 {a c} 0 {a s} 15 {b t} 14 {c a} 15 {c b} 12 {c s} 2 {c t} 0 {s a} 3 {s c} 18 {t c} 17} | {{a b} 5 {a c} Inf {a s} -3 {b t} 5 {c a} -4 {c b} 8 {c s} -8 {c t} Inf {s a} 3 {s c} 8 {t c} -3}}
#Test 1.6 - test for subprocedure that creates Augmenting Network
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-1.6 { createAugmentingNetwork, graph simulation } -setup {
SETUP_AUGMENTINGNETWORK_3 f path
set throughputs {}
set costs {}
} -body {
set result [struct::graph::op::createAugmentingNetwork mygraph $f $path]
set throughputs_arcs [$result arcs -key throughput]
set costs_arcs [$result arcs -key cost]
foreach t $throughputs_arcs c $costs_arcs {
dict set throughputs $t [$result arc set $t throughput]
dict set costs $c [$result arc set $c cost]
}
list [dictsort $throughputs] | [dictsort $costs]
} -cleanup {
unset costs throughputs f costs_arcs throughputs_arcs path t
mygraph destroy
$result destroy
} -result {{{a b} 17 {a c} 0 {a s} 18 {b a} 3 {b t} 11 {c a} 15 {c b} 12 {c s} 2 {c t} 0 {s a} 0 {s c} 18 {t b} 3 {t c} 17} | {{a b} 5 {a c} Inf {a s} -3 {b a} -5 {b t} 5 {c a} -4 {c b} 8 {c s} -8 {c t} Inf {s a} Inf {s c} 8 {t b} -5 {t c} -3}}
# -------------------------------------------------------------------------
# Wrong # args: Missing, Too many
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-2.0 { BusackerGowen, wrong args, missing } {
catch {struct::graph::op::BusackerGowen} msg
set msg
} [tcltest::wrongNumArgs struct::graph::op::BusackerGowen {G desiredFlow s t} 0]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-2.1 { BusackerGowen, wrong args, missing } {
catch {struct::graph::op::BusackerGowen G} msg
set msg
} [tcltest::wrongNumArgs struct::graph::op::BusackerGowen {G desiredFlow s t} 1]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-2.2 { BusackerGowen, wrong args, missing } {
catch {struct::graph::op::BusackerGowen G desiredFlow} msg
set msg
} [tcltest::wrongNumArgs struct::graph::op::BusackerGowen {G desiredFlow s t} 2]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-2.3 { BusackerGowen, wrong args, too many} {
catch {struct::graph::op::BusackerGowen G desiredFlow c s t z} msg
set msg
} [tcltest::tooManyArgs struct::graph::op::BusackerGowen {G desiredFlow s t}]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-2.4 { BusackerGowen, wrong args, missing } {
catch {struct::graph::op::BusackerGowen G desiredFlow s} msg
set msg
} [tcltest::wrongNumArgs struct::graph::op::BusackerGowen {G desiredFlow s t} 3]
# -------------------------------------------------------------------------
# Logical arguments checks and failures
#Test 3.0 - case when sink and source nodes given at input aren't nodes of input graph
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-3.0 {BusackerGowen, wrong sink or source } {
SETUP_BUSACKERGOWEN_1
catch {struct::graph::op::BusackerGowen mygraph 25 x y } result
mygraph destroy
set result
} [LackOfSinkOrSource x y]
#Test 3.1 - case when input network has lacking attributes
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-3.1 {BusackerGowen, missing attributes } {
SETUP_BUSACKERGOWEN_2
catch {struct::graph::op::BusackerGowen mygraph 25 s t } result
mygraph destroy
set result
} [WrongAttributes throughput cost]
#Test 3.2 - case when wrong input value of desired flow is given at input
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BusackerGowen-3.2 {BusackerGowen, wrong input, desired flow } {
SETUP_BUSACKERGOWEN_1
catch {struct::graph::op::BusackerGowen mygraph 0 s t } result
mygraph destroy
set result
} [WrongValueAtInput desiredFlow]
|
