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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
|
use Test::More tests => 124;
use Graph;
use Graph::Directed;
use Graph::Undirected;
my $g = Graph::Directed->new;
$g->add_weighted_path("b", 1, "f", 2, "c", 3, "d", 3,
"f", 2, "g", 2, "e");
$g->add_weighted_edges("d", "e", 3,
"g", "a", 3,
"g", "f", 2,
"b", "a", 3,
"h", "b", 1,
"h", "c", 1);
my $u = Graph::Undirected->new;
$u->add_weighted_path("b", 1, "f",
2, "c",
3, "d",
3, "f",
2, "g",
2, "e");
$u->add_weighted_edges("d", "e", 3,
"g", "a", 3,
"g", "f", 2,
"b", "a", 3,
"h", "b", 1,
"h", "c", 1);
my $sgb_d = $g->SPT_Dijkstra(first_root => "b");
is( $sgb_d, "b-a,b-f,c-d,f-c,f-g,g-e" );
my $sgb_bf = $g->SPT_Bellman_Ford(first_root => "b");
is( $sgb_bf, "b-a,b-f,c-d,f-c,f-g,g-e" );
my $sgh_d = $g->SPT_Dijkstra(first_root => "h");
is( $sgh_d, "b-a,b-f,c-d,f-g,g-e,h-b,h-c" );
my $sga_d = $g->SPT_Dijkstra(first_root => "a", next_root => undef);
is( $sga_d, '' );
my $sub = $u->SPT_Dijkstra(first_root => "b");
is( $sub, "a=b,b=f,b=h,c=h,d=f,e=g,f=g" );
my $suh = $u->SPT_Dijkstra(first_root => "h");
is( $suh, "a=b,b=f,b=h,c=d,c=h,e=g,f=g" );
my $sua = $u->SPT_Dijkstra(first_root => "a");
print "# sua = $sua\n";
ok( $sua eq "a=b,a=g,b=f,b=h,c=h,d=e,e=g" ||
$sua eq "a=b,a=g,b=f,b=h,c=h,d=f,e=g" ||
$sua eq "a=b,a=g,c=f,c=h,d=e,e=g,f=g" ||
$sua eq "a=b,a=g,c=f,c=h,d=f,e=g,f=g" );
# Sedgewick, Algorithms in C, Third Edition
# Chapter 21, "Shortest Paths", Figure 21.10 (p 282)
my $g2 = Graph::Directed->new;
$g2->add_weighted_edge(qw(0 1 0.41));
$g2->add_weighted_edge(qw(1 2 0.51));
$g2->add_weighted_edge(qw(2 3 0.50));
$g2->add_weighted_edge(qw(4 3 0.36));
$g2->add_weighted_edge(qw(3 5 0.38));
$g2->add_weighted_edge(qw(3 0 0.45));
$g2->add_weighted_edge(qw(0 5 0.29));
$g2->add_weighted_edge(qw(5 4 0.21));
$g2->add_weighted_edge(qw(1 4 0.32));
$g2->add_weighted_edge(qw(4 2 0.32));
$g2->add_weighted_edge(qw(5 1 0.29));
my $s2_di = $g2->SPT_Dijkstra(first_root => "0");
is( $s2_di, "0-1,0-5,4-2,4-3,5-4" );
my $s2_bf = $g2->SPT_Bellman_Ford(first_root => "0");
is( $s2_bf, "0-1,0-5,4-2,4-3,5-4" );
my $g3 = Graph::Directed->new;
$g3->add_weighted_path(qw(a 1 b 2 c 3 d -1 e 4 f));
my $s3_da;
eval '$s3_da = $g3->SPT_Dijkstra(first_root => "a")';
like($@, qr/Graph::SPT_Dijkstra: edge d-e is negative \(-1\)/);
is( $s3_da, undef );
my $s3_bf;
eval '$s3_bf = $g3->SPT_Bellman_Ford(first_root => "a")';
is($@, '');
is( $s3_bf, "a-b,b-c,c-d,d-e,e-f");
$g3->add_weighted_path(qw(b -2 a));
undef $s3_bf;
eval '$s3_bf = $g3->SPT_Bellman_Ford(first_root => "a")';
like($@, qr/Graph::SPT_Bellman_Ford: negative cycle exists/);
is( $s3_bf, undef );
# http://rt.cpan.org/NoAuth/Bug.html?id=516
my $g4 = new Graph::Undirected;
$g4->add_weighted_edge("r1", "l1", 1);
my $d4 = $g4->SSSP_Dijkstra("r1");
is($g4, "l1=r1");
is($d4, "l1=r1");
# Nathan Goodman
my $g5 = Graph::Directed->new;
$g5->add_edge(qw(0 1));
$g5->add_edge(qw(1 2));
my $sg5 = $g5->SPT_Dijkstra(first_root => "0");
is($sg5, "0-1,1-2");
# Test the attributes of the $s2_di from earlier.
# $s2_di->_dump;
is($s2_di->get_edge_attribute('0', '1', 'weight'), 0.41, "edge 0-1");
is($s2_di->get_edge_attribute('0', '5', 'weight'), 0.29, "edge 0-5");
is($s2_di->get_edge_attribute('5', '4', 'weight'), 0.50, "edge 5-4");
is($s2_di->get_edge_attribute('4', '3', 'weight'), 0.86, "edge 4-3");
is($s2_di->get_edge_attribute('4', '2', 'weight'), 0.82, "edge 4-2");
is($s2_di->get_edge_attribute('0', '3', 'weight'), undef, "edge 0-3");
is($s2_di->get_edge_attribute('3', '5', 'weight'), undef, "edge 3-5");
is($s2_di->get_edge_attribute('5', '1', 'weight'), undef, "edge 5-1");
is($s2_di->get_edge_attribute('1', '2', 'weight'), undef, "edge 1-2");
is($s2_di->get_edge_attribute('2', '3', 'weight'), undef, "edge 2-3");
is($s2_di->get_edge_attribute('1', '0', 'weight'), undef, "edge 1-0");
is($s2_di->get_edge_attribute('5', '0', 'weight'), undef, "edge 5-0");
is($s2_di->get_edge_attribute('4', '5', 'weight'), undef, "edge 4-5");
is($s2_di->get_edge_attribute('3', '4', 'weight'), undef, "edge 3-4");
is($s2_di->get_edge_attribute('2', '4', 'weight'), undef, "edge 2-4");
is($s2_di->get_edge_attribute('3', '0', 'weight'), undef, "edge 3-0");
is($s2_di->get_edge_attribute('5', '3', 'weight'), undef, "edge 5-3");
is($s2_di->get_edge_attribute('1', '5', 'weight'), undef, "edge 1-5");
is($s2_di->get_edge_attribute('2', '1', 'weight'), undef, "edge 2-1");
is($s2_di->get_edge_attribute('3', '2', 'weight'), undef, "edge 3-2");
is($s2_di->get_vertex_attribute('0', 'weight'), undef, "vertex 0");
is($s2_di->get_vertex_attribute('1', 'weight'), 0.41, "vertex 1");
is($s2_di->get_vertex_attribute('2', 'weight'), 0.82, "vertex 2");
is($s2_di->get_vertex_attribute('3', 'weight'), 0.86, "vertex 3");
is($s2_di->get_vertex_attribute('4', 'weight'), 0.50, "vertex 4");
is($s2_di->get_vertex_attribute('5', 'weight'), 0.29, "vertex 5");
is($s2_di->get_vertex_attribute('0', 'p'), undef, "vertex 0 p");
is($s2_di->get_vertex_attribute('1', 'p'), 0, "vertex 1 p");
is($s2_di->get_vertex_attribute('2', 'p'), 4, "vertex 2 p");
is($s2_di->get_vertex_attribute('3', 'p'), 4, "vertex 3 p");
is($s2_di->get_vertex_attribute('4', 'p'), 5, "vertex 4 p");
is($s2_di->get_vertex_attribute('5', 'p'), 0, "vertex 5 p");
is("@{[$g2->SP_Dijkstra('0', '0')]}", "0", "path 0 0");
is("@{[$g2->SP_Dijkstra('0', '1')]}", "0 1", "path 0 1");
is("@{[$g2->SP_Dijkstra('0', '2')]}", "0 5 4 2", "path 0 2");
is("@{[$g2->SP_Dijkstra('0', '3')]}", "0 5 4 3", "path 0 3");
is("@{[$g2->SP_Dijkstra('0', '4')]}", "0 5 4", "path 0 4");
is("@{[$g2->SP_Dijkstra('0', '5')]}", "0 5", "path 0 5");
is("@{[$g2->SP_Dijkstra('1', '0')]}", "1 4 3 0", "path 1 0");
is("@{[$g2->SP_Dijkstra('1', '1')]}", "1", "path 1 1");
is("@{[$g2->SP_Dijkstra('1', '2')]}", "1 2", "path 1 2");
is("@{[$g2->SP_Dijkstra('1', '3')]}", "1 4 3", "path 1 3");
is("@{[$g2->SP_Dijkstra('1', '4')]}", "1 4", "path 1 4");
is("@{[$g2->SP_Dijkstra('1', '5')]}", "1 4 3 5", "path 1 5");
is("@{[$g2->SP_Dijkstra('0', '0')]}", "0", "path 0 0");
is("@{[$g2->SP_Dijkstra('0', '1')]}", "0 1", "path 0 1");
is("@{[$g2->SP_Dijkstra('0', '2')]}", "0 5 4 2", "path 0 2");
is("@{[$g2->SP_Dijkstra('0', '3')]}", "0 5 4 3", "path 0 3");
is("@{[$g2->SP_Dijkstra('0', '4')]}", "0 5 4", "path 0 4");
is("@{[$g2->SP_Dijkstra('0', '5')]}", "0 5", "path 0 5");
is($s2_bf->get_edge_attribute('0', '1', 'weight'), 0.41, "edge 0-1");
is($s2_bf->get_edge_attribute('0', '5', 'weight'), 0.29, "edge 0-5");
is($s2_bf->get_edge_attribute('5', '4', 'weight'), 0.21, "edge 5-4");
is($s2_bf->get_edge_attribute('4', '3', 'weight'), 0.36, "edge 4-3");
is($s2_bf->get_edge_attribute('4', '2', 'weight'), 0.32, "edge 4-2");
is($s2_bf->get_edge_attribute('0', '3', 'weight'), undef, "edge 0-3");
is($s2_bf->get_edge_attribute('3', '5', 'weight'), undef, "edge 3-5");
is($s2_bf->get_edge_attribute('5', '1', 'weight'), undef, "edge 5-1");
is($s2_bf->get_edge_attribute('1', '2', 'weight'), undef, "edge 1-2");
is($s2_bf->get_edge_attribute('2', '3', 'weight'), undef, "edge 2-3");
is($s2_bf->get_edge_attribute('1', '0', 'weight'), undef, "edge 1-0");
is($s2_bf->get_edge_attribute('5', '0', 'weight'), undef, "edge 5-0");
is($s2_bf->get_edge_attribute('4', '5', 'weight'), undef, "edge 4-5");
is($s2_bf->get_edge_attribute('3', '4', 'weight'), undef, "edge 3-4");
is($s2_bf->get_edge_attribute('2', '4', 'weight'), undef, "edge 2-4");
is($s2_bf->get_edge_attribute('3', '0', 'weight'), undef, "edge 3-0");
is($s2_bf->get_edge_attribute('5', '3', 'weight'), undef, "edge 5-3");
is($s2_bf->get_edge_attribute('1', '5', 'weight'), undef, "edge 1-5");
is($s2_bf->get_edge_attribute('2', '1', 'weight'), undef, "edge 2-1");
is($s2_bf->get_edge_attribute('3', '2', 'weight'), undef, "edge 3-2");
is($s2_bf->get_vertex_attribute('0', 'weight'), undef, "vertex 0");
is($s2_bf->get_vertex_attribute('1', 'weight'), 0.41, "vertex 1");
is($s2_bf->get_vertex_attribute('2', 'weight'), 0.82, "vertex 2");
is($s2_bf->get_vertex_attribute('3', 'weight'), 0.86, "vertex 3");
is($s2_bf->get_vertex_attribute('4', 'weight'), 0.50, "vertex 4");
is($s2_bf->get_vertex_attribute('5', 'weight'), 0.29, "vertex 5");
is($s2_bf->get_vertex_attribute('0', 'p'), undef, "vertex 0 p");
is($s2_bf->get_vertex_attribute('1', 'p'), 0, "vertex 1 p");
is($s2_bf->get_vertex_attribute('2', 'p'), 4, "vertex 2 p");
is($s2_bf->get_vertex_attribute('3', 'p'), 4, "vertex 3 p");
is($s2_bf->get_vertex_attribute('4', 'p'), 5, "vertex 4 p");
is($s2_bf->get_vertex_attribute('5', 'p'), 0, "vertex 5 p");
is("@{[$g2->SP_Bellman_Ford('0', '0')]}", "0", "path 0 0");
is("@{[$g2->SP_Bellman_Ford('0', '1')]}", "0 1", "path 0 1");
is("@{[$g2->SP_Bellman_Ford('0', '2')]}", "0 5 4 2", "path 0 2");
is("@{[$g2->SP_Bellman_Ford('0', '3')]}", "0 5 4 3", "path 0 3");
is("@{[$g2->SP_Bellman_Ford('0', '4')]}", "0 5 4", "path 0 4");
is("@{[$g2->SP_Bellman_Ford('0', '5')]}", "0 5", "path 0 5");
is("@{[$g2->SP_Bellman_Ford('1', '0')]}", "1 4 3 0", "path 1 0");
is("@{[$g2->SP_Bellman_Ford('1', '1')]}", "1", "path 1 1");
is("@{[$g2->SP_Bellman_Ford('1', '2')]}", "1 2", "path 1 2");
is("@{[$g2->SP_Bellman_Ford('1', '3')]}", "1 4 3", "path 1 3");
is("@{[$g2->SP_Bellman_Ford('1', '4')]}", "1 4", "path 1 4");
is("@{[$g2->SP_Bellman_Ford('1', '5')]}", "1 4 3 5", "path 1 5");
is("@{[$g2->SP_Bellman_Ford('0', '0')]}", "0", "path 0 0");
is("@{[$g2->SP_Bellman_Ford('0', '1')]}", "0 1", "path 0 1");
is("@{[$g2->SP_Bellman_Ford('0', '2')]}", "0 5 4 2", "path 0 2");
is("@{[$g2->SP_Bellman_Ford('0', '3')]}", "0 5 4 3", "path 0 3");
is("@{[$g2->SP_Bellman_Ford('0', '4')]}", "0 5 4", "path 0 4");
is("@{[$g2->SP_Bellman_Ford('0', '5')]}", "0 5", "path 0 5");
{
my $g = Graph::Directed->new(refvertexed => 1);
$g->add_edge(qw(a b));
$g->add_edge(qw(a c));
$g->add_edge(qw(c d));
$g->add_edge(qw(c e));
$g->add_edge(qw(e f));
my $r = [1, 2, 3];
$g->add_edge('f', $r);
my $s0 = $g->SPT_Dijkstra(first_root => 'a');
ok($s0->has_vertex('f'));
my @e0 = $s0->successors('f');
is(@e0, 1);
is_deeply($e0[0], $r);
my $s1 = $g->SPT_Bellman_Ford(first_root => 'a');
ok($s1->has_vertex('f'));
my @e1 = $s1->successors('f');
is(@e1, 1);
is($e1[0], $r);
}
|
