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 -*-
#Dinic's algorithm for computing maximum flow in flow network - Tests
#
# ------------------------------------------------------------------------------------
# Tests concerning returning right values by algorithm
#Test 1.0
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-1.0 { graph simulation } {
SETUP_MAXIMUMFLOW_1
set result [dictsort [struct::graph::op::MaximumFlowByDinic mygraph s t dinic]]
mygraph destroy
set result
} {{s v1} 10 {s v2} 9 {v1 v3} 4 {v1 v4} 6 {v2 v4} 9 {v3 t} 9 {v4 t} 10 {v4 v3} 5}
#Test 1.1
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-1.1 { graph simulation } {
SETUP_MAXIMUMFLOW_1
set result [dictsort [struct::graph::op::MaximumFlowByDinic mygraph s t mkm]]
mygraph destroy
set result
} {{s v1} 10 {s v2} 9 {v1 v3} 4 {v1 v4} 6 {v2 v4} 9 {v3 t} 9 {v4 t} 10 {v4 v3} 5}
#Test 1.2
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-1.2 { graph simulation } {
SETUP_FORDFULKERSON_1
set result [dictsort [struct::graph::op::MaximumFlowByDinic mygraph s t mkm]]
mygraph destroy
set result
} {{s v1} 12 {s v2} 11 {v1 v3} 12 {v2 v4} 11 {v3 t} 19 {v4 t} 4 {v4 v3} 7}
#Test 1.3
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-1.3 { graph simulation } {
SETUP_FORDFULKERSON_2
set result [dictsort [struct::graph::op::MaximumFlowByDinic mygraph a d mkm]]
mygraph destroy
set result
} {{a b} 1000000 {a c} 1000000 {b d} 1000000 {c d} 1000000}
#Test 1.4
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-1.4 { graph simulation } {
SETUP_FORDFULKERSON_3
set result [dictsort [struct::graph::op::MaximumFlowByDinic mygraph s t mkm]]
mygraph destroy
set result
} {{s v1} 6 {s v2} 5 {s v3} 3 {v1 t} 3 {v1 v2} 3 {v2 t} 8 {v3 t} 3}
#Test 1.5
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-1.5 { graph simulation } {
SETUP_FORDFULKERSON_4
set result [dictsort [struct::graph::op::MaximumFlowByDinic mygraph s t mkm]]
mygraph destroy
set result
} {{s v1} 4 {s v2} 5 {s v3} 3 {v1 t} 3 {v1 v2} 1 {v2 t} 6 {v3 t} 3}
#Test 1.6
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-1.6 { graph simulation } {
SETUP_FORDFULKERSON_5
set result [dictsort [struct::graph::op::MaximumFlowByDinic mygraph s t mkm]]
mygraph destroy
set result
} {{s v1} 6.5 {s v2} 5.5 {s v3} 3.5 {v1 t} 3.1 {v1 v2} 3.4000000000000004 {v2 t} 8.9 {v3 t} 3.5}
#Test 1.7
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-1.7 { graph simulation } {
SETUP_FORDFULKERSON_1
set result [dictsort [struct::graph::op::MaximumFlowByDinic mygraph s t dinic]]
mygraph destroy
set result
} {{s v1} 12 {s v2} 11 {v1 v3} 12 {v2 v4} 11 {v3 t} 19 {v4 t} 4 {v4 v3} 7}
#Test 1.8
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-1.8 { graph simulation } {
SETUP_FORDFULKERSON_2
set result [dictsort [struct::graph::op::MaximumFlowByDinic mygraph a d dinic]]
mygraph destroy
set result
} {{a b} 1000000 {a c} 1000000 {b d} 1000000 {c d} 1000000}
#Test 1.9
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-1.9 { graph simulation } {
SETUP_FORDFULKERSON_3
set result [dictsort [struct::graph::op::MaximumFlowByDinic mygraph s t dinic]]
mygraph destroy
set result
} {{s v1} 6 {s v2} 5 {s v3} 3 {v1 t} 3 {v1 v2} 3 {v2 t} 8 {v3 t} 3}
#Test 1.10
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-1.10 { graph simulation } {
SETUP_FORDFULKERSON_4
set result [dictsort [struct::graph::op::MaximumFlowByDinic mygraph s t dinic]]
mygraph destroy
set result
} {{s v1} 4 {s v2} 5 {s v3} 3 {v1 t} 3 {v1 v2} 1 {v2 t} 6 {v3 t} 3}
#Test 1.11
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-1.11 { graph simulation } {
SETUP_FORDFULKERSON_5
set result [dictsort [struct::graph::op::MaximumFlowByDinic mygraph s t dinic]]
mygraph destroy
set result
} {{s v1} 6.5 {s v2} 5.5 {s v3} 3.5 {v1 t} 3.1 {v1 v2} 3.4000000000000004 {v2 t} 8.9 {v3 t} 3.5}
# -------------------------------------------------------------------------
# Wrong # args: Missing, Too many
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-2.0 { BlockingFlow, wrong args, missing } {
catch {struct::graph::op::MaximumFlowByDinic} msg
set msg
} [tcltest::wrongNumArgs struct::graph::op::MaximumFlowByDinic {G s t blockingFlowAlg} 0]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-2.1 { BlockingFlow, wrong args, missing } {
catch {struct::graph::op::MaximumFlowByDinic G} msg
set msg
} [tcltest::wrongNumArgs struct::graph::op::MaximumFlowByDinic {G s t blockingFlowAlg} 1]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-2.2 { BlockingFlow, wrong args, missing } {
catch {struct::graph::op::MaximumFlowByDinic G s} msg
set msg
} [tcltest::wrongNumArgs struct::graph::op::MaximumFlowByDinic {G s t blockingFlowAlg} 2]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-2.3 { BlockingFlow, wrong args, missing } {
catch {struct::graph::op::MaximumFlowByDinic G s t} msg
set msg
} [tcltest::wrongNumArgs struct::graph::op::MaximumFlowByDinic {G s t blockingFlowAlg} 3]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-2.4 { BlockingFlow, wrong args, too many} {
catch {struct::graph::op::MaximumFlowByDinic G a b c d} msg
set msg
} [tcltest::tooManyArgs struct::graph::op::MaximumFlowByDinic {G s t blockingFlowAlg}]
# -------------------------------------------------------------------------
# Logical arguments checks and failures
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-DinicMaximumFlow-3.0 { bad value of blocking flow algorithm variable } {
catch {struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg} msg
set msg
} "Uncorrect name of blocking flow algorithm. Choose \"mkm\" for Malhotra, Kumar and Maheshwari algorithm and \"dinic\" for Dinic algorithm."
|