Map/Tube.pm

filter: Statementstmt 91.3% 21 / 23 Branchbran n/a Conditioncond n/a MC/DCmcdc n/a Subroutinesub 100% 8 / 8 Podpod n/a totaltotal 93.5% 29 / 31 CC 1 SCAR 0.4
CC
1
Cov
91%
BEGIN
1.3
BEGIN
1.0
BEGIN
1.0
CRAP 1.0
« Test/Map/Tube.pm ↑ Summary Map/Tube/Pluggable.pm »
1 package Map::Tube;
2  
3 19 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 19 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
5 19 ▶use version;
Subroutine BEGIN: called CC=1 SCAR=0.0
6  
7 our $VERSION = qv('v5.2.0');
8 our $AUTHORITY = 'cpan:MANWAR';
9  
10 =head1 NAME
11  
12 Map::Tube - Lightweight Routing Framework.
13  
14 =head1 VERSION
15  
16 Version v5.2.0
17  
18 =cut
19  
20 19 ▶use Carp ();
Subroutine BEGIN: called CC=1 SCAR=0.0
21 19 ▶use Unicode::Normalize;
Subroutine BEGIN: called CC=1 SCAR=0.0
22 19 ▶use Encode qw(decode_utf8);
Subroutine BEGIN: called CC=1 SCAR=0.0
23  
24 19 ▶use v5.14;
Subroutine BEGIN: called CC=1 SCAR=0.0
25 0 ▶use XML::Twig;
Subroutine BEGIN: called CC=1 SCAR=2.6
26 use Data::Dumper;
27 use Map::Tube::Node;
28 use Map::Tube::Line;
29 use Map::Tube::Table;
30 use Map::Tube::Route;
31 use Map::Tube::Pluggable;
32 use Map::Tube::Exception::MissingMapData;
33 use Map::Tube::Exception::MissingStationName;
34 use Map::Tube::Exception::InvalidStationName;
35 use Map::Tube::Exception::MissingStationId;
36 use Map::Tube::Exception::InvalidStationId;
37 use Map::Tube::Exception::InvalidStationLineId;
38 use Map::Tube::Exception::MissingLineId;
39 use Map::Tube::Exception::InvalidLineId;
40 use Map::Tube::Exception::MissingLineName;
41 use Map::Tube::Exception::InvalidLineName;
42 use Map::Tube::Exception::InvalidLineColor;
43 use Map::Tube::Exception::FoundMultiLinedStation;
44 use Map::Tube::Exception::FoundMultiLinkedStation;
45 use Map::Tube::Exception::FoundSelfLinkedStation;
46 use Map::Tube::Exception::DuplicateStationId;
47 use Map::Tube::Exception::DuplicateStationName;
48 use Map::Tube::Exception::MissingPluginGraph;
49 use Map::Tube::Exception::MissingPluginFormatter;
50 use Map::Tube::Exception::MissingPluginFuzzyFind;
51 use Map::Tube::Exception::MalformedMapData;
52 use Map::Tube::Exception::InvalidLineStructure;
53 use Map::Tube::Exception::InvalidStationStructure;
54 use Map::Tube::Exception::RouteNotFound;
55 use Map::Tube::Utils qw(to_perl is_same trim common_lines get_method_map is_valid_color);
56 use Map::Tube::Types qw(Routes Tables Lines NodeMap LineMap Color);
57  
58 use Moo::Role;
59 use Role::Tiny qw();
60 use Types::Common::Numeric qw(PositiveOrZeroNum);
61 use namespace::autoclean;
62  
63 =encoding utf8
64  
65 =head1 DESCRIPTION
66  
67 The core module defined as a Role (Moo) to process the map data. It provides the
68 interface to find the shortest route in terms of stoppage between two nodes. Also
69 you can get all possible routes between two given nodes.
70  
71 The routing algorithm is line-change-aware: when two candidate routes have the
72 same number of stops, the one requiring fewer line changes is preferred. Each
73 line change incurs a small fractional penalty (0.5) on top of the normal per-hop
74 cost of 1, so hop count always dominates but unnecessary changes are avoided.
75  
76 If you are keen to know the internals of L<Map::Tube> then please follow the note
77 documented in L<Map::Tube::Cookbook>.
78  
79 =head1 MAP LEADER BOARD
80  
81 +----------------------+-----------+------------------------------------------+
82 | Author | PAUSE ID | Map Count (City) |
83 +----------------------+-----------+------------------------------------------+
84 | Michal Josef Spacek | SKIM | 22 (Bucharest, Budapest, Dnipropetrovsk, |
85 | | | Kazan, Kharkiv, Kiev, KualaLumpur, |
86 | | | Malaga, Minsk, Moscow, Nanjing, |
87 | | | NizhnyNovgorod, Novosibirsk, Prague, |
88 | | | SaintPetersburg, Samara, Singapore, |
89 | | | Sofia, Tbilisi, Vienna, Warsaw, |
90 | | | Yekaterinburg) |
91 | | | |
92 | Gisbert W Selke | GWS | 17 (Beijing, Brussels, Chicago, Glasgow, |
93 | | | Hamburg, Hannover, KoelnBonn, Lyon, |
94 | | | Muenchen, Napoli, Oslo, Paris, RheinRuhr,|
95 | | | San Francisco, Stockholm, Stuttgart, |
96 | | | Toulouse) |
97 | | | |
98 | Mohammad Sajid Anwar | MANWAR | 8 (Barcelona, Delhi, Kolkatta, Leipzig, |
99 | | | London, Madrid, NYC, Tokyo) |
100 | | | |
101 | FUNG Cheok Yin | CYFUNG | 1 (Hong Kong) |
102 | | | |
103 | Peter Harrison | EARLYBEAN | 1 (Sydney) |
104 | | | |
105 | Errietta Kostala | ERRIETTA | 1 (Athens) |
106 | | | |
107 | Giuseppe Di Terlizzi | GDT | 1 (Rome) |
108 | | | |
109 | Marco Fontani | MFONTANI | 1 (Milan) |
110 | | | |
111 | Renee Baecker | RENEEB | 1 (Frankfurt) |
112 | | | |
113 | Soren Lund | SLU | 1 (Copenhagen) |
114 | | | |
115 | Slaven Rezic | SREZIC | 1 (Berlin) |
116 | | | |
117 | Stefan Limbacher | STELIM | 1 (Nuremberg) |
118 | | | |
119 | Vitali Peil | VPEIL | 1 (Bielefeld) |
120 +----------------------+-----------+------------------------------------------+
121  
122 =cut
123  
124 has [qw(name name_to_id plugins _active_link _other_links _link_lines _line_stations _line_station_index _common_lines)] => (is => 'rw');
125 has experimental => (is => 'ro', default => sub { 0 });
126 has nodes => (is => 'rw', isa => NodeMap);
127 has lines => (is => 'rw', isa => Lines );
128 has tables => (is => 'rw', isa => Tables );
129 has routes => (is => 'rw', isa => Routes );
130 has _lines => (is => 'rw', isa => LineMap);
131 has bgcolor => (is => 'rw', isa => Color );
132 has line_change_penalty => (is => 'rw', isa => PositiveOrZeroNum, default => 0.5 );
133  
134 our $AUTOLOAD;
135 our $PLUGINS = {
136 'Map::Tube::Plugin::Graph' => 1,
137 'Map::Tube::Plugin::FuzzyFind' => 1,
138 };
139  
140 sub AUTOLOAD {
141  
142 my $name = $AUTOLOAD;
143 $name =~ s/.*://;
144  
145 return if $name eq 'DESTROY';
146  
147 my @caller = caller(0);
148 @caller = caller(2) if $caller[3] eq '(eval)';
149  
150 my $method_map = get_method_map();
151 if (exists $method_map->{$name}) {
152 my $module = $method_map->{$name}->{module};
153 my $exception = $method_map->{$name}->{exception};
154 $exception->throw({
155 method => "${module}::${name}",
156 message => "ERROR: Missing plugin $module.",
157 filename => $caller[1],
158 line_number => $caller[2] });
159 }
160  
161 my $class = ref($_[0]) || $_[0];
162 Carp::croak(qq{Can't locate object method "$name" via package "$class"});
163 }
164  
165 sub BUILD {
166 my ($self) = @_;
167  
168 # Handle lazy attributes.
169 my @attributes = (keys %{Moo->_constructor_maker_for(ref($self))->all_attribute_specs});
170 unless ((grep /^xml$/, @attributes) || (grep /^json$/, @attributes)) {
171 die "ERROR: Can't apply Map::Tube role, missing 'xml' or 'json'.";
172 }
173  
174 $self->_init_map;
175 $self->_load_plugins;
176 }
177  
178 =head1 SYNOPSIS
179  
180 =head2 Common Usage
181  
182 use strict; use warnings;
183 use Map::Tube::London;
184  
185 my $map = Map::Tube::London->new;
186 print $map->get_shortest_route('Baker Street', 'Euston Square'), "\n";
187  
188 You should expect the result like below:
189  
190 Baker Street (Circle, Hammersmith & City, Bakerloo, Metropolitan, Jubilee), Great Portland Street (Circle, Hammersmith & City, Metropolitan), Euston Square (Circle, Hammersmith & City, Metropolitan)
191  
192 Alternatively,
193  
194 use strict; use warnings;
195 use Map::Tube::London;
196  
197 my $map = Map::Tube::London->new;
198 print $map->get_shortest_route('Baker Street', 'Euston Square')->preferred, "\n";
199  
200 You should now expect the result like below:
201  
202 Baker Street (Circle, Hammersmith & City, Metropolitan), Great Portland Street (Circle, Hammersmith & City, Metropolitan), Euston Square (Circle, Hammersmith & City, Metropolitan)
203  
204 =head1 METHODS
205  
206 =head2 get_shortest_routes($from, $to)
207  
208 This requires C<$from> and C<$to> station names parameters. It returns an object
209 of type L<Map::Tube::Route>. On error it throws an exception of type L<Map::Tube::Exception>.
210  
211 =cut
212  
213 sub get_shortest_route {
214 my ($self, $from, $to) = @_;
215  
216 ($from, $to) =
217 $self->_validate_input('get_shortest_route', $from, $to);
218  
219 my $_from = $self->get_node_by_id($from);
220 my $_to = $self->get_node_by_id($to);
221  
222 $self->_capture_common_lines($_from, $_to);
223  
224 my $reverse = 0;
225  
226 # Found common lines between start and end nodes.
227 if (@{$self->{_common_lines}}) {
228 my $_common_line = $self->{_common_lines}->[0];
229 my $from_index = $self->{_line_station_index}
230 ->{uc($_common_line)}
231 ->{$_from->id};
232 my $to_index = $self->{_line_station_index}
233 ->{uc($_common_line)}
234 ->{$_to->id};
235  
236 # TODO: This cause issue with unidirection route with station index.
237 # $reverse = 1 if (defined $from_index
238 # && defined $to_index
239 # && ($from_index < $to_index));
240 }
241  
242 if ($reverse) {
243 ($from, $to) = ($to, $from);
244 ($_from, $_to) = ($_to, $_from);
245 }
246  
247 $self->_get_shortest_route($from);
248  
249 my $nodes = [];
250 while (defined($to) && !(is_same($from, $to))) {
251 push @$nodes, $self->get_node_by_id($to);
252 $to = $self->_get_path($to);
253 }
254  
255 push @$nodes, $_from;
256  
257 my $_nodes;
258  
259 if ($reverse) {
260 $_nodes = [ @$nodes ];
261 }
262 else {
263 $_nodes = [ reverse(@$nodes) ];
264 }
265  
266 my $start = $_nodes->[0];
267 my $end = $_nodes->[-1];
268  
269 # If you end up with just 2 nodes i.e. start and end, then
270 # double check, if start is directly linked to end node.
271 if (scalar(@$_nodes) == 2) {
272 my $start_name = $start->name;
273 my $end_name = $end->name;
274 unless ($self->_is_directly_linked($start_name, $end_name)) {
275 my @caller = caller(0);
276 @caller = caller(2) if $caller[3] eq '(eval)';
277 Map::Tube::Exception::RouteNotFound->throw({
278 method => __PACKAGE__."::get_shortest_route",
279 message => "ERROR: Route not found from [$start_name] to [$end_name].",
280 filename => $caller[1],
281 line_number => $caller[2] });
282 }
283 }
284  
285 return Map::Tube::Route->new(
286 { from => $start,
287 to => $end,
288 nodes => $_nodes,
289 link_lines => $self->_link_lines,
290 }
291 );
292 }
293  
294 =head2 get_all_routes($from, $to) *** EXPERIMENTAL ***
295  
296 This requires C<$from> and C<$to> station names as parameters. It returns a ref to a
297 list of objects of type L<Map::Tube::Route>. On error it throws an exception of type
298 L<Map::Tube::Exception>.
299  
300 Be careful when using this against a large map. You may encounter a warning similar to
301 this one when running against London map:
302  
303 Deep recursion on subroutine "Map::Tube::_get_all_routes"
304  
305 However, for comparatively smaller maps, like below, it is happy to give all routes.
306  
307 A(1) ---- B(2)
308 / \
309 C(3) -------- F(6) --- G(7) ---- H(8)
310 \ /
311 D(4) ---- E(5)
312  
313 =cut
314  
315 sub get_all_routes {
316 my ($self, $from, $to) = @_;
317  
318 ($from, $to) =
319 $self->_validate_input('get_all_routes', $from, $to);
320  
321 return $self->_get_all_routes([ $from ], $to);
322 }
323  
324 =head2 name()
325  
326 Returns the map name.
327  
328 =head2 get_node_by_id($node_id)
329  
330 Returns an object of type L<Map::Tube::Node> for a given C<$node_id>.
331  
332 =cut
333  
334 sub get_node_by_id {
335 my ($self, $id) = @_;
336  
337 my @caller = caller(0);
338 @caller = caller(2) if $caller[3] eq '(eval)';
339 Map::Tube::Exception::MissingStationId->throw({
340 method => __PACKAGE__."::get_node_by_id",
341 message => "ERROR: Missing Station ID.",
342 filename => $caller[1],
343 line_number => $caller[2] }) unless defined $id;
344  
345 my $node = $self->{nodes}->{$id};
346 Map::Tube::Exception::InvalidStationId->throw({
347 method => __PACKAGE__."::get_node_by_id",
348 message => "ERROR: Invalid Station ID [$id].",
349 filename => $caller[1],
350 line_number => $caller[2] }) unless defined $node;
351  
352 # Check if the node name appears more than once with different id.
353 my @nodes = $self->_get_node_id($node->name);
354 return $node if (scalar(@nodes) == 1);
355  
356 my $lines = {};
357 foreach my $l (@{$node->line}) {
358 $lines->{$l->name} = $l if defined $l->name;
359 }
360 foreach my $i (@nodes) {
361 foreach my $j (@{$self->{nodes}->{$i}->line}) {
362 $lines->{$j->name} = $j if defined $j->name;
363 }
364 }
365 $node->line([ values %$lines ]);
366  
367 return $node;
368 }
369  
370 =head2 get_node_by_name($node_name)
371  
372 Returns an object of type L<Map::Tube::Node> for a given C<$node_name>.
373  
374 =cut
375  
376 sub get_node_by_name {
377 my ($self, $name) = @_;
378  
379 my @caller = caller(0);
380 @caller = caller(2) if $caller[3] eq '(eval)';
381 Map::Tube::Exception::MissingStationName->throw({
382 method => __PACKAGE__."::get_node_by_name",
383 message => "ERROR: Missing Station Name.",
384 filename => $caller[1],
385 line_number => $caller[2] }) unless defined $name;
386  
387 my $id = $self->_get_node_id($name);
388 Map::Tube::Exception::InvalidStationName->throw({
389 method => __PACKAGE__."::get_node_by_name",
390 message => "ERROR: Invalid Station Name [$name].",
391 filename => $caller[1],
392 line_number => $caller[2] }) unless defined $id;
393  
394 return $self->get_node_by_id($id);
395 }
396  
397 =head2 get_line_by_id($line_id)
398  
399 Returns an object of type L<Map::Tube::Line>.
400  
401 =cut
402  
403 sub get_line_by_id {
404 my ($self, $id) = @_;
405  
406 my @caller = caller(0);
407 @caller = caller(2) if $caller[3] eq '(eval)';
408 Map::Tube::Exception::MissingLineId->throw({
409 method => __PACKAGE__."::get_line_by_id",
410 message => "ERROR: Missing Line ID.",
411 filename => $caller[1],
412 line_number => $caller[2] }) unless defined $id;
413  
414 my $line = $self->_get_line_object_by_id($id);
415 Map::Tube::Exception::InvalidLineId->throw({
416 method => __PACKAGE__."::get_line_by_id",
417 message => "ERROR: Invalid Line ID [$id].",
418 filename => $caller[1],
419 line_number => $caller[2] }) unless defined $line;
420  
421 return $line;
422 }
423  
424 =head2 get_line_by_name($line_name)
425  
426 Returns an object of type L<Map::Tube::Line>.
427  
428 =cut
429  
430 sub get_line_by_name {
431 my ($self, $name) = @_;
432  
433 my @caller = caller(0);
434 @caller = caller(2) if $caller[3] eq '(eval)';
435 Map::Tube::Exception::MissingLineName->throw({
436 method => __PACKAGE__."::get_line_by_name",
437 message => "ERROR: Missing Line Name.",
438 filename => $caller[1],
439 line_number => $caller[2] }) unless defined $name;
440  
441 my $line = $self->_get_line_object_by_name($name);
442 $name = _decode_utf8_if_needed($name);
443 Map::Tube::Exception::InvalidLineName->throw({
444 method => __PACKAGE__."::get_line_by_name",
445 message => "ERROR: Invalid Line Name [$name].",
446 filename => $caller[1],
447 line_number => $caller[2] }) unless defined $line;
448  
449 return $line;
450 }
451  
452 =head2 get_lines()
453  
454 Returns a ref to a list of objects of type L<Map::Tube::Line>, containing
455 all lines in the map (but excluding "other links").
456  
457 =cut
458  
459 sub get_lines {
460 my ($self) = @_;
461  
462 my $lines = [];
463 my $other_links = $self->_other_links;
464 foreach (@{$self->{lines}}) {
465 next if exists $other_links->{uc($_->id)};
466 push @$lines, $_ if defined $_->name;
467 }
468  
469 return $lines;
470 }
471  
472 =head2 get_stations($line_name)
473  
474 Returns a ref to a list of objects of type L<Map::Tube::Node> for the line called C<$line_name>.
475 If C<$line_name> is missing, it will return all stations in the map.
476  
477 =cut
478  
479 sub get_stations {
480 my ($self, $line_name) = @_;
481  
482 my $lines = [];
483 my $stations = [];
484 my $seen = {};
485  
486 if (defined $line_name) {
487 my @caller = caller(0);
488 @caller = caller(2) if $caller[3] eq '(eval)';
489  
490 my $line = $self->_get_line_object_by_name($line_name);
491 Map::Tube::Exception::InvalidLineName->throw({
492 method => __PACKAGE__."::get_stations",
493 message => "ERROR: Invalid Line Name [$line_name].",
494 filename => $caller[1],
495 line_number => $caller[2] })
496 unless defined $line;
497  
498 $lines = [ $self->_get_line_object_by_name($line_name) ];
499 }
500 else {
501 $lines = $self->get_lines;
502 }
503  
504 foreach my $line (@$lines) {
505 foreach my $station (@{$line->{stations}}) {
506 unless (exists $seen->{$station->id}) {
507 push @$stations, $self->get_node_by_id($station->id);
508 $seen->{$station->id} = 1;
509 }
510 }
511 }
512  
513 return $stations;
514 }
515  
516 =head2 get_next_stations($station_name)
517  
518 Returns a ref to the list of next stations from the given C<$station_name> as objects
519 of type L<Map::Tube::Node>.
520  
521 =cut
522  
523 sub get_next_stations {
524 my ($self, $station_name, $line_name) = @_;
525  
526 my @caller = caller(0);
527 @caller = caller(2) if $caller[3] eq '(eval)';
528 Map::Tube::Exception::MissingStationName->throw({
529 method => __PACKAGE__."::get_next_stations",
530 message => "ERROR: Missing Station Name.",
531 filename => $caller[1],
532 line_number => $caller[2] }) unless defined $station_name;
533  
534 my $node_id = $self->_get_node_id($station_name);
535 Map::Tube::Exception::InvalidStationName->throw({
536 method => __PACKAGE__."::get_next_stations",
537 message => "ERROR: Invalid Station Name [$station_name].",
538 filename => $caller[1],
539 line_number => $caller[2] }) unless defined $node_id;
540  
541 # Optional: restrict results to stations reachable from this one on a
542 # specific line. This takes any per-edge line restriction (set via the
543 # "A:x" style link syntax) into account, so a link that physically only
544 # runs on line x will correctly be excluded when asking about line y,
545 # even though both stations are nominally on both lines.
546 my $_line_id;
547 if (defined $line_name) {
548 my $_line = $self->_get_line_object_by_name($line_name);
549 Map::Tube::Exception::InvalidLineName->throw({
550 method => __PACKAGE__."::get_next_stations",
551 message => "ERROR: Invalid Line Name [$line_name].",
552 filename => $caller[1],
553 line_number => $caller[2] }) unless defined $_line;
554 $_line_id = uc($_line->id);
555 }
556  
557 my $nodes = [];
558 my $node = $self->get_node_by_id($node_id);
559  
560 if (defined $_line_id) {
561 my %_node_lines = map { uc($_->{id}) => 1 } @{$node->{line}};
562 # If the starting station isn't even served by this line, it has
563 # no neighbors on it, full stop.
564 return $nodes unless $_node_lines{$_line_id};
565 }
566  
567 foreach my $link (split /,/,$node->{link}) {
568 my $_next_node = $self->get_node_by_id($link);
569  
570 if (defined $_line_id) {
571 my %_next_lines = map { uc($_->{id}) => 1 } @{$_next_node->{line}};
572  
573 my $_node_restrictions = $self->{_link_lines}->{uc($node_id)};
574 my $_restriction = defined($_node_restrictions) ? $_node_restrictions->{uc($link)} : undef;
575 if (defined $_restriction) {
576 my %_allowed = map { uc($_) => 1 } @$_restriction;
577 next unless $_allowed{$_line_id};
578 }
579 next unless $_next_lines{$_line_id};
580 }
581  
582 push @$nodes, $_next_node;
583 }
584  
585 return $nodes;
586 }
587  
588 =head2 get_linked_stations($station_name, $line_name)
589  
590 Returns a ref to the list of the names of the linked stations from the given
591 C<$station_name> as strings.
592  
593 The C<$line_name> param is optional. If passed, only stations linked via that
594 specific line are returned -- this respects any per-edge line restriction set
595 via the "A:x" style link syntax, so a link that only physically runs on one
596 line will not be listed as reachable via another line the two stations
597 otherwise share.
598  
599 =cut
600  
601 sub get_linked_stations {
602 my ($self, $station_name, $line_name) = @_;
603  
604 my $nodes = $self->get_next_stations($station_name, $line_name);
605 my $linked_stations = [];
606 foreach my $node (@$nodes) {
607 push @$linked_stations, $node->name;
608 }
609  
610 return $linked_stations;
611 }
612  
613 =head2 bgcolor($color)
614  
615 Set the background color for the map. Returns the new value. If called
616 without a value, returns the unchanged previous value. Setting this is
617 optional. Please set it before making a call to method
618 L<Map::Tube::Plugin::Graph/"as_image($line_name)">. If not set, it will
619 try to guess and may not be as good as you would expect.The C<$color>
620 can be a simply a color name or hash code (C<#RRGGBB>).
621  
622 =head2 line_change_penalty($penalty)
623  
624 When calculating shortest routes, each change from one line to another incurs
625 a penalty which is added to the number of hops on the route. The default penalty
626 is 0.5. This method can be used to query the current value or to set it to a new
627 value, which must be at least 0. (Values of 1 or higher probably do not make much
628 sense, since the number of hops should be the dominating factor.) If you just care
629 about the nnumber of hops but not for changes, set it to 0.
630  
631 =cut
632  
633 #
634 #
635 # DO NOT MAKE IT PUBLIC
636  
637 sub get_map_data {
638 my ($self, $caller, $method) = @_;
639  
640 my $data;
641 my $xml = $self->can('xml') ? $self->xml : '';
642 if ($xml ne '') {
643 eval {
644 $data = XML::Twig->new->parsefile($xml)->simplify(keyattr => 'stations', forcearray => 0);
645 # Handle if there is only one line.
646 my $lines = $data->{lines}->{line};
647 if (ref($lines) eq 'HASH') {
648 $data->{lines}->{line} = [ $lines ];
649 }
650 };
651 unless ($@) {
652 $self->_validate_map_structure($data, $caller);
653 return $data;
654 }
655  
656 $@ =~ s/\s+at\s+\S*?\.pm\s+line\s+.*$//;
657 Map::Tube::Exception::MalformedMapData->throw({
658 method => $method,
659 message => "ERROR: Malformed Map Data ($xml): $@",
660 filename => $caller->[1],
661 line_number => $caller->[2] });
662 }
663 else {
664 my $json = $self->can('json') ? $self->json : '';
665 if ($json ne '') {
666 eval { $data = to_perl($json) };
667 unless ($@) {
668 $self->_validate_map_structure($data, $caller);
669 return $data;
670 }
671  
672 $@ =~ s/\s+at\s+\S*?\.pm\s+line\s+.*$//;
673 Map::Tube::Exception::MalformedMapData->throw({
674 method => $method,
675 message => "ERROR: Malformed Map Data ($json): $@",
676 filename => $caller->[1],
677 line_number => $caller->[2] });
678 }
679 else {
680 if (!defined $caller) {
681 $method = __PACKAGE__.'::get_map_data';
682 my @_caller = caller(0);
683 @_caller = caller(2) if $_caller[3] eq '(eval)';
684 $caller = \@_caller;
685 }
686  
687 Map::Tube::Exception::MissingMapData->throw({
688 method => $method,
689 message => "ERROR: Missing Map Data.",
690 filename => $caller->[1],
691 line_number => $caller->[2] });
692 }
693 }
694 }
695  
696 =head1 PLUGINS
697  
698 =head2 L<Map::Tube::Plugin::Graph>
699  
700 The L<Map::Tube::Plugin::Graph> plugin adds support to generate the entire map
701 or a map for a particular line as a base64 encoded string of a PNG image.
702 For C<Map::Tube> v3.54 or above, you can set the background color explicitly.
703  
704 use strict; use warnings;
705 use MIME::Base64;
706 use Map::Tube::London;
707  
708 my $tube = Map::Tube::London->new;
709  
710 # Optionally, you can override the default background color.
711 $tube->bgcolor("gray");
712  
713 # Entire map image
714 my $name = $tube->name;
715 open(my $MAP_IMAGE, ">", "$name.png")
716 or die "ERROR: Can't open [$name.png]: $!";
717 binmode($MAP_IMAGE);
718 print $MAP_IMAGE decode_base64($tube->as_image);
719 close($MAP_IMAGE);
720  
721 # Just a particular line map image
722 my $line = 'Bakerloo';
723 open(my $LINE_IMAGE, ">", "$line.png")
724 or die "ERROR: Can't open [$line.png]: $!";
725 binmode($LINE_IMAGE);
726 print $LINE_IMAGE decode_base64($tube->as_image($line));
727 close($LINE_IMAGE);
728  
729 Please refer to the L<documentation|Map::Tube::Plugin::Graph> for more details.
730  
731 =head2 L<Map::Tube::Plugin::Formatter>
732  
733 The L<Map::Tube::Plugin::Formatter> plugin adds support to format objects
734 supported by the plugin.
735  
736 use strict; use warnings;
737 use Map::Tube::London;
738  
739 my $tube = Map::Tube::London->new;
740  
741 my $node = $tube->get_node_by_name('Baker Street');
742 print $node->to_xml, "\n\n";
743 print $node->to_json, "\n\n";
744 print $node->to_yaml, "\n\n";
745 print $node->to_string, "\n\n";
746  
747 my $line = $tube->get_line_by_name('Metropolitan');
748 print $line->to_xml, "\n\n";
749 print $line->to_json, "\n\n";
750 print $line->to_yaml, "\n\n";
751 print $line->to_string, "\n\n";
752  
753 my $route = $tube->get_shortest_route('Baker Street', 'Wembley Park');
754 print $route->to_xml, "\n\n";
755 print $route->to_json, "\n\n";
756 print $route->to_yaml, "\n\n";
757 print $route->to_string,"\n\n";
758  
759 Please refer to the L<documentation|Map::Tube::Plugin::Formatter> for more info.
760  
761 =head2 L<Map::Tube::Plugin::FuzzyFind>
762  
763 Gisbert W. Selke built the add-on for L<Map::Tube> to find stations and lines by
764 name, possibly partly or inexactly specified. The module is a Moo role which gets
765 plugged into the Map::Tube::* family automatically once it is installed.
766  
767 use strict; use warnings;
768 use Map::Tube::London;
769  
770 my $tube = Map::Tube::London->new();
771  
772 print 'line matches exactly: ', scalar($tube->fuzzy_find(search => 'erloo', objects => 'lines')), "\n";
773 print 'line contains : ', scalar($tube->fuzzy_find(search => 'erloo', objects => 'lines', method => 'in')), "\n";
774  
775 Please refer to the L<documentation|Map::Tube::Plugin::FuzzyFind> for more info.
776  
777 =head1 MAP DATA FORMAT
778  
779 Map data can be represented in JSON or XML format. The preferred format is JSON.
780 C<Map::Tube v3.23> or above comes with a handy script C<map-data-converter>, that
781 can be used to change the data format of an existing map data.Below is how we can
782 represent the sample map:
783  
784 A(1) ---- B(2)
785 / \
786 C(3) -------- F(6) --- G(7) ---- H(8)
787 \ /
788 D(4) ---- E(5)
789  
790 =head2 JSON
791  
792 {
793 "name" : "sample map",
794 "lines" : {
795 "line" : [
796 { "id" : "A", "name" : "A", "color" : "red" },
797 { "id" : "B", "name" : "B", "color" : "#FFFF00" }
798 ]
799 },
800 "stations" : {
801 "station" : [
802 { "id" : "A1", "name" : "A1", "line" : "A", "link" : "B2,C3" },
803 { "id" : "B2", "name" : "B2", "line" : "A", "link" : "A1,F6" },
804 { "id" : "C3", "name" : "C3", "line" : "A,B", "link" : "A1,D4,F6" },
805 { "id" : "D4", "name" : "D4", "line" : "A,B", "link" : "C3,E5" },
806 { "id" : "E5", "name" : "E5", "line" : "B", "link" : "D4,F6" },
807 { "id" : "F6", "name" : "F6", "line" : "B", "link" : "B2,C3,E5" },
808 { "id" : "G7", "name" : "G7", "line" : "B", "link" : "F6,H8" },
809 { "id" : "H8", "name" : "H8", "line" : "B", "link" : "G7" }
810 ]
811 }
812 }
813  
814 =head2 XML
815  
816 <?xml version="1.0" encoding="UTF-8"?>
817 <tube name="sample map">
818 <lines>
819 <line id="A" name="A" color="red" />
820 <line id="B" name="B" color="#FFFF00"/>
821 </lines>
822 <stations>
823 <station id="A1" name="A1" line="A" link="B2,C3" />
824 <station id="B2" name="B2" line="A" link="A1,F6" />
825 <station id="C3" name="C3" line="A,B" link="A1,D4,F6"/>
826 <station id="D4" name="D4" line="A,B" link="C3,E5" />
827 <station id="E5" name="E5" line="B" link="D4,F6" />
828 <station id="F6" name="F6" line="B" link="B2,C3,E5"/>
829 <station id="G7" name="G7" line="B" link="F6,H8" />
830 <station id="H8" name="H8" line="B" link="G7" />
831 </stations>
832 </tube>
833  
834 =head1 MAP VALIDATION
835  
836 =head2 DATA VALIDATION
837  
838 The package L<Test::Map::Tube> can easily be used to validate raw map data. Anyone
839 building a new map using L<Map::Tube> is advised to have a unit test as a part of
840 their distribution. Just like in L<Map::Tube::London> package, there is a unit test
841 somewhat like below:
842  
843 use strict; use warnings;
844 use Test::More;
845 use Map::Tube::London;
846 use Test::Map::Tube;
847 ok_map(Map::Tube::London->new);
848  
849 =head2 FUNCTIONAL VALIDATION
850  
851 The package L<Test::Map::Tube> can easily be used to validate map
852 basic functions provided by L<Map::Tube>.
853  
854 use strict; use warnings;
855 use Test::More;
856 use Test::Map::Tube;
857 use Map::Tube::London;
858 ok_map_functions(Map::Tube::London->new);
859  
860 It can also easily be used to validate map routing functions provided
861 by L<Map::Tube>:
862  
863 use strict; use warnings;
864 use Test::More;
865 use Test::Map::Tube;
866 use Map::Tube::London;
867 my $map = Map::Tube::London->new;
868 my @routes = (
869 "Route 1|Tower Gateway|Aldgate|Tower Gateway,Tower Hill,Aldgate",
870 "Route 2|Liverpool Street|Monument|Liverpool Street,Bank,Monument",
871 );
872 ok_map_routes($map, \@routes);
873  
874 =cut
875  
876 #
877 #
878 # PRIVATE METHODS
879  
880 sub _get_shortest_route {
881 my ($self, $from) = @_;
882  
883 # Each line change adds this fractional penalty on top of the normal hop
884 # cost of 1. Must be < 1 so hop count always dominates, but large enough
885 # to distinguish zero-change routes from one-change routes.
886  
887 $self->_init_table;
888 $self->_set_length($from, 0);
889 $self->_set_path($from, $from);
890  
891 my $all_nodes = $self->{nodes};
892  
893 # Seed the start node with all of its own lines as the active lines.
894 if (defined $all_nodes->{$from}) {
895 my @ids = map { $_->{id} } @{$all_nodes->{$from}->{line}};
896 $self->_set_current_lines($from, \@ids);
897 }
898  
899 # BFS queue. We still use a plain FIFO queue (not a priority queue) so
900 # that the traversal order, and therefore tie-breaking, matches the
901 # original BFS as closely as possible. The only change is that the cost
902 # stored per node is penalty-weighted (fractional), so a same-hop path
903 # with zero line changes beats one with a change.
904 #
905 # "queued" replaces the old $seen: a node is added to the queue at most
906 # once per cost improvement. Unlike the original $seen, a node can be
907 # re-queued if a cheaper (penalty-aware) path is later discovered.
908 my $queued = {};
909 my @queue = ($from);
910 $queued->{$from} = 1;
911  
912 while (@queue) {
913 my $u = shift @queue;
914 my $u_cost = $self->_get_length($u);
915 my $u_node = $all_nodes->{$u};
916 next unless defined $u_node;
917  
918 $self->_set_active_links($u_node);
919  
920 my %active_set = map { $_ => 1 } @{$self->_get_current_lines($u)};
921  
922 foreach my $v (split /\,/, $u_node->{link}) {
923 next if ($v eq $u);
924  
925 my $v_node = $all_nodes->{$v};
926 next unless defined $v_node;
927  
928 my @v_line_ids = map { $_->{id} } @{$v_node->{line}};
929  
930 # If this specific edge (u -> v) is restricted to a subset of
931 # lines, only those lines are eligible to "continue" through it.
932 my $_u_restrictions = $self->{_link_lines}->{uc($u)};
933 my $_restriction = defined($_u_restrictions) ? $_u_restrictions->{uc($v)} : undef;
934 if (defined $_restriction) {
935 my %_allowed = map { $_ => 1 } @$_restriction;
936 @v_line_ids = grep { $_allowed{uc($_)} } @v_line_ids;
937 }
938  
939 my @continuing = grep { $active_set{$_} } @v_line_ids;
940  
941 my $penalty = (@continuing == 0) ? $self->line_change_penalty : 0;
942 my $new_cost = $u_cost + 1 + $penalty;
943  
944 # Update if unvisited or cheaper. "Unvisited" is path==undef
945 # (avoids the 0-cost ambiguity of the start node).
946 my $old_cost = $self->_get_length($v);
947 my $visited = defined $self->{tables}->{$v}->{path};
948  
949 if (!$visited || $new_cost < $old_cost) {
950 $self->_set_length($v, $new_cost);
951 $self->_set_path($v, $u);
952 my @next = @continuing ? @continuing
953 : (defined $_restriction ? @v_line_ids : $self->_capture_common_lines($u_node, $v_node));
954 $self->_set_current_lines($v, \@next);
955  
956 # Re-queue only if not already waiting in the queue.
957 unless ($queued->{$v}) {
958 push @queue, $v;
959 $queued->{$v} = 1;
960 }
961 }
962 }
963  
964 # Allow re-queuing this node in future if a cheaper path is found.
965 delete $queued->{$u};
966 }
967 }
968  
969 sub _get_all_routes {
970 my ($self, $visited, $to) = @_;
971  
972 my $last = $visited->[-1];
973 my $nodes = $self->get_node_by_id($last)->link;
974 foreach my $id (split /\,/, $nodes) {
975 next if _is_visited($id, $visited);
976  
977 if (is_same($id, $to)) {
978 push @$visited, $id;
979 $self->_set_routes($visited);
980 pop @$visited;
981 last;
982 }
983 }
984  
985 foreach my $id (split /\,/, $nodes) {
986 next if (_is_visited($id, $visited) || is_same($id, $to));
987  
988 push @$visited, $id;
989 $self->_get_all_routes($visited, $to);
990 pop @$visited;
991 }
992  
993 return $self->{routes};
994 }
995  
996 sub _map_node_name {
997 my ($self, $name, $id) = @_;
998  
999 $self->{name_to_id}->{NFC(uc($name))} = $id;
1000 }
1001  
1002 sub _validate_input {
1003 my ($self, $method, $from, $to) = @_;
1004  
1005 my @caller = caller(0);
1006 @caller = caller(2) if $caller[3] eq '(eval)';
1007  
1008 Map::Tube::Exception::MissingStationName->throw({
1009 method => __PACKAGE__."::$method",
1010 message => "ERROR: Missing Station Name.",
1011 filename => $caller[1],
1012 line_number => $caller[2] })
1013 unless (defined($from) && defined($to));
1014  
1015 $from = trim($from);
1016 my $_from = $self->get_node_by_name($from);
1017  
1018 $to = trim($to);
1019 my $_to = $self->get_node_by_name($to);
1020  
1021 return ($_from->{id}, $_to->{id});
1022 }
1023  
1024 sub _xml_data {
1025 my ($self) = @_;
1026  
1027 return $self->get_map_data;
1028 }
1029  
1030 sub _init_map {
1031 my ($self) = @_;
1032  
1033 my $_lines = {};
1034 my $lines = {};
1035 my $nodes = {};
1036 my $tables = {};
1037 my $_other_links = {};
1038 my $_link_lines = {};
1039 my $_seen_nodes = {};
1040  
1041 my @caller = caller(0);
1042 @caller = caller(2) if $caller[3] eq '(eval)';
1043  
1044 my $method = __PACKAGE__."::_init_map";
1045 my $data = $self->get_map_data(\@caller, $method);
1046 $self->{name} = $data->{name};
1047  
1048 # Pull all lines detail first
1049 # So that we can check if a station has a valid line attached.
1050 my @lines;
1051 if (exists $data->{lines} && exists $data->{lines}->{line}) {
1052 @lines = (ref $data->{lines}->{line} eq 'HASH')
1053 ? ($data->{lines}->{line})
1054 : @{$data->{lines}->{line}};
1055 }
1056 my $master_line_data = {};
1057 foreach (@lines) {
1058 $master_line_data->{NFC(lc $_->{id})} = 1;
1059 }
1060  
1061 my $has_station_index = {};
1062 foreach my $station (@{$data->{stations}->{station}}) {
1063 my $id = $station->{id};
1064  
1065 # Support per-link line restrictions in the 'link' attribute, e.g.
1066 # link="A:x,C" means the link to station A only runs on line 'x',
1067 # while the link to C is unrestricted (all lines common between the
1068 # two stations apply, as before). Multiple restricted lines for a
1069 # single link are pipe-separated, e.g. link="A:x|y,C".
1070 # This is fully backward compatible: a plain "A,C" with no colon is
1071 # untouched and behaves exactly as it always has.
1072 if (defined $station->{link} && $station->{link} =~ /\:/) {
1073 my @_clean_links = ();
1074 my $_restrictions_for_station = {};
1075 foreach my $_raw_link (split /\,/, $station->{link}) {
1076 if ($_raw_link =~ /\:/) {
1077 my ($_target, $_line_list) = split /\:/, $_raw_link, 2;
1078 my @_restricted_lines = split /\|/, $_line_list;
1079 foreach my $_rline (@_restricted_lines) {
1080 my $_decoded_rline = _decode_utf8_if_needed($_rline);
1081 unless (exists $master_line_data->{NFC(lc $_decoded_rline)}) {
1082 Map::Tube::Exception::InvalidStationLineId->throw({
1083 method => $method,
1084 message => "ERROR: Invalid restricted line [$_rline] for link to [$_target] at station [$id].",
1085 filename => $caller[1],
1086 line_number => $caller[2] });
1087 }
1088 }
1089 $_restrictions_for_station->{uc($_target)} = [ map { uc(_decode_utf8_if_needed($_)) } @_restricted_lines ];
1090 push @_clean_links, $_target;
1091 }
1092 else {
1093 push @_clean_links, $_raw_link;
1094 }
1095 }
1096 $station->{link} = join(",", @_clean_links);
1097 $_link_lines->{uc($id)} = $_restrictions_for_station;
1098 }
1099  
1100 Map::Tube::Exception::DuplicateStationId->throw({
1101 method => $method,
1102 message => "ERROR: Duplicate Station ID [$id].",
1103 filename => $caller[1],
1104 line_number => $caller[2] }) if (exists $_seen_nodes->{$id});
1105  
1106 $_seen_nodes->{$id} = 1;
1107 my $name = $station->{name};
1108 $name = _decode_utf8_if_needed($name);
1109 Map::Tube::Exception::DuplicateStationName->throw({
1110 method => $method,
1111 message => "ERROR: Duplicate Station Name [$name].",
1112 filename => $caller[1],
1113 line_number => $caller[2] }) if (defined $self->{name_to_id}->{NFC(uc($name))});
1114  
1115 $self->_map_node_name($name, $id);
1116 $tables->{$id} = Map::Tube::Table->new({ id => $id });
1117  
1118 my $_station_lines = [];
1119 foreach my $_line (split /\,/, $station->{line}) {
1120 if ($_line =~ /\:/) {
1121 $_line = $self->_capture_line_station($_line, $id);
1122 $has_station_index->{$_line} = 1;
1123 }
1124  
1125 $_line = _decode_utf8_if_needed($_line);
1126 if (!exists $master_line_data->{NFC(lc $_line)}) {
1127 Map::Tube::Exception::InvalidStationLineId->throw({
1128 method => $method,
1129 message => "ERROR: Invalid line [$_line] for station [$name].",
1130 filename => $caller[1],
1131 line_number => $caller[2] });
1132 }
1133  
1134 my $uc_line = uc($_line);
1135 my $line = $lines->{$uc_line};
1136 $line = Map::Tube::Line->new({ id => $_line }) unless defined $line;
1137 $_lines->{$uc_line} = $line;
1138 $lines->{$uc_line} = $line;
1139 push @$_station_lines, $line;
1140 }
1141  
1142 if (exists $station->{other_link} && defined $station->{other_link}) {
1143 my @link_nodes = ();
1144 foreach my $_entry (split /\,/, $station->{other_link}) {
1145 my ($_link_type, $_nodes) = split /\:/, $_entry, 2;
1146 my $uc_link_type = uc($_link_type);
1147 my $line = $lines->{$uc_link_type};
1148 $line = Map::Tube::Line->new({ id => $_link_type, name => $_link_type }) unless defined $line;
1149 $_lines->{$uc_link_type} = $line;
1150 $lines->{$uc_link_type} = $line;
1151 $_other_links->{$uc_link_type} = 1;
1152  
1153 push @$_station_lines, $line;
1154 push @link_nodes, (split /\|/, $_nodes);
1155 }
1156  
1157 $station->{link} .= "," if $station->{link} ne "";
1158 $station->{link} .= join(",", @link_nodes);
1159 }
1160  
1161 $station->{line} = $_station_lines;
1162 my $node = Map::Tube::Node->new($station);
1163 $nodes->{$id} = $node;
1164  
1165 foreach my $line (@{$_station_lines}) {
1166 next if exists $has_station_index->{$line->id};
1167 push @{$line->{stations}}, $node;
1168 }
1169 }
1170  
1171 foreach my $_line (@lines) {
1172 my $uc_line = uc($_line->{id});
1173 my $line = $_lines->{$uc_line};
1174 if (defined $line) {
1175 $line->{name} = $_line->{name};
1176 $line->{color} = $_line->{color};
1177 if ($has_station_index) {
1178 foreach (sort { $a <=> $b } keys %{$self->{_line_stations}->{$uc_line}}) {
1179 my $station_id = $self->{_line_stations}->{$uc_line}->{$_};
1180 $line->add_station($nodes->{$station_id});
1181 }
1182 }
1183 $_lines->{$uc_line} = $line;
1184 }
1185 }
1186  
1187 $self->_order_station_lines($nodes);
1188  
1189 $self->lines([ values %$lines ]);
1190 $self->_lines($_lines);
1191 $self->_other_links($_other_links);
1192 $self->_link_lines($_link_lines);
1193  
1194 # Populate Node links as ref to Node object
1195 foreach my $node_id (keys %$nodes) {
1196 my $node_obj = $nodes->{$node_id};
1197 foreach my $link (split /\,/,$node_obj->{link}) {
1198 push @{$node_obj->{links}}, $nodes->{$link};
1199 }
1200 }
1201  
1202 $self->nodes($nodes);
1203 $self->tables($tables);
1204 }
1205  
1206 sub _decode_utf8_if_needed {
1207 my ($data) = @_;
1208  
1209 if (!utf8::is_utf8($data) && utf8::valid($data)) {
1210 $data = decode_utf8($data);
1211 }
1212  
1213 return $data;
1214 }
1215  
1216 sub _is_directly_linked {
1217 my ($self, $start_station, $end_station) = @_;
1218 my $linked_stations = $self->get_linked_stations($start_station);
1219  
1220 return grep { $_ eq $end_station } @$linked_stations;
1221 }
1222  
1223 sub _init_table {
1224 my ($self) = @_;
1225  
1226 foreach my $id (keys %{$self->{tables}}) {
1227 $self->{tables}->{$id}->{path} = undef;
1228 $self->{tables}->{$id}->{length} = 0;
1229 $self->{tables}->{$id}->{current_lines} = undef;
1230 }
1231  
1232 $self->{_active_links} = undef;
1233 }
1234  
1235 sub _load_plugins {
1236 my ($self) = @_;
1237  
1238 $self->{plugins} = [ Map::Tube::Pluggable::plugins ];
1239 foreach my $plugin (@{$self->plugins}) {
1240 # Only bother applying the approved plugins.
1241 next unless (exists $PLUGINS->{$plugin});
1242 Role::Tiny->apply_roles_to_object($self, $plugin);
1243 }
1244 }
1245  
1246 sub _capture_common_lines {
1247 my ($self, $from, $to) = @_;
1248  
1249 my $from_lines = [ map { $_->id } @{$from->line} ];
1250 my $to_lines = [ map { $_->id } @{$to->line} ];
1251  
1252 $self->{_common_lines} = [ common_lines($from_lines, $to_lines) ];
1253 }
1254  
1255 sub _get_common_lines {
1256 my ($nodes, $active_links) = @_;
1257  
1258 my %_unique_links = ();
1259 foreach (@{$active_links}) {
1260 $_unique_links{$_} = 1;
1261 }
1262  
1263 my %_common_lines = ();
1264 foreach my $_link (keys %_unique_links) {
1265 foreach my $_link_line (@{$nodes->{$_link}->line}) {
1266 $_common_lines{$_link_line->id} = 1;
1267 }
1268 }
1269  
1270 return (keys %_common_lines);
1271 }
1272  
1273 sub _get_next_link {
1274 my ($self, $from, $seen, $links) = @_;
1275  
1276 my $nodes = $self->{nodes};
1277 my $active_links = $self->{_active_links};
1278  
1279 # Revert changes as it breaks routing (v3.65)
1280 # Commit id: 49273fd2a0baaedbfc1d02ef7
1281 # -------------------------------------------
1282 # my @common_lines = _get_common_lines(
1283 # $nodes, [ @{$active_links->[0]}, @{$active_links->[1]} ]
1284 # );
1285  
1286 my @common_lines = common_lines($active_links->[0], $active_links->[1]);
1287  
1288 if ($self->{experimental} && scalar(@{$self->{_common_lines}})) {
1289 @common_lines = (@{$self->{_common_lines}}, @common_lines);
1290 }
1291  
1292 my $link = undef;
1293 foreach my $_link (@$links) {
1294 return (0, $_link) if ((exists $seen->{$_link}) || ($from eq $_link));
1295  
1296 my $node = $nodes->{$_link};
1297 next unless defined $node;
1298  
1299 my @lines = ();
1300 foreach (@{$node->{line}}) { push @lines, $_->{id}; }
1301  
1302 my @common = common_lines(\@common_lines, \@lines);
1303 return (1, $_link) if (scalar(@common) > 0);
1304  
1305 $link = $_link;
1306 }
1307  
1308 return (defined($link), $link);
1309 }
1310  
1311 sub _set_active_links {
1312 my ($self, $node) = @_;
1313  
1314 my $active_links = $self->{_active_links};
1315 my $links = [ split /\,/, $node->{link} ];
1316  
1317 if (defined $active_links) {
1318 shift @$active_links;
1319 push @$active_links, $links;
1320 }
1321 else {
1322 push @$active_links, $links;
1323 push @$active_links, $links;
1324 }
1325  
1326 $self->{_active_links} = $active_links;
1327 }
1328  
1329 sub _validate_map_structure {
1330 my ($self, $data, $caller) = @_;
1331  
1332 unless (exists $data->{lines}
1333 && exists $data->{lines}->{line}
1334 && @{$data->{lines}->{line}}) {
1335 Map::Tube::Exception::InvalidLineStructure->throw({
1336 method => __PACKAGE__."::_validate_map_structure",
1337 message => "ERROR: Invalid line structure in map data.",
1338 filename => $caller->[1],
1339 line_number => $caller->[2] });
1340 }
1341  
1342 unless (exists $data->{stations}
1343 && exists $data->{stations}->{station}
1344 && @{$data->{stations}->{station}}) {
1345 Map::Tube::Exception::InvalidStationStructure->throw({
1346 method => __PACKAGE__."::_validate_map_structure",
1347 message => "ERROR: Invalid station structure in map data.",
1348 filename => $caller->[1],
1349 line_number => $caller->[2] });
1350 }
1351 }
1352  
1353 sub _capture_line_station {
1354 my ($self, $line, $station_id) = @_;
1355  
1356 my ($line_id, $sequence) = split /\:/, $line, 2;
1357 $self->{_line_stations}->{uc($line_id)}->{$sequence} = $station_id;
1358 $self->{_line_station_index}->{uc($line_id)}->{$station_id} = $sequence;
1359  
1360 return $line_id;
1361 }
1362  
1363 sub _validate_multi_lined_nodes {
1364 my ($self, $caller, $node, $id) = @_;
1365  
1366 my %lines = ();
1367 foreach (@{$node->{line}}) { $lines{$_->{id}}++; }
1368  
1369 my $max_link = 1;
1370 foreach (keys %lines) {
1371 $max_link = $lines{$_} if ($max_link < $lines{$_});
1372 }
1373  
1374 if ($max_link > 1) {
1375 my $message = sprintf("ERROR: %s has multiple lines %s,",
1376 $id, join( ',', grep { $lines{$_} > 1 } keys %lines));
1377  
1378 Map::Tube::Exception::FoundMultiLinedStation->throw({
1379 method => __PACKAGE__."::_validate_map_data",
1380 message => $message,
1381 filename => $caller->[1],
1382 line_number => $caller->[2] });
1383 }
1384 }
1385  
1386 sub _set_routes {
1387 my ($self, $routes) = @_;
1388  
1389 my $_routes = [];
1390 my $nodes = $self->{nodes};
1391 foreach my $id (@$routes) {
1392 push @$_routes, $nodes->{$id};
1393 }
1394  
1395 my $from = $_routes->[0];
1396 my $to = $_routes->[-1];
1397 my $route = Map::Tube::Route->new({ from => $from, to => $to, nodes => $_routes, link_lines => $self->_link_lines });
1398 push @{$self->{routes}}, $route;
1399 }
1400  
1401 sub _get_path {
1402 my ($self, $id) = @_;
1403  
1404 return $self->{tables}->{$id}->{path};
1405 }
1406  
1407 sub _set_path {
1408 my ($self, $id, $node_id) = @_;
1409  
1410 return unless (defined $id && defined $node_id);
1411 $self->{tables}->{$id}->{path} = $node_id;
1412 }
1413  
1414 sub _get_length {
1415 my ($self, $id) = @_;
1416  
1417 return 0 unless (defined $id && defined $self->{tables}->{$id});
1418 return $self->{tables}->{$id}->{length};
1419 }
1420  
1421 sub _set_length {
1422 my ($self, $id, $value) = @_;
1423  
1424 return unless (defined $id && defined $value);
1425 $self->{tables}->{$id}->{length} = $value;
1426 }
1427  
1428 # Track the set of line IDs that were active when we arrived at a node.
1429 # This lets _get_shortest_route penalise line changes.
1430 sub _get_current_lines {
1431 my ($self, $id) = @_;
1432  
1433 return [] unless (defined $id && defined $self->{tables}->{$id});
1434 return $self->{tables}->{$id}->{current_lines} // [];
1435 }
1436  
1437 sub _set_current_lines {
1438 my ($self, $id, $lines_ref) = @_;
1439  
1440 return unless (defined $id && defined $lines_ref);
1441 $self->{tables}->{$id}->{current_lines} = $lines_ref;
1442 }
1443  
1444 sub _get_table {
1445 my ($self, $id) = @_;
1446  
1447 return $self->{tables}->{$id};
1448 }
1449  
1450 sub _get_node_id {
1451 my ($self, $name) = @_;
1452  
1453 return unless defined $name;
1454 $name =~ s/^\s+//;
1455 $name =~ s/\s+$//;
1456 $name = _decode_utf8_if_needed($name);
1457 $name = NFC(uc($name));
1458 return $self->{name_to_id}->{$name};
1459 }
1460  
1461 sub _get_line_object_by_name {
1462 my ($self, $name) = @_;
1463  
1464 $name = _decode_utf8_if_needed($name);
1465 $name = NFC(uc($name));
1466 foreach my $line_id (keys %{$self->{_lines}}) {
1467 my $line = $self->{_lines}->{$line_id};
1468 if (defined $line && defined $line->name) {
1469 return $line if ($name eq uc($line->name));
1470 }
1471 }
1472  
1473 return;
1474 }
1475  
1476 sub _get_line_object_by_id {
1477 my ($self, $id) = @_;
1478  
1479 $id = uc($id);
1480 foreach my $line_id (keys %{$self->{_lines}}) {
1481  
1482 my $line = $self->{_lines}->{$line_id};
1483 if (defined $line && defined $line->name) {
1484 return $line if ($id eq uc($line->id));
1485 }
1486 }
1487  
1488 return;
1489 }
1490  
1491 sub _order_station_lines {
1492 my ($self, $nodes) = @_;
1493  
1494 return unless scalar(keys %$nodes);
1495  
1496 foreach my $node (keys %$nodes) {
1497 my $_lines_h = {};
1498 foreach (@{$nodes->{$node}->{line}}) {
1499 $_lines_h->{$_->id} = $_ if defined $_->name;
1500 }
1501 my $_lines_a = [];
1502 foreach (sort keys %$_lines_h) {
1503 push @$_lines_a, $_lines_h->{$_};
1504 }
1505 $nodes->{$node}->line($_lines_a);
1506 }
1507 }
1508  
1509 sub _is_visited {
1510 my ($id, $list) = @_;
1511  
1512 foreach (@$list) {
1513 return 1 if is_same($_, $id);
1514 }
1515  
1516 return 0;
1517 }
1518  
1519 =head1 AUTHOR
1520  
1521 Mohammad Sajid Anwar, C<< <mohammad.anwar at yahoo.com> >>
1522  
1523 =head1 REPOSITORY
1524  
1525 L<https://github.com/manwar/Map-Tube>
1526  
1527 =head1 SEE ALSO
1528  
1529 =over 2
1530  
1531 =item * L<Map::Tube::CLI>
1532  
1533 =item * L<Map::Tube::API>
1534  
1535 =item * L<Map::Tube::Server>
1536  
1537 =item * L<Map::Metro>
1538  
1539 =back
1540  
1541 =head1 CONTRIBUTORS
1542  
1543 =over 2
1544  
1545 =item * Michal Špaček, C<< <skim at cpan.org> >>
1546  
1547 =item * Slaven Rezic, C<< <srezic at cpan.org> >>
1548  
1549 =item * Gisbert W. Selke, C<< <gws at cpan.org> >>
1550  
1551 =item * Toby Inkster, C<< <tobyink at cpan.org> >>
1552  
1553 =item * Ed J, C<< <etj at cpan.org> >>
1554  
1555 =back
1556  
1557 =head1 BUGS
1558  
1559 Please report any bugs or feature requests through the web interface at L<https://github.com/manwar/Map-Tube/issues>.
1560 I will be notified and then you'll automatically be notified of progress on your
1561 bug as I make changes.
1562  
1563 =head1 SUPPORT
1564  
1565 You can find documentation for this module with the perldoc command.
1566  
1567 perldoc Map::Tube
1568  
1569 You can also look for information at:
1570  
1571 =over 4
1572  
1573 =item * BUG Report
1574  
1575 L<https://github.com/manwar/Map-Tube/issues>
1576  
1577 =item * Search MetaCPAN
1578  
1579 L<https://metacpan.org/dist/Map-Tube/>
1580  
1581 =back
1582  
1583 =head1 LICENSE AND COPYRIGHT
1584  
1585 Copyright (C) 2010 - 2026 Mohammad Sajid Anwar.
1586  
1587 This program is free software; you can redistribute it and / or modify it under
1588 the terms of the the Artistic License (2.0). You may obtain a copy of the full
1589 license at:
1590  
1591 L<http://www.perlfoundation.org/artistic_license_2_0>
1592  
1593 Any use, modification, and distribution of the Standard or Modified Versions is
1594 governed by this Artistic License.By using, modifying or distributing the Package,
1595 you accept this license. Do not use, modify, or distribute the Package, if you do
1596 not accept this license.
1597  
1598 If your Modified Version has been derived from a Modified Version made by someone
1599 other than you,you are nevertheless required to ensure that your Modified Version
1600 complies with the requirements of this license.
1601  
1602 This license does not grant you the right to use any trademark, service mark,
1603 tradename, or logo of the Copyright Holder.
1604  
1605 This license includes the non-exclusive, worldwide, free-of-charge patent license
1606 to make, have made, use, offer to sell, sell, import and otherwise transfer the
1607 Package with respect to any patent claims licensable by the Copyright Holder that
1608 are necessarily infringed by the Package. If you institute patent litigation
1609 (including a cross-claim or counterclaim) against any party alleging that the
1610 Package constitutes direct or contributory patent infringement,then this Artistic
1611 License to you shall terminate on the date that such litigation is filed.
1612  
1613 Disclaimer of Warranty: THE PACKAGE IS PROVIDED BY THE COPYRIGHT HOLDER AND
1614 CONTRIBUTORS "AS IS' AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES. THE IMPLIED
1615 WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR
1616 NON-INFRINGEMENT ARE DISCLAIMED TO THE EXTENT PERMITTED BY YOUR LOCAL LAW. UNLESS
1617 REQUIRED BY LAW, NO COPYRIGHT HOLDER OR CONTRIBUTOR WILL BE LIABLE FOR ANY DIRECT,
1618 INDIRECT, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING IN ANY WAY OUT OF THE USE
1619 OF THE PACKAGE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1620  
1621 =cut
1622  
1623 1; # End of Map::Tube
« Test/Map/Tube.pm ↑ Summary Map/Tube/Pluggable.pm »