1MATLAB(1) User Contributed Perl Documentation MATLAB(1)
2
6 PDL::MATLAB - A guide for MATLAB users.
7
9 If you are a MATLAB user, this page is for you. It explains the key
10 differences between MATLAB and PDL to help you get going as quickly as
11 possible.
12 This document is not a tutorial. For that, go to PDL::QuickStart. This
14 document complements the Quick Start guide, as it highlights the key
15 differences between MATLAB and PDL.
16
18 The key differences between MATLAB and PDL are threading, and Perl.
19 Threading means you can get a reference to just a part of your data,
21 and operate on it in a way that makes sense for your application. Those
22 operations will be reflected in the original data.
23 Perl is a general purpose programming language with thousands of
25 modules freely available on the web. PDL is an extension of Perl. This
26 gives PDL programs access to more features than most numerical tools
27 can dream of. At the same time, most syntax differences between MATLAB
28 and PDL are a result of its Perl foundation.
29 You do not have to learn much Perl to be effective with PDL. But if you
31 wish to learn Perl, there is excellent documentation available on-line
32 (<http://perldoc.perl.org>) or through the command "perldoc perl".
33 There is also a beginner's portal (<http://perl-begin.org>).
34 Perl's module repository is called CPAN (<http://www.cpan.org>) and it
36 has a vast array of modules. Run "perldoc cpan" for more information.
37
39 MATLAB typically refers to vectors, matrices, and arrays. Perl already
40 has arrays, and the terms "vector" and "matrix" typically refer to one-
41 and two-dimensional collections of data. Having no good term to
42 describe their object, PDL developers coined the term "ndarray" to give
43 a name to their data type.
44 A ndarray consists of a series of numbers organized as an N-dimensional
46 data set. ndarrays provide efficient storage and fast computation of
47 large N-dimensional matrices. They are highly optimized for numerical
48 work.
49 For more information, see "ndarrays vs Perl Arrays" later in this
51 document.
52
54 Unlike MATLAB, PDL does not come with a dedicated IDE. It does however
55 come with an interactive shell and you can use a Perl IDE to develop
56 PDL programs.
57 PDL interactive shell
59 To start the interactive shell, open a terminal and run "perldl" or
60 "pdl2". As in MATLAB, the interactive shell is the best way to learn
61 the language. To exit the shell, type "exit", just like MATLAB.
62 Writing PDL programs
64 One popular IDE for Perl is called Padre (<http://padre.perlide.org>).
65 It is cross platform and easy to use.
66 Whenever you write a stand-alone PDL program (i.e. outside the "perldl"
68 or "pdl2" shell) you must start the program with "use PDL;". This
69 command imports the PDL module into Perl. Here is a sample PDL program:
70 use PDL; # Import main PDL module.
72 use PDL::NiceSlice; # Import additional PDL module.
73 use PDL::AutoLoader; # Import additional PDL module.
74 $y = pdl [2,3,4]; # Statements end in semicolon.
76 $A = pdl [ [1,2,3],[4,5,6] ]; # 2-dimensional matrix.
77 print $A x $y->transpose;
79 Save this file as "myprogram.pl" and run it with:
81 perl myprogram.pl
83 New: Flexible syntax
85 In current versions of PDL (version 2.4.7 or later) there is a flexible
86 matrix syntax that can look extremely similar to MATLAB:
87 1) Use spaces to separate elements:
89 $y = pdl q[ 2 3 4 ];
91 2) Use a ';' to delimit rows:
93 $A = pdl q[ 1,2,3 ; 4,5,6 ];
95 Basically, as long as you put a "q" in front of the opening bracket,
97 PDL should "do what you mean". So you can write in a syntax that is
98 more comfortable for you.
99
101 There are two modules that MATLAB users will want to use:
102 PDL::NiceSlice
104 Gives PDL a syntax for slices (sub-matrices) that is shorter and
105 more familiar to MATLAB users.
106 % MATLAB
108 b(1:5) --> Selects the first 5 elements from b.
109 # PDL without NiceSlice
111 $y->slice("0:4") --> Selects the first 5 elements from $y.
112 # PDL with NiceSlice
114 $y(0:4) --> Selects the first 5 elements from $y.
115 PDL::AutoLoader
117 Provides a MATLAB-style autoloader for PDL. If an unknown function
118 "foo()" is called, PDL looks for a file called "foo.pdl". If it
119 finds one, it reads it.
120
122 This section explains how PDL's syntax differs from MATLAB. Most MATLAB
123 users will want to start here.
124 General "gotchas"
126 Indices
127 In PDL, indices start at '0' (like C and Java), not 1 (like MATLAB
128 or FORTRAN). For example, if $y is an array with 5 elements, the
129 elements would be numbered from 0 to 4. This is different, but
130 less difficult as soon as you need to do calculations based on
131 offsets.
132 Displaying an object
134 MATLAB normally displays object contents automatically. In the PDL
135 shells you display objects explicitly with the "print" command or
136 the shortcut "p":
137 MATLAB:
139 >> a = 12
141 a = 12
142 >> b = 23; % Suppress output.
143 >>
144 PDL Shell (perldl or pdl2):
146 pdl> $x = 12 # No output.
148 pdl> print $x # Print object.
149 12
150 pdl> p $x # "p" is a shorthand for "print" in the shell.
151 12
152 pdl>
153 In pdl2 there is the "do_print" command that will toggle the
155 "quiet" mode, which defaults to on. In "print" mode, expressions
156 you enter on the command line will have their values printed.
157 Creating ndarrays
159 Variables in PDL
160 Variables always start with the '$' sign.
161 MATLAB: value = 42
163 PerlDL: $value = 42
164 Basic syntax
166 Use the "pdl" constructor to create a new ndarray.
167 MATLAB: v = [1,2,3,4]
169 PerlDL: $v = pdl [1,2,3,4]
170 MATLAB: A = [ 1,2,3 ; 3,4,5 ]
172 PerlDL: $A = pdl [ [1,2,3] , [3,4,5] ]
173 Simple matrices
175 MATLAB PDL
176 ------ ------
177 Matrix of ones ones(5) ones 5,5
178 Matrix of zeros zeros(5) zeros 5,5
179 Random matrix rand(5) random 5,5
180 Linear vector 1:5 sequence 5
181 Notice that in PDL the parenthesis in a function call are often
183 optional. It is important to keep an eye out for possible
184 ambiguities. For example:
185 pdl> p zeros 2, 2 + 2
187 Should this be interpreted as "zeros(2,2) + 2" or as "zeros 2,
189 (2+2)"? Both are valid statements:
190 pdl> p zeros(2,2) + 2
192 [
193 [2 2]
194 [2 2]
195 ]
196 pdl> p zeros 2, (2+2)
197 [
198 [0 0]
199 [0 0]
200 [0 0]
201 [0 0]
202 ]
203 Rather than trying to memorize Perl's order of precedence, it is
205 best to use parentheses to make your code unambiguous. Remember
206 you may need to come back to your code, and parentheses make your
207 own (as well as others') comprehension easier.
208 Linearly spaced sequences
210 MATLAB: >> linspace(2,10,5)
211 ans = 2 4 6 8 10
212 PerlDL: pdl> p zeroes(5)->xlinvals(2,10)
214 [2 4 6 8 10]
215 Explanation: Start with a 1-dimensional ndarray of 5 elements and
217 give it equally spaced values from 2 to 10.
218 MATLAB has a single function call for this. On the other hand,
220 PDL's method is more flexible:
221 pdl> p zeros(5,5)->xlinvals(2,10)
223 [
224 [ 2 4 6 8 10]
225 [ 2 4 6 8 10]
226 [ 2 4 6 8 10]
227 [ 2 4 6 8 10]
228 [ 2 4 6 8 10]
229 ]
230 pdl> p zeros(5,5)->ylinvals(2,10)
231 [
232 [ 2 2 2 2 2]
233 [ 4 4 4 4 4]
234 [ 6 6 6 6 6]
235 [ 8 8 8 8 8]
236 [10 10 10 10 10]
237 ]
238 pdl> p zeros(3,3,3)->zlinvals(2,6)
239 [
240 [
241 [2 2 2]
242 [2 2 2]
243 [2 2 2]
244 ]
245 [
246 [4 4 4]
247 [4 4 4]
248 [4 4 4]
249 ]
250 [
251 [6 6 6]
252 [6 6 6]
253 [6 6 6]
254 ]
255 ]
256 Slicing and indices
258 Extracting a subset from a collection of data is known as slicing.
259 PDL and MATLAB have a similar syntax for slicing, but there are
260 two important differences:
261 1) PDL indices start at 0, as in C and Java. MATLAB starts indices
263 at 1.
264 2) In MATLAB you think "rows and columns". In PDL, think "x and
266 y".
267 MATLAB PerlDL
269 ------ ------
270 >> A pdl> p $A
271 A = [
272 1 2 3 [1 2 3]
273 4 5 6 [4 5 6]
274 7 8 9 [7 8 9]
275 ]
276 -------------------------------------------------------
277 (row = 2, col = 1) (x = 0, y = 1)
278 >> A(2,1) pdl> p $A(0,1)
279 ans = [
280 4 [4]
281 ]
282 -------------------------------------------------------
283 (row = 2 to 3, col = 1 to 2) (x = 0 to 1, y = 1 to 2)
284 >> A(2:3,1:2) pdl> p $A(0:1,1:2)
285 ans = [
286 4 5 [4 5]
287 7 8 [7 8]
288 ]
289 Warning
291 When you write a stand-alone PDL program, if you want the
292 "nice slice" syntax, you have to include the PDL::NiceSlice
293 module. See the previous section "MODULES FOR MATLAB USERS"
294 for more information.
295 use PDL; # Import main PDL module.
297 use PDL::NiceSlice; # Nice syntax for slicing.
298 use PDL::AutoLoader; # MATLAB-like autoloader.
299 $A = random 4,4;
301 print $A(0,1);
302 Matrix Operations
304 Matrix multiplication
305 MATLAB: A * B
306 PerlDL: $A x $B
307 Element-wise multiplication
309 MATLAB: A .* B
310 PerlDL: $A * $B
311 Transpose
313 MATLAB: A'
314 PerlDL: $A->transpose
315 Functions that aggregate data
317 Some functions (like "sum", "max" and "min") aggregate data for an
318 N-dimensional data set. This is a place where MATLAB and PDL take a
319 different approach:
320 In MATLAB, these functions all work along one dimension.
322 >> A = [ 1,5,4 ; 4,2,1 ]
323 A = 1 5 4
324 4 2 1
325 >> max(A)
326 ans = 4 5 4
327 >> max(A')
328 ans = 5 4
329 If you want the maximum for the entire data set, you can use
331 the special A(:) notation which basically turns the entire
332 data set into a single 1-dimensional vector.
333 >> max(A(:))
335 ans = 5
336 >> A = ones(2,2,2,2)
337 >> max(A(:))
338 ans = 1
339 PDL offers two functions for each feature.
341 sum vs sumover
342 avg vs average
343 max vs maximum
344 min vs minimum
345 The long name works over a dimension, while the short name
347 works over the entire ndarray.
348 pdl> p $A = pdl [ [1,5,4] , [4,2,1] ]
350 [
351 [1 5 4]
352 [4 2 1]
353 ]
354 pdl> p $A->maximum
355 [5 4]
356 pdl> p $A->transpose->maximum
357 [4 5 4]
358 pdl> p $A->max
359 5
360 pdl> p ones(2,2,2)->max
361 1
362 pdl> p ones(2,2,2,2)->max
363 1
364 Note Notice that PDL aggregates horizontally while MATLAB aggregates
366 vertically. In other words:
367 MATLAB PerlDL
369 max(A) == $A->transpose->maximum
370 max(A') == $A->maximum
371 TIP: In MATLAB you think "rows and columns". In PDL, think "x and
373 y".
374 Higher dimensional data sets
376 A related issue is how MATLAB and PDL understand data sets of higher
377 dimension. MATLAB was designed for 1D vectors and 2D matrices. Higher
378 dimensional objects ("N-D arrays") were added on top. In contrast, PDL
379 was designed for N-dimensional ndarrays from the start. This leads to a
380 few surprises in MATLAB that don't occur in PDL:
381 MATLAB sees a vector as a 2D matrix.
383 MATLAB PerlDL
384 ------ ------
385 >> vector = [1,2,3,4]; pdl> $vector = pdl [1,2,3,4]
386 >> size(vector) pdl> p $vector->dims
387 ans = 1 4 4
388 MATLAB sees "[1,2,3,4]" as a 2D matrix (1x4 matrix). PDL sees it
390 as a 1D vector: A single dimension of size 4.
391 But MATLAB ignores the last dimension of a 4x1x1 matrix.
393 MATLAB PerlDL
394 ------ ------
395 >> A = ones(4,1,1); pdl> $A = ones 4,1,1
396 >> size(A) pdl> p $A->dims
397 ans = 4 1 4 1 1
398 And MATLAB treats a 4x1x1 matrix differently from a 1x1x4 matrix.
400 MATLAB PerlDL
401 ------ ------
402 >> A = ones(1,1,4); pdl> $A = ones 1,1,4
403 >> size(A) pdl> p $A->dims
404 ans = 1 1 4 1 1 4
405 MATLAB has no direct syntax for N-D arrays.
407 pdl> $A = pdl [ [[1,2,3],[4,5,6]], [[2,3,4],[5,6,7]] ]
408 pdl> p $A->dims
409 3 2 2
410 Feature support.
412 In MATLAB, several features such as sparse matrix support are not
413 available for N-D arrays. In PDL, just about any feature supported
414 by 1D and 2D ndarrays, is equally supported by N-dimensional
415 ndarrays. There is usually no distinction.
416 Loop Structures
418 Perl has many loop structures, but we will only show the one that is
419 most familiar to MATLAB users:
420 MATLAB PerlDL
422 ------ ------
423 for i = 1:10 for $i (1..10) {
424 disp(i) print $i
425 endfor }
426 Note Never use for-loops for numerical work. Perl's for-loops are
428 faster than MATLAB's, but they both pale against a "vectorized"
429 operation. PDL has many tools that facilitate writing vectorized
430 programs. These are beyond the scope of this guide. To learn
431 more, see: PDL::Indexing, PDL::Threading, and PDL::PP.
432 Likewise, never use 1..10 for numerical work, even outside a for-
434 loop. 1..10 is a Perl array. Perl arrays are designed for
435 flexibility, not speed. Use ndarrays instead. To learn more, see
436 the next section.
437 ndarrays vs Perl Arrays
439 It is important to note the difference between a ndarray and a Perl
440 array. Perl has a general-purpose array object that can hold any type
441 of element:
442 @perl_array = 1..10;
444 @perl_array = ( 12, "Hello" );
445 @perl_array = ( 1, 2, 3, \@another_perl_array, sequence(5) );
446 Perl arrays allow you to create powerful data structures (see Data
448 structures below), but they are not designed for numerical work. For
449 that, use ndarrays:
450 $pdl = pdl [ 1, 2, 3, 4 ];
452 $pdl = sequence 10_000_000;
453 $pdl = ones 600, 600;
454 For example:
456 $points = pdl 1..10_000_000 # 4.7 seconds
458 $points = sequence 10_000_000 # milliseconds
459 TIP: You can use underscores in numbers ("10_000_000" reads better than
461 10000000).
462 Conditionals
464 Perl has many conditionals, but we will only show the one that is most
465 familiar to MATLAB users:
466 MATLAB PerlDL
468 ------ ------
469 if value > MAX if ($value > $MAX) {
470 disp("Too large") print "Too large\n";
471 elseif value < MIN } elsif ($value < $MIN) {
472 disp("Too small") print "Too small\n";
473 else } else {
474 disp("Perfect!") print "Perfect!\n";
475 end }
476 Note Here is a "gotcha":
478 MATLAB: elseif
480 PerlDL: elsif
481 If your conditional gives a syntax error, check that you wrote
483 your "elsif"'s correctly.
484 TIMTOWDI (There Is More Than One Way To Do It)
486 One of the most interesting differences between PDL and other tools is
487 the expressiveness of the Perl language. TIMTOWDI, or "There Is More
488 Than One Way To Do It", is Perl's motto.
489 Perl was written by a linguist, and one of its defining properties is
491 that statements can be formulated in different ways to give the
492 language a more natural feel. For example, you are unlikely to say to a
493 friend:
494 "While I am not finished, I will keep working."
496 Human language is more flexible than that. Instead, you are more likely
498 to say:
499 "I will keep working until I am finished."
501 Owing to its linguistic roots, Perl is the only programming language
503 with this sort of flexibility. For example, Perl has traditional while-
504 loops and if-statements:
505 while ( ! finished() ) {
507 keep_working();
508 }
509 if ( ! wife_angry() ) {
511 kiss_wife();
512 }
513 But it also offers the alternative until and unless statements:
515 until ( finished() ) {
517 keep_working();
518 }
519 unless ( wife_angry() ) {
521 kiss_wife();
522 }
523 And Perl allows you to write loops and conditionals in "postfix" form:
525 keep_working() until finished();
527 kiss_wife() unless wife_angry();
529 In this way, Perl often allows you to write more natural, easy to
531 understand code than is possible in more restrictive programming
532 languages.
533 Functions
535 PDL's syntax for declaring functions differs significantly from
536 MATLAB's.
537 MATLAB PerlDL
539 ------ ------
540 function retval = foo(x,y) sub foo {
541 retval = x.**2 + x.*y my ($x, $y) = @_;
542 endfunction return $x**2 + $x*$y;
543 }
544 Don't be intimidated by all the new syntax. Here is a quick run through
546 a function declaration in PDL:
547 1) "sub" stands for "subroutine".
549 2) "my" declares variables to be local to the function. This helps you
551 not accidentally use undeclared variables, which is enforced if you
552 "use strict". See strict for more.
553 3) "@_" is a special Perl array that holds all the function parameters.
555 This might seem like a strange way to do functions, but it allows you
556 to make functions that take a variable number of parameters. For
557 example, the following function takes any number of parameters and adds
558 them together:
559 sub mysum {
561 my ($i, $total) = (0, 0);
562 for $i (@_) {
563 $total += $i;
564 }
565 return $total;
566 }
567 In more recent versions of Perl, you can "use signatures" for a
569 different syntax for declaring function parameters. See signatures for
570 more.
571 4) You can assign values to several variables at once using the syntax:
573 ($x, $y, $z) = (1, 2, 3);
575 So, in the previous examples:
577 # This declares two local variables and initializes them to 0.
579 my ($i, $total) = (0, 0);
580 # This takes the first two elements of @_ and puts them in $x and $y.
582 my ($x, $y) = @_;
583 5) The "return" statement gives the return value of the function, if
585 any.
586
588 ASCII File IO
589 To read data files containing whitespace separated columns of numbers
590 (as would be read using the MATLAB load command) one uses the PDL rcols
591 in PDL::IO::Misc. For a general review of the IO functionality
592 available in PDL, see the documentation for PDL::IO, e.g., "help
593 PDL::IO" in the pdl2 shell or " pdldoc PDL::IO " from the shell command
594 line.
595 Data structures
597 To create complex data structures, MATLAB uses "cell arrays" and
598 "structure arrays". Perl's arrays and hashes offer similar
599 functionality but are more powerful and flexible. This section is only
600 a quick overview of what Perl has to offer. To learn more about this,
601 please go to <http://perldoc.perl.org/perldata.html> or run the command
602 "perldoc perldata".
603 Arrays
605 Perl arrays are similar to MATLAB's cell arrays, but more
606 flexible. For example, in MATLAB, a cell array is still
607 fundamentally a matrix. It is made of rows, and rows must have the
608 same length.
609 MATLAB
611 ------
612 array = {1, 12, 'hello'; rand(3, 2), ones(3), 'junk'}
613 => OK
614 array = {1, 12, 'hello'; rand(3, 2), ones(3) }
615 => ERROR
616 A Perl array is a general purpose, sequential data structure. It
618 can contain any data type.
619 PerlDL
621 ------
622 @array = ( [1, 12, 'hello'] , [ random(3,2), ones(3,3), 'junk' ] )
623 => OK
624 @array = ( [1, 12, 'hello'] , [ random(3,2), ones(3,3) ] )
625 => OK
626 @array = ( 5 , {'name' => 'Mike'} , [1, 12, 'hello'] )
627 => OK
628 Notice that Perl array's start with the "@" prefix instead of the
630 "$" used by ndarrays.
631 To learn about Perl arrays, please go to
633 <http://perldoc.perl.org/perldata.html> or run the command
634 "perldoc perldata".
635 Hashes
637 Perl hashes are similar to MATLAB's structure arrays:
638 MATLAB
640 ------
641 >> drink = struct('type', 'coke', 'size', 'large', 'myarray', {1,2,3})
642 >> drink.type = 'sprite'
643 >> drink.price = 12 % Add new field to structure array.
644 PerlDL
646 ------
647 pdl> %drink = ( type => 'coke' , size => 'large', myndarray => ones(3,3,3) )
648 pdl> $drink{type} = 'sprite'
649 pdl> $drink{price} = 12 # Add new field to hash.
650 Notice that Perl hashes start with the "%" prefix instead of the
652 "@" for arrays and "$" used by ndarrays.
653 To learn about Perl hashes, please go to
655 <http://perldoc.perl.org/perldata.html> or run the command
656 "perldoc perldata".
657 Performance
659 PDL has powerful performance features, some of which are not normally
660 available in numerical computation tools. The following pages will
661 guide you through these features:
662 PDL::Indexing
664 Level: Beginner
665 This beginner tutorial covers the standard "vectorization" feature
667 that you already know from MATLAB. Use this page to learn how to
668 avoid for-loops to make your program more efficient.
669 PDL::Threading
671 Level: Intermediate
672 PDL's "vectorization" feature goes beyond what most numerical
674 software can do. In this tutorial you'll learn how to "thread"
675 over higher dimensions, allowing you to vectorize your program
676 further than is possible in MATLAB.
677 Benchmarks
679 Level: Intermediate
680 Perl comes with an easy to use benchmarks module to help you find
682 how long it takes to execute different parts of your code. It is a
683 great tool to help you focus your optimization efforts. You can
684 read about it online (<http://perldoc.perl.org/Benchmark.html>) or
685 through the command "perldoc Benchmark".
686 PDL::PP
688 Level: Advanced
689 PDL's Pre-Processor is one of PDL's most powerful features. You
691 write a function definition in special markup and the pre-
692 processor generates real C code which can be compiled. With PDL:PP
693 you get the full speed of native C code without having to deal
694 with the full complexity of the C language.
695 Plotting
697 PDL has full-featured plotting abilities. Unlike MATLAB, PDL relies
698 more on third-party libraries (pgplot and PLplot) for its 2D plotting
699 features. Its 3D plotting and graphics uses OpenGL for performance and
700 portability. PDL has three main plotting modules:
701 PDL::Graphics::PGPLOT
703 Best for: Plotting 2D functions and data sets.
704 This is an interface to the venerable PGPLOT library. PGPLOT has
706 been widely used in the academic and scientific communities for
707 many years. In part because of its age, PGPLOT has some
708 limitations compared to newer packages such as PLplot (e.g. no RGB
709 graphics). But it has many features that still make it popular in
710 the scientific community.
711 PDL::Graphics::PLplot
713 Best for: Plotting 2D functions as well as 2D and 3D data sets.
714 This is an interface to the PLplot plotting library. PLplot is a
716 modern, open source library for making scientific plots. It
717 supports plots of both 2D and 3D data sets. PLplot is best
718 supported for unix/linux/macosx platforms. It has an active
719 developers community and support for win32 platforms is improving.
720 PDL::Graphics::TriD
722 Best for: Plotting 3D functions.
723 The native PDL 3D graphics library using OpenGL as a backend for
725 3D plots and data visualization. With OpenGL, it is easy to
726 manipulate the resulting 3D objects with the mouse in real time.
727 Writing GUIs
729 Through Perl, PDL has access to all the major toolkits for creating a
730 cross platform graphical user interface. One popular option is wxPerl
731 (<http://wxperl.sourceforge.net>). These are the Perl bindings for
732 wxWidgets, a powerful GUI toolkit for writing cross-platform
733 applications.
734 wxWidgets is designed to make your application look and feel like a
736 native application in every platform. For example, the Perl IDE Padre
737 is written with wxPerl.
738 Simulink
740 Simulink is a graphical dynamical system modeler and simulator. It can
741 be purchased separately as an add-on to MATLAB. PDL and Perl do not
742 have a direct equivalent to MATLAB's Simulink. If this feature is
743 important to you, then take a look at Scilab:
744 <http://www.scilab.org>
746 Scilab is another numerical analysis software. Like PDL, it is free and
748 open source. It doesn't have PDL's unique features, but it is very
749 similar to MATLAB. Scilab comes with Xcos (previously Scicos), a
750 graphical system modeler and simulator similar to Simulink.
751
753 In graph theory <https://en.wikipedia.org/wiki/Graph_theory>, an
754 apparently-simple but difficult problem is the "shortest path" problem,
755 of finding the shortest path between any two nodes. A famous solution
756 to this, albeit expensive (it is "O(V^3)" where "V" is the number of
757 vertices) is the Floyd-Warshall algorithm, which iterates through all
758 the possible paths.
759 Both the MATLAB solution and the PDL solution use vectorisation, so
761 hopefully this is a useful comparison. The MATLAB version started with
762 the code in code by Giorgos Dim
763 <https://uk.mathworks.com/matlabcentral/fileexchange/67503-floyd-
764 warshall-vectorized>, but modified as that code produces an incorrect
765 path matrix.
766 Sample data (reflected on both the Wikipedia page, and the Rosetta Code
768 website) for the weighted-edges matrix is, in PDL format:
769 my $we = pdl q[
771 [Inf Inf -2 Inf]
772 [ 4 Inf 3 Inf]
773 [Inf Inf Inf 2]
774 [Inf -1 Inf Inf]
775 ];
776 and in MATLAB format:
778 A = [0 Inf -2 Inf; 4 0 3 Inf; Inf Inf 0 2; Inf -1 Inf 0]
780 PDL version
782 To solve for only distances without capturing the shortest actual
783 paths:
784 $we .= $we->hclip($we->mslice('X', $_) + $we->mslice($_, 'X'))
786 for 0..($we->dim(0)-1);
787 This loops over each possible intermediate point ("k" in the other
789 literature), setting it to $_ (a Perl idiom). It uses "hclip" in
790 PDL::Primitive for vectorised calculation of the distance between the
791 intermediate point's predecessors and successors. Those are the two
792 components of the addition expression, using "slices" alluded to above.
793 The ".=" is the PDL syntax for updating an ndarray.
794 To capture the shortest-path "next vertex" matrix as well:
796 use PDL::Lite;
798 my $d = $we->copy->inplace;
799 $d->diagonal(0, 1) .= 0;
800 my $suc = $we->copy->inplace;
801 my $adjacent_coords = PDL::whichND($we->isfinite);
802 $suc->indexND($adjacent_coords) .= $adjacent_coords->slice(0)->flat;
803 $suc->diagonal(0, 1) .= PDL::Basic::sequence($d->dim(0));
804 for (my $k = $d->dim(0)-1; $k >= 0; $k--) {
805 my $d_copy = $d->copy;
806 $d .= $d->hclip($d->mslice('X', $k) + $d->mslice($k, 'X'));
807 my $coords = PDL::whichND($d < $d_copy);
808 my $from_coords = $coords->copy->inplace;
809 $from_coords->slice(0) .= $k;
810 $suc->indexND($coords) .= $suc->indexND($from_coords);
811 }
812 The "diagonal" and "slice" expressions show how to update data via a
814 query syntax.
815 MATLAB version
817 Path-lengths only:
818 function D = FloydWarshall(D)
820 for k = 1:length(D)
821 D = min(D,D(:,k) + D(k,:));
822 end
823 end
824 The path vertices-capturing as well:
826 function [D,P] = FloydWarshall(D)
828 P = D;
829 n = length(D);
830 coords = find(isfinite(P));
831 P(coords) = floor((coords-1) / n)+1; % the col in 1-based
832 for v = 1:n; P(v, v) = v; end
833 for k = 1:n
834 prevD = D;
835 D = min(D,D(:,k) + D(k,:));
836 coords = find(D<prevD);
837 from_coords = n * (k-1) + mod(coords-1, n) + 1; % change col to k in 1-based
838 P(coords) = P(from_coords);
839 end
840 end
841 By comparison, the lack of "threading" means that to update the
843 diagonal requires a for-loop, which in the sphere of vectorised
844 calculations is a bad thing. The calculations of coordinates are
845 complicated by the 1-based counting.
846
848 Copyright 2010 Daniel Carrera (dcarrera@gmail.com). You can distribute
849 and/or modify this document under the same terms as the current Perl
850 license.
851 See: <http://dev.perl.org/licenses/>
853
855 I'd like to thank David Mertens, Chris Marshall and Sigrid Carrera for
856 their immense help reviewing earlier drafts of this guide. Without
857 their hours of work, this document would not be remotely as useful to
858 MATLAB users as it is today.
859perl v5.34.0 2021-08-16 MATLAB(1)