File: dinicmaximumflow.test

package info (click to toggle)
tcllib 1.20%2Bdfsg-1
  • links: PTS
  • area: main
  • in suites: bullseye
  • size: 68,064 kB
  • sloc: tcl: 216,842; ansic: 14,250; sh: 2,846; xml: 1,766; yacc: 1,145; pascal: 881; makefile: 107; perl: 84; f90: 84; python: 33; ruby: 13; php: 11
file content (137 lines) | stat: -rw-r--r-- 6,453 bytes parent folder | download | duplicates (9)
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."