File: dinicblockingflow.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 (70 lines) | stat: -rw-r--r-- 3,455 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
# -*- tcl -*-
#Blocking flow by MKM - Tests
#
# ------------------------------------------------------------------------------------
# Tests concerning returning right values by algorithm

#Test 1.0
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BlockingFlowDinic-1.0 { graph simulation } {
    SETUP_BLOCKINGFLOW_1
    set result [dictsort [struct::graph::op::BlockingFlowByDinic mygraph s t]]
    mygraph destroy
    set result
} {{s v1} 3 {s v3} 2 {v1 v2} 2 {v1 v4} 1 {v2 v5} 2 {v3 v4} 1 {v3 v6} 1 {v4 v5} 1 {v4 v7} 1 {v5 t} 3 {v6 v7} 1 {v7 t} 2}

# {{v1 v4} 1 {v2 v5} 2 {v3 v4} 1 {v3 v6} 1 {v4 v5} 1 {v5 t} 3 {v4 v7} 1 {v7 t} 2 {v6 v7} 1 {s v1} 3 {s v3} 2 {v1 v2} 2}

#Test 1.1 - case when input residual graph is created from network that hasn't any flows yet
#Tcl does a 4/6 split at 1, C does a 2/8 split at 1.
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BlockingFlowDinic-1.1 { graph simulation } {
    SETUP_MAXIMUMFLOW_1
    set result [dictsort [struct::graph::op::BlockingFlowByDinic mygraph s t]]
    mygraph destroy
    set result
} [tmE \
       {{s v1} 10 {s v2} 4 {v1 v3} 4 {v1 v4} 6 {v2 v4} 4 {v3 t} 4 {v4 t} 10} \
       {{s v1} 10 {s v2} 2 {v1 v3} 2 {v1 v4} 8 {v2 v4} 2 {v3 t} 2 {v4 t} 10}]

#Test 1.2 - case when input residual graph is created from network that has already some flows used in it
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BlockingFlowDinic-1.2 { graph simulation } {
    SETUP_BLOCKINGFLOW_2
    set result [dictsort [struct::graph::op::BlockingFlowByDinic mygraph s t]]
    mygraph destroy
    set result
} {{s v2} 5 {v2 v4} 5 {v3 t} 5 {v4 v3} 5}

#Test 1.3 - case when from residual graph we get level graph with no arcs - the blocking flow is not found
#cause there are no paths between sink and source in residual graph.
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BlockingFlowDinic-1.3 { graph simulation } {
    SETUP_BLOCKINGFLOW_3
    set result [dictsort [struct::graph::op::BlockingFlowByDinic mygraph s t]]
    mygraph destroy
    set result
} {}

# -------------------------------------------------------------------------
# Wrong # args: Missing, Too many

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BlockingFlowDinic-2.0 { BlockingFlow, wrong args, missing } {
    catch {struct::graph::op::BlockingFlowByDinic} msg
    set msg
} [tcltest::wrongNumArgs struct::graph::op::BlockingFlowByDinic {G s t} 0]

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BlockingFlowDinic-2.1 { BlockingFlow, wrong args, missing } {
    catch {struct::graph::op::BlockingFlowByDinic G} msg
    set msg
} [tcltest::wrongNumArgs struct::graph::op::BlockingFlowByDinic {G s t} 1]

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BlockingFlowDinic-2.2 { BlockingFlow, wrong args, missing } {
    catch {struct::graph::op::BlockingFlowByDinic G s} msg
    set msg
} [tcltest::wrongNumArgs struct::graph::op::BlockingFlowByDinic {G s t} 2]

test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-BlockingFlowDinic-2.3 { BlockingFlow, wrong args, too many} {
    catch {struct::graph::op::BlockingFlowByDinic G y x z} msg
    set msg
} [tcltest::tooManyArgs struct::graph::op::BlockingFlowByDinic {G s t}]

# -------------------------------------------------------------------------
# Logical arguments checks and failures