| 1 | package Map::Tube::Cookbook; | ||
| 2 | |||
| 3 | use strict; | ||
| 4 | use warnings; | ||
| 5 | use version; | ||
| 6 | |||
| 7 | our $VERSION = qv('v5.2.0'); | ||
| 8 | our $AUTHORITY = 'cpan:MANWAR'; | ||
| 9 | |||
| 10 | =head1 NAME | ||
| 11 | |||
| 12 | Map::Tube::Cookbook - Cookbook for Map::Tube library. | ||
| 13 | |||
| 14 | =head1 VERSION | ||
| 15 | |||
| 16 | Version v5.2.0 | ||
| 17 | |||
| 18 | =cut | ||
| 19 | |||
| 20 | use v5.14; | ||
| 21 | use strict; use warnings; | ||
| 22 | |||
| 23 | =head1 DESCRIPTION | ||
| 24 | |||
| 25 | Cookbook for L<Map::Tube> library. | ||
| 26 | |||
| 27 | =head1 CREATE A MAP | ||
| 28 | |||
| 29 | C<Map::Tube v3.22> or above supports map data in XML and JSON format. Here is | ||
| 30 | the structure of a map in XML format: | ||
| 31 | |||
| 32 | <?xml version="1.0" encoding="UTF-8"?> | ||
| 33 | <tube name="Your-Map-Name"> | ||
| 34 | <lines> | ||
| 35 | <line id="Line-ID" | ||
| 36 | name="Line-Name" | ||
| 37 | color="Line-Color-Code" /> | ||
| 38 | ..... | ||
| 39 | ..... | ||
| 40 | ..... | ||
| 41 | ..... | ||
| 42 | </lines> | ||
| 43 | |||
| 44 | <stations> | ||
| 45 | <station id="Station-ID" | ||
| 46 | name="Station-Name" | ||
| 47 | line="Line-ID:Station-Index" | ||
| 48 | link="Station-ID" | ||
| 49 | other_link="Link-Name:Station-ID" /> | ||
| 50 | ..... | ||
| 51 | ..... | ||
| 52 | ..... | ||
| 53 | ..... | ||
| 54 | </stations> | ||
| 55 | </tube> | ||
| 56 | |||
| 57 | And the same in JSON format: | ||
| 58 | |||
| 59 | { | ||
| 60 | "name" : "Your-Map-Name", | ||
| 61 | "lines" : { | ||
| 62 | "line" : [ | ||
| 63 | { "id" : "Line-ID", | ||
| 64 | "name" : "Line-Name", | ||
| 65 | "color" : "Line-Color-Code" | ||
| 66 | }, | ||
| 67 | ..... | ||
| 68 | ..... | ||
| 69 | ..... | ||
| 70 | ..... | ||
| 71 | ] | ||
| 72 | }, | ||
| 73 | "stations" : { | ||
| 74 | "station" : [ | ||
| 75 | { "id" : "Station-ID", | ||
| 76 | "name" : "Station-Name", | ||
| 77 | "line" : "Line-ID:Station-Index", | ||
| 78 | "link" : "Station-ID", | ||
| 79 | "other_link" : "Link-Name:Station-ID" | ||
| 80 | }, | ||
| 81 | ..... | ||
| 82 | ..... | ||
| 83 | ..... | ||
| 84 | ..... | ||
| 85 | ] | ||
| 86 | } | ||
| 87 | } | ||
| 88 | |||
| 89 | A more rigorous description of the requirements will be given | ||
| 90 | L<below|/FORMAL-REQUIREMENTS-FOR-MAPS>. Let us start with an informal | ||
| 91 | introduction. | ||
| 92 | |||
| 93 | The root of the XML data is C<tube> which has one optional attribute | ||
| 94 | C<name>, i.e. map name, and two children: C<lines> and C<stations>. | ||
| 95 | |||
| 96 | The node C<lines> has one or more C<line> children. The node C<line> | ||
| 97 | defines one 'line' of the map. The node C<line> has to have the | ||
| 98 | attributes C<id> and C<name>. Optionally it can have C<color> as well. | ||
| 99 | They are explained below: | ||
| 100 | |||
| 101 | +------------+---------------------------------------------------------------+ | ||
| 102 | | Attribute | Description | | ||
| 103 | +------------+---------------------------------------------------------------+ | ||
| 104 | | | | | ||
| 105 | | id | Unique line id of the map. It should consist of printable | | ||
| 106 | | | characters from 7-bit ASCII. It shouldn't contain "," or ":". | | ||
| 107 | | | | | ||
| 108 | | name | Line name of the map. It should be unique since this name is | | ||
| 109 | | | what end users will typically use. | | ||
| 110 | | | | | ||
| 111 | | color | Line color is optional. It should have color name or hexcode. | | ||
| 112 | | | | | ||
| 113 | +------------+---------------------------------------------------------------+ | ||
| 114 | |||
| 115 | Example from L<Map::Tube::Delhi> as shown below: | ||
| 116 | |||
| 117 | <line id="Red" name="Red" color="#8B0000" /> | ||
| 118 | |||
| 119 | The node C<stations> has one or more C<station> children. The node | ||
| 120 | C<station> is used to represent a 'station' of the map. It must have | ||
| 121 | attributes C<id>, C<name>, C<line> and C<link>. It can optionally have | ||
| 122 | an attribute C<other_link>. | ||
| 123 | |||
| 124 | +------------+---------------------------------------------------------------+ | ||
| 125 | | Attribute | Description | | ||
| 126 | +------------+---------------------------------------------------------------+ | ||
| 127 | | | | | ||
| 128 | | id | Unique line id of the map. It should consist of printable | | ||
| 129 | | | characters from 7-bit ASCII. It shouldn't contain "," or ":". | | ||
| 130 | | | | | ||
| 131 | | name | Station name of the map. It should be unique since this name | | ||
| 132 | | | is what end users will typically use. | | ||
| 133 | | | | | ||
| 134 | | line | Represents the station line along with the station index on | | ||
| 135 | | | the line. It should be ":" separated, e.g. "Red:2", meaning | | ||
| 136 | | | this is the second station on line 'Red'. Station index | | ||
| 137 | | | is NOT mandatory but nice to have. If the station is served | | ||
| 138 | | | by more than one line, they should all be listed, separated | | ||
| 139 | | | by ",". For example, "Red:9,Green:16". | | ||
| 140 | | | The lines are referenced by id, not by name. | | ||
| 141 | | | | | ||
| 142 | | link | Represents all stations linked to this station, e.g. "B04". | | ||
| 143 | | | If it is linked to more than one station, they should all be | | ||
| 144 | | | listed, separated by ",". For example, "B04,B02". | | ||
| 145 | | | The stations are referenced by id, not by name. See below | | ||
| 146 | | | for how to restrict links to specific lines. | | ||
| 147 | | | | | ||
| 148 | | other_link | This attribute is optional. This is useful if the station is | | ||
| 149 | | | linked via some other form of link and not by any of the | | ||
| 150 | | | lines, e.g., some stations are linked by tunnel. | | ||
| 151 | | | This can be defined as "Tunnel:B02". | | ||
| 152 | | | | | ||
| 153 | +------------+---------------------------------------------------------------+ | ||
| 154 | |||
| 155 | Example from L<Map::Tube::London> without station index: | ||
| 156 | |||
| 157 | <station id="B003" | ||
| 158 | name="Bank" | ||
| 159 | line="Central,DLR,Northern,Waterloo & City" | ||
| 160 | link="S002,S024,L013,M011,L012,W008" | ||
| 161 | other_link="Tunnel:M009" /> | ||
| 162 | |||
| 163 | Example from L<Map::Tube::Delhi> with station index: | ||
| 164 | |||
| 165 | <station id="B03" | ||
| 166 | name="Dwarka Sector 9" | ||
| 167 | line="Blue:3" | ||
| 168 | link="B04,B02" /> | ||
| 169 | |||
| 170 | Let us create an XML map for the following map: | ||
| 171 | |||
| 172 | A(1) ---- B(2) | ||
| 173 | / \ | ||
| 174 | C(3) -------- F(6) --- G(7) ---- H(8) | ||
| 175 | \ / | ||
| 176 | D(4) ---- E(5) | ||
| 177 | |||
| 178 | Below is the XML representation C<sample.xml> of the above map: | ||
| 179 | |||
| 180 | <?xml version="1.0" encoding="UTF-8"?> | ||
| 181 | <tube name="Sample"> | ||
| 182 | <lines> | ||
| 183 | <line id="L1" name="L1" /> | ||
| 184 | </lines> | ||
| 185 | <stations> | ||
| 186 | <station id="L01" name="A" line="L1:1" link="L02,L03" /> | ||
| 187 | <station id="L02" name="B" line="L1:2" link="L01,L06" /> | ||
| 188 | <station id="L03" name="C" line="L1:3" link="L01,L04,L06" /> | ||
| 189 | <station id="L04" name="D" line="L1:4" link="L03,L05" /> | ||
| 190 | <station id="L05" name="E" line="L1:5" link="L04,L06" /> | ||
| 191 | <station id="L06" name="F" line="L1:6" link="L02,L03,L05,L07" /> | ||
| 192 | <station id="L07" name="G" line="L1:7" link="L06,L08" /> | ||
| 193 | <station id="L08" name="H" line="L1:8" link="L07" /> | ||
| 194 | </stations> | ||
| 195 | </tube> | ||
| 196 | |||
| 197 | Next is the JSON representation C<sample.json> of the above map: | ||
| 198 | |||
| 199 | { | ||
| 200 | "name" : "Sample", | ||
| 201 | "lines" : { "line" : [ { "id" : "L1", "name" : "L1" } ] }, | ||
| 202 | "stations" : { "station" : [ { "id" : "L01", "name": "A", "line": "L1:1", "link": "L02,L03" }, | ||
| 203 | { "id" : "L02", "name": "B", "line": "L1:2", "link": "L01,L06" }, | ||
| 204 | { "id" : "L03", "name": "C", "line": "L1:3", "link": "L01,L04,L06" }, | ||
| 205 | { "id" : "L04", "name": "D", "line": "L1:4", "link": "L03,L05" }, | ||
| 206 | { "id" : "L05", "name": "E", "line": "L1:5", "link": "L04,L06" }, | ||
| 207 | { "id" : "L06", "name": "F", "line": "L1:6", "link": "L02,L03,L05,L07" }, | ||
| 208 | { "id" : "L07", "name": "G", "line": "L1:7", "link": "L06,L08" }, | ||
| 209 | { "id" : "L08", "name": "H", "line": "L1:8", "link": "L07" } | ||
| 210 | ] | ||
| 211 | } | ||
| 212 | } | ||
| 213 | |||
| 214 | =head2 FORMAL REQUIREMENTS FOR MAPS | ||
| 215 | |||
| 216 | These are the requirements for map files. (In the following we will use XML syntax and | ||
| 217 | terminology, which straightforwardly translates into JSON.) | ||
| 218 | |||
| 219 | =over 4 | ||
| 220 | |||
| 221 | =item * Map files SHOULD be UTF8-coded. | ||
| 222 | |||
| 223 | =item * All C<id>s and names of both lines and stations are treated as case-insensitive, i.e., | ||
| 224 | C<MYNAME>, C<myname>, and C<MyName> are considered to be identical. | ||
| 225 | |||
| 226 | =item * The top level element MUST be a C<< <tube> >> element. It MAY have a C<name> attribute | ||
| 227 | giving the human-readable name of the map. | ||
| 228 | It MAY also have other attributes, which will in general be ignored by L<Map::Tube>. | ||
| 229 | |||
| 230 | =item * Under C<< <tube> >>, there MUST be exactly one C<< <lines> >> and exactly one | ||
| 231 | C<< <stations> >> element. | ||
| 232 | |||
| 233 | =item * Under the C<< <lines> >> element, there MUST be one or more C<< <line> >> elements, | ||
| 234 | each completely defining one tube line. | ||
| 235 | |||
| 236 | =item * Each tube line used in the map MUST have exactly one defining C<< <line> >> element. | ||
| 237 | All defined lines MUST be mentioned at at least two stations. | ||
| 238 | |||
| 239 | =item * Each C<< <line> >> element MUST have an C<id> attribute and a C<name> attribute. | ||
| 240 | It MAY have a C<color> attribute. | ||
| 241 | It MAY also have other attributes, which will in general be ignored by L<Map::Tube>. | ||
| 242 | |||
| 243 | =item * The value of the C<id> attribute SHOULD consist of 7-bit printing characters without | ||
| 244 | spaces. It MUST NOT contain a comma (",") or a colon (":"). In general, it will be a | ||
| 245 | rather short string, but this is not required. Each C<id> MUST be unique among the lines. | ||
| 246 | Line C<id>s are case-insensitive, so any two line C<id>s MUST NOT differ only in case. | ||
| 247 | Any line C<id> SHOULD NOT occur also as a station C<id>. C<id>s are usually not seen by | ||
| 248 | end users. | ||
| 249 | |||
| 250 | =item * The C<name> attribute MAY be any string. It MUST be unique among the lines (but it MAY | ||
| 251 | be the same as a station C<name>). Typically, end users will interact with these names, | ||
| 252 | so this should be kept in mind when choosing names. | ||
| 253 | |||
| 254 | =item * The C<color> attribute MAY specify the color which graphical representations of the map | ||
| 255 | SHOULD use for this line. The value MUST be either a color in HTML-style triple-hexadecimal | ||
| 256 | code (C<#RRGGBB>) or one of a set of color names predefined in C<share/color-names.txt>. | ||
| 257 | |||
| 258 | =item * Under the C<< <stations> >> element, there MUST be two or more C<< <station> >> elements, | ||
| 259 | each completely defining one tube station. | ||
| 260 | |||
| 261 | =item * Each tube station used in the map MUST have exactly one defining C<< <station> >> element. | ||
| 262 | Even if a station is served by more than one line, there MUST NOT be more than one | ||
| 263 | C<< <station> >> element for this station. | ||
| 264 | |||
| 265 | =item * Each C<< <station> >> element MUST have an C<id> attribute, a C<name> attribute, a C<line> | ||
| 266 | attribute and a C<link> attribute. It MAY have an C<other_link> attribute. | ||
| 267 | It MAY also have other attributes, which will in general be ignored by L<Map::Tube>. | ||
| 268 | |||
| 269 | =item * The value of the C<id> attribute SHOULD consist of 7-bit printing characters without | ||
| 270 | spaces. It MUST NOT contain a comma (",") or a colon (":"). In general, it will be a | ||
| 271 | rather short string, but this is not required. Each C<id> MUST be unique among the stations. | ||
| 272 | Station C<id>s are case-insensitive, so two station's C<id>s MUST NOT differ only in case. | ||
| 273 | Any station C<id> SHOULD NOT occur also as a line C<id>. C<id>s are usually not seen by | ||
| 274 | end users. | ||
| 275 | |||
| 276 | =item * The C<name> attribute MAY be any string. It MUST be unique among the stations (but it | ||
| 277 | MAY be the same as a line C<name>). Typically, end users will interact with these names, | ||
| 278 | so this should be kept in mind when choosing names. | ||
| 279 | |||
| 280 | =item * The value of the C<line> attribute MUST be a list of one or more I<line-spec>s. If there | ||
| 281 | is more than one I<line-spec>, they MUST be separated by commas (","). Lines MUST NOT | ||
| 282 | be named more than once in any station's I<line-spec>s. | ||
| 283 | |||
| 284 | =item * A I<line-spec> MUST consist of a defined line C<id>, which MAY be followed by a colon | ||
| 285 | (":") and a positive integer. The line C<id> signifies a line serving this station. If the | ||
| 286 | extended form (with colon) is used, the integer signifies the position of this station on | ||
| 287 | the line. Typically, the station at one (arbitrarily chosen) end will be denoted by 1, the | ||
| 288 | next one by 2, etc. The numbers NEED NOT be consecutive, but they MUST be in strictly | ||
| 289 | increasing order. | ||
| 290 | |||
| 291 | =item * Each line MUST either throughout use the extended I<line-spec> form or the short form. | ||
| 292 | Any given line MUST NOT use the extended form at some stations and the short form at | ||
| 293 | others. However, different lines MAY differ in this respect from each other. | ||
| 294 | |||
| 295 | =item * The value of the C<link> attribute MUST be a list of one or more I<link-spec>s. If there is | ||
| 296 | more than one I<link-spec>, they MUST be separated by commas (","). Stations MUST | ||
| 297 | NOT be named more than once in any station's I<link-spec>s. | ||
| 298 | |||
| 299 | =item * A I<link-spec> MUST consist of a defined station C<id>, which MAY be followed by a colon | ||
| 300 | (":") and one or more line C<id>s, separated from each other by vertical bars ("|"). To | ||
| 301 | explain, assume we are looking at the C<< <station> >> element for some station I<A>, and | ||
| 302 | assume one of it's I<link-spec>s names a station I<B>. In the simple form (without colon), | ||
| 303 | it is assumed that all lines shared by stations I<A> and I<B> will connect station I<A> to | ||
| 304 | station I<B>. In the restricted form (with colon), only the lines that are named in the | ||
| 305 | I<link-spec> for station I<B> will be assumed to connect station I<A> to station I<B>. | ||
| 306 | Simple and restricted I<line-spec>s MAY be intermixed freely. The restricted form is useful | ||
| 307 | (and necessary) only in very special circumstances. | ||
| 308 | |||
| 309 | =item * Any line C<id> named in a restricted I<link-spec> of a station MUST also be named in this | ||
| 310 | station's I<line-spec>s. | ||
| 311 | |||
| 312 | =item * For each line named in a station's I<line-spec>s, at least one of the stations named in its | ||
| 313 | I<link-spec>s MUST also name this line in its I<line-spec>s. | ||
| 314 | |||
| 315 | =item * For each station named in a station's C<link-spec>s there MUST be at least one line named | ||
| 316 | in both these stations' I<line-spec>s. | ||
| 317 | |||
| 318 | =item * If a station (say, with C<id> I<A>) names a station (say, with C<id> I<B>) in its | ||
| 319 | I<link-spec>s I<and> vice-versa, this is called a I<bidirectional> link, otherwise it is | ||
| 320 | called a I<unidirectional> link. | ||
| 321 | |||
| 322 | =item * The value of the C<other_link> attribute, if present, MUST be a list of one or more | ||
| 323 | I<other-link-spec>s. If there is more than one I<other-link-spec>, they MUST be separated | ||
| 324 | by commas (","). An I<other-link-spec> describes a non-tube connection between two | ||
| 325 | different stations, usually through some passageway, tunnel or escalator link. | ||
| 326 | |||
| 327 | =item * An I<other-link-spec> MUST consist of an identifier, followed by a colon (":"), followed | ||
| 328 | by the C<id> of a defined station. The identifier doubles as both an id (in that it | ||
| 329 | uniquely identifies an entity) and a name (in that it may be displayed to end users). | ||
| 330 | As such, it SHOULD follow the rules for line C<id>s. The identifier MAY be the C<id> of | ||
| 331 | a defined line. Any line C<id> MUST NOT come up both in some station's CI<link-spec>s | ||
| 332 | I<and> in some (possibly different) station's I<other-link-spec>s. | ||
| 333 | |||
| 334 | =item * A station MAY be named both in another station's I<link-spec>s and its I<other-link-spec>s, | ||
| 335 | although this is unusual. | ||
| 336 | |||
| 337 | =item * For each I<other-link-spec> at some station (say, with C<id> I<A>) that names another | ||
| 338 | station (say, with C<id> I<B>), there MUST be a corresponding I<other-link-spec> at | ||
| 339 | station I<B> that uses the same identifier and names station I<A>. (In other words, | ||
| 340 | I<other-link-spec>s MUST come in pairs, making all such connections bidirectional.) | ||
| 341 | |||
| 342 | =item * A station MUST NOT name itself in its I<link-spec>s nor in its I<other-link-spec>s. | ||
| 343 | |||
| 344 | =item * Usually, lines are I<connected> in the sense that any station on a given line is | ||
| 345 | reachable from each other station on the same line. However, this is not required. | ||
| 346 | |||
| 347 | =item * Usually, maps are I<connected> in the sense that any station on the map is | ||
| 348 | reachable from each other station on the map. However, this is not required. | ||
| 349 | |||
| 350 | =item * As indicated above, maps MAY also use attributes other than those mentioned above. These | ||
| 351 | will in general be ignored by most L<Map::Tube> software. However, your software may make | ||
| 352 | use of the additional data either for its own purposes, or it may make these attributes | ||
| 353 | usable for L<Map::Tube>. E.g., L<Map::Tube::Beijing> and L<Map::Tube::Hongkong> (q.v.) both | ||
| 354 | use additional C<name_alt> attributes in order to provide not only Latin-script (Pinyin) | ||
| 355 | versions of the names but, as an alternative, also Han (Chinese script) names. The version | ||
| 356 | to use is decided when the L<Map::Tube> object is instantiated. (This could also be used to | ||
| 357 | specify alternative station names in I<n>-lingual areas (where I<n> > 1).) | ||
| 358 | |||
| 359 | =back | ||
| 360 | |||
| 361 | |||
| 362 | =head1 WORK WITH A MAP | ||
| 363 | |||
| 364 | You would need C<Map::Tube> v3.22 or above to be able to support the JSON format. | ||
| 365 | |||
| 366 | The following code manages map data in XML format: | ||
| 367 | |||
| 368 | package Sample::Map; | ||
| 369 | |||
| 370 | use Moo; | ||
| 371 | use namespace::clean; | ||
| 372 | |||
| 373 | has xml => (is => 'ro', default => sub { 'sample.xml' }); | ||
| 374 | with 'Map::Tube'; | ||
| 375 | |||
| 376 | package main; | ||
| 377 | use strict; use warnings; | ||
| 378 | |||
| 379 | my $map = Sample::Map->new; | ||
| 380 | print $map->get_shortest_route('A', 'D'); | ||
| 381 | |||
| 382 | In order to support map data in JSON format, just replace the line below: | ||
| 383 | |||
| 384 | has xml => (is => 'ro', default => sub { 'sample.xml' }); | ||
| 385 | |||
| 386 | with | ||
| 387 | |||
| 388 | has json => (is => 'ro', default => sub { 'sample.json' }); | ||
| 389 | |||
| 390 | =head1 MAP GRAPH | ||
| 391 | |||
| 392 | For a graphical representation of the entire map or just a particular line map, | ||
| 393 | just install the plugin L<Map::Tube::Plugin::Graph>, and you have all the tools | ||
| 394 | to create a map image. | ||
| 395 | |||
| 396 | use strict; use warnings; | ||
| 397 | use MIME::Base64; | ||
| 398 | use Sample::Map; | ||
| 399 | |||
| 400 | my $map = Sample::Map->new; | ||
| 401 | my $name = $map->name; | ||
| 402 | open(my $MAP_IMAGE, ">$name.png"); | ||
| 403 | binmode($MAP_IMAGE); | ||
| 404 | print $MAP_IMAGE decode_base64($map->as_image); | ||
| 405 | close($MAP_IMAGE); | ||
| 406 | |||
| 407 | =head1 FUZZY FIND | ||
| 408 | |||
| 409 | To enable the fuzzy search ability to the sample map, you would need to | ||
| 410 | install L<Map::Tube::Plugin::FuzzyFind>, and you have everything you need | ||
| 411 | to perform the task. | ||
| 412 | |||
| 413 | use strict; use warnings; | ||
| 414 | use Sample::Map; | ||
| 415 | |||
| 416 | my $map = Sample::Map->new; | ||
| 417 | print 'Line contains: ', $map->fuzzy_find(search => 'a', object => 'lines'); | ||
| 418 | |||
| 419 | =head1 VALIDATE MAP | ||
| 420 | |||
| 421 | There is a handy package L<Test::Map::Tube> that can help you in testing | ||
| 422 | the basic map structure and functionalities. | ||
| 423 | |||
| 424 | use strict; use warnings; | ||
| 425 | use Test::More; | ||
| 426 | |||
| 427 | my $min_ver = 0.09; | ||
| 428 | eval "use Test::Map::Tube $min_ver tests => 2"; | ||
| 429 | plan skip_all => "Test::Map::Tube $min_ver required" if $@; | ||
| 430 | |||
| 431 | use Sample::Map; | ||
| 432 | my $map = Sample::Map->new; | ||
| 433 | ok_map($map); | ||
| 434 | ok_map_functions($map); | ||
| 435 | |||
| 436 | =head1 SEARCH ALGORITHM | ||
| 437 | |||
| 438 | Map::Tube uses L<Dijkstra's | ||
| 439 | Algorithm|https://en.wikipedia.org/wiki/Dijkstra's_algorithm>, invented | ||
| 440 | and published by computer science pioneer L<Edsger W. | ||
| 441 | Dijkstra|https://en.wikipedia.org/wiki/Edsger_W._Dijkstra> in the 1950s. | ||
| 442 | |||
| 443 | Let us take this sample map. | ||
| 444 | |||
| 445 | 1 -------- 2 | ||
| 446 | / \ / \ | ||
| 447 | / \ / \ | ||
| 448 | 0 ------ 6 ------ 3 | ||
| 449 | \ / \ / | ||
| 450 | \ / \ / | ||
| 451 | 5 -------- 4 | ||
| 452 | |||
| 453 | We would build a table initially as follows: | ||
| 454 | |||
| 455 | +--------+---------------+ | ||
| 456 | | Vertex | Path | Length | | ||
| 457 | +--------+------+--------+ | ||
| 458 | | 0 | - | INF | | ||
| 459 | | 1 | - | INF | | ||
| 460 | | 2 | - | INF | | ||
| 461 | | 3 | - | INF | | ||
| 462 | | 4 | - | INF | | ||
| 463 | | 5 | - | INF | | ||
| 464 | | 6 | - | INF | | ||
| 465 | +--------+------+--------+ | ||
| 466 | |||
| 467 | In the table, the index on the left represents the vertex we are going | ||
| 468 | to (for convenience, we will assume that we are starting at vertex 0). | ||
| 469 | The Path field tells us which vertex precedes us in the path. The | ||
| 470 | Length field is the length of the path from the starting vertex to that | ||
| 471 | vertex, which we initialize to INFinity under the assumption that there | ||
| 472 | is no path unless we find one, in which case the length will be less | ||
| 473 | than infinity. | ||
| 474 | |||
| 475 | We begin by indicating that 0 can reach itself with a path of length 0. | ||
| 476 | This is better than infinity, so we replace INF with 0 in the Length | ||
| 477 | column, and we also place a 0 in the Path column. Now we look at 0's | ||
| 478 | neighbors. All three of 0's neighbors 1, 5, and 6 can be reached from 0 | ||
| 479 | with a path of length 1 (1 + the length of the path to 0, which is 0), | ||
| 480 | and for all three of them this is better than INFinity, so we update | ||
| 481 | their Path and Length fields and then enqueue them because we will have | ||
| 482 | to look at their neighbors next. | ||
| 483 | |||
| 484 | We dequeue 1, and look at its neighbors 0, 2, and 6. The path through | ||
| 485 | vertex 1 to each of those vertices would have a length of 2 (1 + the | ||
| 486 | length of the path to 1, which is 1). For 0 and 6 this is worse than | ||
| 487 | what is already in their Length field so we will do nothing for them. | ||
| 488 | For 2, the path of length 2 is better than infinity, so we will put 2 in | ||
| 489 | its Length field and 1 in its Path field, since it came from 1, and then | ||
| 490 | we will enqueue it so we can eventually look at its neighbors if | ||
| 491 | necessary. | ||
| 492 | |||
| 493 | We dequeue the 5 and look at its neighbors 0, 4, and 6. The path through | ||
| 494 | vertex 5 to each of those vertices would have a length of 2 (1 + the | ||
| 495 | length of the path to 5, which is 1). For 0 and 6, this is worse than | ||
| 496 | what is already in their Length field, so we will do nothing for them. | ||
| 497 | For 4, the path of length 2 is better than infinity, so we will put 2 in | ||
| 498 | its Length field and 5 in its Path field, since it came from 5, and then | ||
| 499 | we will enqueue it so we can eventually look at its neighbors if | ||
| 500 | necessary. | ||
| 501 | |||
| 502 | Next we dequeue the 6, which shares an edge with each of the other six | ||
| 503 | vertices. The path through 6 to any of these vertices would have a | ||
| 504 | length of 2, but only vertex 3 currently has a higher Length (infinity), | ||
| 505 | so we will update 3's fields and enqueue it. | ||
| 506 | |||
| 507 | Of the remaining items in the queue the path through them to their | ||
| 508 | neighbors will all have a length of 3, since they all have a length of | ||
| 509 | 2, which will be worse than the values that are already in the Length | ||
| 510 | fields of all the vertices, so we will not make any more changes to the | ||
| 511 | table. The result is the following table: | ||
| 512 | |||
| 513 | +--------+---------------+ | ||
| 514 | | Vertex | Path | Length | | ||
| 515 | +--------+------+--------+ | ||
| 516 | | 0 | 0 | 0 | | ||
| 517 | | 1 | 0 | 1 | | ||
| 518 | | 2 | 1 | 2 | | ||
| 519 | | 3 | 6 | 2 | | ||
| 520 | | 4 | 5 | 2 | | ||
| 521 | | 5 | 0 | 1 | | ||
| 522 | | 6 | 0 | 1 | | ||
| 523 | +--------+------+--------+ | ||
| 524 | |||
| 525 | Now if we need to know how far away a vertex is from vertex 0, we can | ||
| 526 | look it up in the table. | ||
| 527 | |||
| 528 | =head1 TEAM | ||
| 529 | |||
| 530 | =head2 Gisbert W Selke (GWS) | ||
| 531 | |||
| 532 | Author of maps like L<Glasgow|Map::Tube::Glasgow>, L<Lyon|Map::Tube::Lyon> etc. | ||
| 533 | Also the creator of the wonderful L<Fuzzy Find|Map::Tube::Plugin::FuzzyFind> plugin. | ||
| 534 | |||
| 535 | =head2 Michal Spacek (SKIM) | ||
| 536 | |||
| 537 | Author of most of the maps, e.g. L<Moscow|Map::Tube::Moscow>, | ||
| 538 | L<Kiev|Map::Tube::Kiev>, L<Warsaw|Map::Tube::Warsaw>, | ||
| 539 | L<Sofia|Map::Tube::Sofia> etc. He is the top in the leader board of map | ||
| 540 | authorship. He has been the source behind many nice features that we | ||
| 541 | have. | ||
| 542 | |||
| 543 | =head2 Slaven Rezic (SREZIC) | ||
| 544 | |||
| 545 | Author of maps like L<Berlin|Map::Tube::Berlin>. | ||
| 546 | |||
| 547 | =head1 AUTHOR | ||
| 548 | |||
| 549 | Mohammad Sajid Anwar, C<< <mohammad.anwar at yahoo.com> >> | ||
| 550 | |||
| 551 | =head1 REPOSITORY | ||
| 552 | |||
| 553 | L<https://github.com/manwar/Map-Tube> | ||
| 554 | |||
| 555 | =head1 BUGS | ||
| 556 | |||
| 557 | Please report any bugs or feature requests through the web interface at | ||
| 558 | L<https://github.com/manwar/Map-Tube/issues>. I will be notified and | ||
| 559 | then you'll automatically be notified of progress on your bug as I make | ||
| 560 | changes. | ||
| 561 | |||
| 562 | =head1 SUPPORT | ||
| 563 | |||
| 564 | You can find documentation for this module with the perldoc command. | ||
| 565 | |||
| 566 | perldoc Map::Tube::Cookbook | ||
| 567 | |||
| 568 | You can also look for information at: | ||
| 569 | |||
| 570 | =over 4 | ||
| 571 | |||
| 572 | =item * BUG Report | ||
| 573 | |||
| 574 | L<https://github.com/manwar/Map-Tube/issues> | ||
| 575 | |||
| 576 | =item * Search MetaCPAN | ||
| 577 | |||
| 578 | L<https://metacpan.org/dist/Map-Tube/> | ||
| 579 | |||
| 580 | =back | ||
| 581 | |||
| 582 | =head1 LICENSE AND COPYRIGHT | ||
| 583 | |||
| 584 | Copyright (C) 2010 - 2026 Mohammad Sajid Anwar. | ||
| 585 | |||
| 586 | This program is free software; you can redistribute it and/or modify it under | ||
| 587 | the terms of the the Artistic License (2.0). You may obtain a copy of the full | ||
| 588 | license at: | ||
| 589 | |||
| 590 | L<http://www.perlfoundation.org/artistic_license_2_0> | ||
| 591 | |||
| 592 | Any use, modification, and distribution of the Standard or Modified Versions is | ||
| 593 | governed by this Artistic License.By using, modifying or distributing the Package, | ||
| 594 | you accept this license. Do not use, modify, or distribute the Package, if you do | ||
| 595 | not accept this license. | ||
| 596 | |||
| 597 | If your Modified Version has been derived from a Modified Version made by someone | ||
| 598 | other than you,you are nevertheless required to ensure that your Modified Version | ||
| 599 | complies with the requirements of this license. | ||
| 600 | |||
| 601 | This license does not grant you the right to use any trademark, service mark, | ||
| 602 | tradename, or logo of the Copyright Holder. | ||
| 603 | |||
| 604 | This license includes the non-exclusive, worldwide, free-of-charge patent license | ||
| 605 | to make, have made, use, offer to sell, sell, import and otherwise transfer the | ||
| 606 | Package with respect to any patent claims licensable by the Copyright Holder that | ||
| 607 | are necessarily infringed by the Package. If you institute patent litigation | ||
| 608 | (including a cross-claim or counterclaim) against any party alleging that the | ||
| 609 | Package constitutes direct or contributory patent infringement,then this Artistic | ||
| 610 | License to you shall terminate on the date that such litigation is filed. | ||
| 611 | |||
| 612 | Disclaimer of Warranty: THE PACKAGE IS PROVIDED BY THE COPYRIGHT HOLDER AND | ||
| 613 | CONTRIBUTORS "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES. THE IMPLIED | ||
| 614 | WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR | ||
| 615 | NON-INFRINGEMENT ARE DISCLAIMED TO THE EXTENT PERMITTED BY YOUR LOCAL LAW. UNLESS | ||
| 616 | REQUIRED BY LAW, NO COPYRIGHT HOLDER OR CONTRIBUTOR WILL BE LIABLE FOR ANY DIRECT, | ||
| 617 | INDIRECT, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING IN ANY WAY OUT OF THE USE | ||
| 618 | OF THE PACKAGE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ||
| 619 | |||
| 620 | =cut | ||
| 621 | |||
| 622 | 1; # End of Map::Tube::Cookbook |