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
|
# -*- tcl -*-
#Floyd-Warshall's Algorithm - Tests
#
#Searching distances between all nodes.
#------------------------------------------------------------------------------------
#Tests concerning returning right values by algorithm
#Test 1.0 - special case for pathfinding algorithm.
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-1.0 { FloydWarshall, graph simulation } {
SETUP_BELLMANFORD_1
set result [dictsort [struct::graph::op::FloydWarshall mygraph]]
mygraph destroy
set result
} {{node1 node1} 0 {node1 node2} 1 {node1 node3} 2 {node1 node4} 3 {node2 node1} 3 {node2 node2} 0 {node2 node3} 1 {node2 node4} 2 {node3 node1} 2 {node3 node2} 3 {node3 node3} 0 {node3 node4} 1 {node4 node1} 1 {node4 node2} 2 {node4 node3} 3 {node4 node4} 0}
#Tests 1.1 - 1.3 - Test cases when there occur existance of cycle with negative sum of weights at edges
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-1.1 { FloydWarshall, negative cycles } {
SETUP_NEGATIVECYCLE_1
catch { struct::graph::op::FloydWarshall mygraph} result
mygraph destroy
set result
} [NegativeCycleOccurance {mygraph}]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-1.2 { FloydWarshall, negative cycles } {
SETUP_NEGATIVECYCLE_2
catch { struct::graph::op::FloydWarshall mygraph } result
mygraph destroy
set result
} [NegativeCycleOccurance {mygraph}]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-1.3 { FloydWarshall, negative cycles } {
SETUP_NEGATIVECYCLE_3
catch { struct::graph::op::FloydWarshall mygraph } result
mygraph destroy
set result
} [NegativeCycleOccurance {mygraph}]
#Test 1.4 - case when we are given a graph without any edges
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-1.4 { FloydWarshall, no edges } {
SETUP_NOEDGES_1
set result [dictsort [struct::graph::op::FloydWarshall mygraph]]
mygraph destroy
set result
} {{node1 node1} 0 {node1 node2} Inf {node1 node3} Inf {node1 node4} Inf {node2 node1} Inf {node2 node2} 0 {node2 node3} Inf {node2 node4} Inf {node3 node1} Inf {node3 node2} Inf {node3 node3} 0 {node3 node4} Inf {node4 node1} Inf {node4 node2} Inf {node4 node3} Inf {node4 node4} 0}
#Test 1.5 - case when we are given a graph with all edge's weights set to 0
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-1.5 { FloydWarshall, all weights set to 0 } {
SETUP_ZEROWEIGHTED_K4
set result [dictsort [struct::graph::op::FloydWarshall mygraph]]
mygraph destroy
set result
} {{node1 node1} 0 {node1 node2} 0 {node1 node3} 0 {node1 node4} 0 {node2 node1} 0 {node2 node2} 0 {node2 node3} 0 {node2 node4} 0 {node3 node1} 0 {node3 node2} 0 {node3 node3} 0 {node3 node4} 0 {node4 node1} 0 {node4 node2} 0 {node4 node3} 0 {node4 node4} 0}
#Test 1.6 - case when we are given a graph with some edge's weights set to 0
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-1.6 { FloydWarshall, some weights set to 0 } {
SETUP_PARTIALLYZEROWEIGHTED
set result [dictsort [struct::graph::op::FloydWarshall mygraph]]
mygraph destroy
set result
} {{node1 node1} 0 {node1 node2} 0 {node1 node3} 0 {node1 node4} 1 {node2 node1} 2 {node2 node2} 0 {node2 node3} 0 {node2 node4} 1 {node3 node1} 2 {node3 node2} 2 {node3 node3} 0 {node3 node4} 1 {node4 node1} 1 {node4 node2} 1 {node4 node3} 1 {node4 node4} 0}
#Test 1.7 - case when we are given a complete K4 graph with some edge's weights set to 0
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-1.7 { FloydWarshall, some weights set to 0 } {
SETUP_PARTIALLYZEROWEIGHTED_K4
set result [dictsort [struct::graph::op::FloydWarshall mygraph]]
mygraph destroy
set result
} {{node1 node1} 0 {node1 node2} 0 {node1 node3} 0 {node1 node4} 0 {node2 node1} 0 {node2 node2} 0 {node2 node3} 0 {node2 node4} 0 {node3 node1} 0 {node3 node2} 0 {node3 node3} 0 {node3 node4} 0 {node4 node1} 0 {node4 node2} 0 {node4 node3} 0 {node4 node4} 0}
#Tests 1.8 - 1.10 - counting right values for special cases of graphs
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-1.8 { FloydWarshall, graph simulation } {
SETUP_JOHNSONS_1
set result [dictsort [struct::graph::op::FloydWarshall mygraph]]
mygraph destroy
set result
} {{node1 node1} 0 {node1 node2} -4 {node1 node3} 1 {node1 node4} -1 {node1 node5} 3 {node2 node1} 4 {node2 node2} 0 {node2 node3} 5 {node2 node4} 3 {node2 node5} 7 {node3 node1} -1 {node3 node2} -5 {node3 node3} 0 {node3 node4} -2 {node3 node5} 2 {node4 node1} 5 {node4 node2} 1 {node4 node3} 6 {node4 node4} 0 {node4 node5} 8 {node5 node1} 1 {node5 node2} -3 {node5 node3} 2 {node5 node4} -4 {node5 node5} 0}
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-1.9 { FloydWarshall, graph simulation } {
SETUP_JOHNSONS_2
set result [dictsort [struct::graph::op::FloydWarshall mygraph]]
mygraph destroy
set result
} {{node1 node1} 0 {node1 node2} 8 {node1 node3} 7 {node1 node4} 5 {node1 node5} 3 {node1 node6} 5 {node2 node1} Inf {node2 node2} 0 {node2 node3} -1 {node2 node4} -3 {node2 node5} -5 {node2 node6} -3 {node3 node1} Inf {node3 node2} 1 {node3 node3} 0 {node3 node4} -2 {node3 node5} -4 {node3 node6} -2 {node4 node1} Inf {node4 node2} Inf {node4 node3} Inf {node4 node4} 0 {node4 node5} Inf {node4 node6} Inf {node5 node1} Inf {node5 node2} Inf {node5 node3} Inf {node5 node4} 2 {node5 node5} 0 {node5 node6} Inf {node6 node1} Inf {node6 node2} 3 {node6 node3} 2 {node6 node4} 0 {node6 node5} -2 {node6 node6} 0}
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-1.10 { FloydWarshall, graph simulation } {
SETUP_BELLMANFORD_2
set result [dictsort [struct::graph::op::FloydWarshall mygraph]]
mygraph destroy
set result
} {{node1 node1} 0 {node1 node2} 8 {node1 node3} 5 {node1 node4} 7 {node1 node5} 3 {node1 node6} 5 {node2 node1} Inf {node2 node2} 0 {node2 node3} -3 {node2 node4} -1 {node2 node5} -5 {node2 node6} -3 {node3 node1} Inf {node3 node2} 3 {node3 node3} 0 {node3 node4} 2 {node3 node5} -2 {node3 node6} 0 {node4 node1} Inf {node4 node2} 1 {node4 node3} -2 {node4 node4} 0 {node4 node5} -4 {node4 node6} -2 {node5 node1} Inf {node5 node2} Inf {node5 node3} Inf {node5 node4} Inf {node5 node5} 0 {node5 node6} 2 {node6 node1} Inf {node6 node2} Inf {node6 node3} Inf {node6 node4} Inf {node6 node5} Inf {node6 node6} 0}
#
# -------------------------------------------------------------------------
# Wrong # args: Missing, Too many
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-2.0 { FloydWarshall, wrong args, missing } {
catch {struct::graph::op::FloydWarshall} msg
set msg
} [tcltest::wrongNumArgs struct::graph::op::FloydWarshall {G} 0]
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-2.1 { FloydWarshall, wrong args, too many} {
catch {struct::graph::op::FloydWarshall G y x} msg
set msg
} [tcltest::tooManyArgs struct::graph::op::FloydWarshall {G}]
# -------------------------------------------------------------------------
# Logical arguments checks and failures
#Test 3.0 - case when given graph doesn't have weights at all edges
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-3.0 {FloydWarshall, lack of weights at edges } {
SETUP_UNWEIGHTED_K4
catch {struct::graph::op::FloydWarshall mygraph} result
mygraph destroy
set result
} [UnweightedArcOccurance]
#Test 3.1 - case when given graph doesn't have weights at all edges
test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-FloydWarshall-3.1 {FloydWarshall, lack of weights at edges } {
SETUP_UNWEIGHTED_K4
catch {struct::graph::op::FloydWarshall mygraph} result
mygraph destroy
set result
} [UnweightedArcOccurance]
|
