File Coverage

blib/lib/Map/Tube/Cookbook.pm
Criterion Covered Total %
statement 11 11 100.0
branch n/a
condition n/a
subroutine 4 4 100.0
pod n/a
total 15 15 100.0


line stmt bran cond sub pod time code
1             package Map::Tube::Cookbook;
2              
3             $Map::Tube::Cookbook::VERSION = '0.06';
4             $Map::Tube::Cookbook::AUTHORITY = 'cpan:MANWAR';
5              
6             =head1 NAME
7              
8             Map::Tube::Cookbook - Cookbook for Map::Tube library.
9              
10             =head1 VERSION
11              
12             Version 0.06
13              
14             =cut
15              
16 1     1   15376 use 5.006;
  1         26  
17 1     1   4 use strict; use warnings;
  1     1   1  
  1         18  
  1         2  
  1         5  
  1         24  
18 1     1   576 use Data::Dumper;
  1         6428  
  1         119  
19              
20             =head1 DESCRIPTION
21              
22             Cookbook for L v3.22 or above library.
23              
24             =head1 SETUP MAP
25              
26             C or above now supports map data in XML and JSON format. Here is
27             the Structure of map in XML format:
28              
29            
30            
31            
32            
33             name="Line-Name"
34             color="Line-Color-Code" />
35             .....
36             .....
37             .....
38             .....
39            
40              
41            
42            
43             name="Station-Name"
44             line="Line-ID:Station-Index"
45             link="Station-ID"
46             other_link="Link-Name:Station-ID" />
47             .....
48             .....
49             .....
50             .....
51            
52            
53              
54             And same in JSON format:
55              
56             {
57             "name" : "Your-Map-Name",
58             "lines" : {
59             "line" : [
60             { "id" : "Line-ID",
61             "name" : "Line-Name",
62             "color" : "Line-Code-Code"
63             },
64             .....
65             .....
66             .....
67             .....
68             ]
69             },
70             "stations" : {
71             "station" : [
72             { "id" : "Station-ID",
73             "name" : "Station-Name",
74             "line" : "Line-ID:Station-Index",
75             "link" : "Station-ID",
76             "other_link" : "Link-Name:Station-ID"
77             },
78             .....
79             .....
80             .....
81             .....
82             ]
83             }
84             }
85              
86             The root of the xml data is C having one optional attribute C i.e map
87             name and two childrens C and C.
88              
89             The node C has one or more children C. The node C defines the
90             'Line' of the map. The node C has to have the attributes C, C.
91             Optionally it can have C as well. They are explained as below:
92              
93             +-----------+---------------------------------------------------------------+
94             | Attribute | Description |
95             +-----------+---------------------------------------------------------------+
96             | | |
97             | id | Unique line id of the map. Ideally should be numeric but can |
98             | | be alphanumeric. It shouldn't contain ",". |
99             | | |
100             | name | Line name of the map. It doesn't have to be unique as long as |
101             | | it has unique line id. |
102             | | |
103             | color | Line color is optional. It should have color name or hexcode. |
104             | | |
105             +-----------+---------------------------------------------------------------+
106              
107             Example from L as shown below:
108              
109            
110              
111             The node C has one or more children C. The node C is
112             used to represent 'station' of the map.It must have attributes C, C,
113             C and C. It can optionally have attribute C.
114              
115             +------------+--------------------------------------------------------------+
116             | Attribute | Description |
117             +------------+--------------------------------------------------------------+
118             | | |
119             | id | Unique station id of the map. Ideally should be numeric but |
120             | | can be alphanumeric. It shouldn't contain ",". |
121             | | |
122             | name | Station name of the map.It doesn't have to be unique as long |
123             | | as it has unique station id. |
124             | | |
125             | line | Represents the station line alongwith the station index on |
126             | | the line. It should be ":" separated, e.g. "Red:2". It means |
127             | | this is the first station on the line 'Red'. Station index |
128             | | is NOT mandatory but nice to have. If the station crosses |
129             | | more than one lines, then they should be listed as "," |
130             | | separated. For Example, "Red:9,Green:16". |
131             | | |
132             | link | Represents all linked stations to this station. e.g. "B04" |
133             | | If it is linked to more than one stations then they should |
134             | | be listed as ", " separated. For example "B04,B02". |
135             | | |
136             | other_link | This attribute is optional. This is useful if the station is |
137             | | linked via other link and not by any of the lines, e.g. some |
138             | | stations are linked by tunnel. This can be defined as |
139             | | "Tunnel:B02" |
140             | | |
141             +------------+--------------------------------------------------------------+
142              
143             Example from L without station index:
144              
145            
146             name="Bank"
147             line="Central,DLR,Northern,Waterloo & City"
148             link="S002,S024,L013,M011,L012,W008"
149             other_link="Tunnel:M009" />
150              
151             Example from L with station index:
152              
153            
154             name="Dwarka Sector 9"
155             line="Blue:3"
156             link="B04,B02" />
157              
158             Let us create xml map for the following map:
159              
160             A(1) ---- B(2)
161             / \
162             C(3) -------- F(6) --- G(7) ---- H(8)
163             \ /
164             D(4) ---- E(5)
165              
166             Below is the XML representation C of the above map:
167              
168            
169            
170            
171            
172            
173            
174            
175            
176            
177            
178            
179            
180            
181            
182            
183            
184              
185             Next is the JSON representation C of the above map:
186              
187             {
188             "name" : "Sample",
189             "lines" : { "line" : [ { "id" : "L1", "name" : "L1" } ] },
190             "stations" : { "station" : [ { "id" : "L01", "name": "A", "line": "L1:1", "link": "L02,L03" },
191             { "id" : "L02", "name": "B", "line": "L1:2", "link": "L01,L06" },
192             { "id" : "L03", "name": "C", "line": "L1:3", "link": "L01,L04,L06" },
193             { "id" : "L04", "name": "D", "line": "L1:4", "link": "L03,L05" },
194             { "id" : "L05", "name": "E", "line": "L1:5", "link": "L04,L06" },
195             { "id" : "L06", "name": "F", "line": "L1:6", "link": "L02,L03,L05,L07" },
196             { "id" : "L07", "name": "G", "line": "L1:7", "link": "L06,L08" },
197             { "id" : "L08", "name": "H", "line": "L1:8", "link": "L07" }
198             ]
199             }
200             }
201              
202             =head1 CREATE MAP
203              
204             You would need the C v3.22 or above to be able to support JSON format.
205              
206             Following code manage the map data in XML format.
207              
208             package Sample::Map;
209              
210             use Moo;
211             use namespace::clean;
212              
213             has xml => (is => 'ro', default => sub { 'sample.xml' });
214             with 'Map::Tube';
215              
216             package main;
217             use strict; use warnings;
218              
219             my $map = Sample::Map->new;
220             print $map->get_shortest_route('A', 'D');
221              
222             In order to support map data in JSON format, just replace the line below:
223              
224             has xml => (is => 'ro', default => sub { 'sample.xml' });
225              
226             with
227              
228             has json => (is => 'ro', default => sub { 'sample.json' });
229              
230             =head1 MAP GRAPH
231              
232             To print the entire map or just a particular line map, just install the plugin
233             L and you have all the tools to create map image.
234              
235             use strict; use warnings;
236             use MIME::Base64;
237             use Sample::Map;
238              
239             my $map = Sample::Map->new;
240             my $name = $map->name;
241             open(my $MAP_IMAGE, ">$name.png");
242             binmode($MAP_IMAGE);
243             print $MAP_IMAGE decode_base64($map->as_image);
244             close($MAP_IMAGE);
245              
246             =head1 FUZZY FIND
247              
248             To enable the fuzzy search ability to the sample map, you would need to install
249             L and you have everything you need to perform the
250             task.
251              
252             use strict; use warnings;
253             use Sample::Map;
254              
255             my $map = Sample::Map->new;
256             print 'Line contains: ', $map->fuzzy_find(search => 'a', object => 'lines');
257              
258             =head1 VALIDATE MAP
259              
260             There is handy package L that can help you in testing the basic
261             map structure and functionalities.
262              
263             use strict; use warnings;
264             use Test::More;
265              
266             my $min_ver = 0.09;
267             eval "use Test::Map::Tube $min_ver tests => 2";
268             plan skip_all => "Test::Map::Tube $min_ver required" if $@;
269              
270             use Sample::Map;
271             my $map = Sample::Map->new;
272             ok_map($map);
273             ok_map_functions($map);
274              
275             =head1 SEARCH ALGORITHM
276              
277             Lets take the same sample map.
278              
279             1 -------- 2
280             / \ / \
281             / \ / \
282             0 ------ 6 ------ 3
283             \ / \ /
284             \ / \ /
285             5 -------- 4
286              
287             We would build a table as follows:
288              
289             +--------+---------------+
290             | Vertex | Path | Length |
291             +--------+------+--------+
292             | 0 | - | INF |
293             | 1 | - | INF |
294             | 2 | - | INF |
295             | 3 | - | INF |
296             | 4 | - | INF |
297             | 5 | - | INF |
298             | 6 | - | INF |
299             +--------+------+--------+
300              
301             In the table, the index on the left represents the vertex we are going to (for
302             convenience, we will assume that we are starting at vertex 0). We will ignore the
303             Known field; it is only necessary if the edges are weighted. The Path field tells
304             us which vertex precedes us in the path. The Length field is the length of the
305             path from the starting vertex to that vertex, which we initialize to INFinity
306             under the assumption that there is no path unless we find one, in which case the
307             length will be less than infinity.
308              
309             We begin by indicating that 0 can reach itself with a path of length 0. This is
310             better than infinity, so we replace INF with 0 in the Length column, and we also
311             place a 0 in the Path column. Now we look at 0's neighbors. All three of 0's
312             neighbors 1, 5, and 6 can be reached from 0 with a path of length 1 (1 + the
313             length of the path to 0, which is 0), and for all three of them this is better,so
314             we update their Path and Length fields and then enqueue them because we will have
315             to look at their neighbors next.
316              
317             We dequeue 1, and look at its neighbors 0, 2, and 6. The path through vertex 1 to
318             each of those vertices would have a length of 2 (1 + the length of the path to 1,
319             which is 1). For 0 and 6 this is worse than what is already in their Length field
320             so we will do nothing for them. For 2, the path of length 2 is better than
321             infinity, so we will put 2 in its Length field and 1 in its Path field, since it
322             came from 1, and then we will enqueue so we can eventually look at its neighbors
323             if necessary.
324              
325             We dequeue the 5 and look at its neighbors 0, 4, and 6. The path through vertex 5
326             to each of those vertices would have a length of 2 (1 + the length of the path to
327             5, which is 1). For 0 and 6, this is worse than what is already in their Length
328             field, so we will do nothing for them. For 4, the path of length 2 is better than
329             infinity, so we will put 2 in its Length field and 5 in its Path field, since it
330             came from 5, and then we will enqueue it so we can eventually look at its
331             neighbors if necessary.
332              
333             Next we dequeue the 6, which shares an edge with each of the other six vertices.
334             The path through 6 to any of these vertices would have a length of 2, but only
335             vertex 3 currently has a higher Length (infinity), so we will update 3's fields
336             and enqueue it.
337              
338             Of the remaining items in the queue the path through them to their neighbors will
339             all have a length of 3, since they all have a length of 2, which will be worse
340             than the values that are already in the Length fields of all the vertices, so we
341             will not make any more changes to the table. The result is the following table:
342              
343             +--------+---------------+
344             | Vertex | Path | Length |
345             +--------+------+--------+
346             | 0 | 0 | 0 |
347             | 1 | 0 | 1 |
348             | 2 | 1 | 2 |
349             | 3 | 6 | 2 |
350             | 4 | 5 | 2 |
351             | 5 | 0 | 1 |
352             | 6 | 0 | 1 |
353             +--------+------+--------+
354              
355             Now if we need to know how far away a vertex is from vertex 0, we can look it up
356             in the table.
357              
358             =head1 TEAM
359              
360             =head2 Gisbert W Selke (GWS)
361              
362             Author of maps like L, L etc.
363             Also the creator of wonderful plugin L.
364              
365             =head2 Michal Spacek (SKIM)
366              
367             Author of most of the maps e.g. L, L,
368             L, L etc. He is the top in the
369             leader board of maximum number of maps. He has been the source behind many nice
370             features that we have.
371              
372             =head2 Slaven Rezic (SREZIC)
373              
374             Author of map like L.
375              
376             =head1 AUTHOR
377              
378             Mohammad S Anwar, C<< >>
379              
380             =head1 REPOSITORY
381              
382             L
383              
384             =head1 SEE ALSO
385              
386             L
387              
388             =head1 BUGS
389              
390             Please report any bugs or feature requests to C,
391             or through the web interface at L.
392             I will be notified and then you'll automatically be notified of progress on your
393             bug as I make changes.
394              
395             =head1 SUPPORT
396              
397             You can find documentation for this module with the perldoc command.
398              
399             perldoc Map::Tube::Cookbook
400              
401             You can also look for information at:
402              
403             =over 4
404              
405             =item * RT: CPAN's request tracker (report bugs here)
406              
407             L
408              
409             =item * AnnoCPAN: Annotated CPAN documentation
410              
411             L
412              
413             =item * CPAN Ratings
414              
415             L
416              
417             =item * Search CPAN
418              
419             L
420              
421             =back
422              
423             =head1 LICENSE AND COPYRIGHT
424              
425             Copyright (C) 2015 - 2016 Mohammad S Anwar.
426              
427             This program is free software; you can redistribute it and/or modify it under
428             the terms of the the Artistic License (2.0). You may obtain a copy of the full
429             license at:
430              
431             L
432              
433             Any use, modification, and distribution of the Standard or Modified Versions is
434             governed by this Artistic License.By using, modifying or distributing the Package,
435             you accept this license. Do not use, modify, or distribute the Package, if you do
436             not accept this license.
437              
438             If your Modified Version has been derived from a Modified Version made by someone
439             other than you,you are nevertheless required to ensure that your Modified Version
440             complies with the requirements of this license.
441              
442             This license does not grant you the right to use any trademark, service mark,
443             tradename, or logo of the Copyright Holder.
444              
445             This license includes the non-exclusive, worldwide, free-of-charge patent license
446             to make, have made, use, offer to sell, sell, import and otherwise transfer the
447             Package with respect to any patent claims licensable by the Copyright Holder that
448             are necessarily infringed by the Package. If you institute patent litigation
449             (including a cross-claim or counterclaim) against any party alleging that the
450             Package constitutes direct or contributory patent infringement,then this Artistic
451             License to you shall terminate on the date that such litigation is filed.
452              
453             Disclaimer of Warranty: THE PACKAGE IS PROVIDED BY THE COPYRIGHT HOLDER AND
454             CONTRIBUTORS "AS IS' AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES. THE IMPLIED
455             WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR
456             NON-INFRINGEMENT ARE DISCLAIMED TO THE EXTENT PERMITTED BY YOUR LOCAL LAW. UNLESS
457             REQUIRED BY LAW, NO COPYRIGHT HOLDER OR CONTRIBUTOR WILL BE LIABLE FOR ANY DIRECT,
458             INDIRECT, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING IN ANY WAY OUT OF THE USE
459             OF THE PACKAGE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
460              
461             =cut
462              
463             1; # End of Map::Tube::Cookbook