Pathologically Eclectic Rubbish Lister  
PerlMonks 
Is this a valid approach to finding if a path through a set of points has completed?by atcroft (Abbot) 
on Jul 16, 2018 at 07:26 UTC ( #1218535=perlquestion: print w/replies, xml )  Need Help?? 
atcroft has asked for the wisdom of the Perl Monks concerning the following question: (I considered submitting this as a meditation, but due to my lack of knowledge on the topic, I thought better of posting there.) Recently I was thinking about a problem. Specifically, I was considering the idea from the point of view of "ants" (for lack of a better term) following all of the possible paths, and trying to think through how to determine if a path has been completed. As a starting thought experiment, I considered 6 points, with ants moving from each point to each remaining point. I thought of 5 different cases that could occur (points labeled '1'..'6', paths written ordered least to greatest):
The cases map out (roughly) as follows: Case 1: 1  2  3 6 5 4 Case 2: 1  2  3 \ 6  5  4 Case 3: 1  2  3 \ 6  5  4 \ / + Case 4: 1  2  3 \ \ 6  5  4 Case 5: 1  2  3 \ /  \ 6  5  4 \ / + (I realized as I was writing this that being able to find that a path might not be as useful as I thought, but that does not take *that much* away from this question.) I'm not aware of (or at least remember) dealing with graphs in the CS classes I took (years ago), so there may be a nice theory or approach I am not aware of. What I came up with was to create a matrix containing the number of connections between between points. (By writing all of the connections in leastgreatest ordering, only half the matrix had to be used, as illustrated by the following. Unfilled entries are noted as '', otherwise the count of connections is filled in in rowcolumn order.) Case 1 Case 2 Case 3 Case 4 Case 5 X 1 2 3 4 5 6 X 1 2 3 4 5 6 X 1 2 3 4 5 6 X 1 2 3 4 5 6 X 1 2 3 4 5 6 1  1 0 0 0 0 1  1 0 0 0 1 1  1 0 0 0 1 1  1 0 0 0 1 1  1 0 0 0 1 2   1 0 0 0 2   1 0 0 0 2   1 0 0 0 2   1 0 0 0 2   1 0 0 0 3    0 0 0 3    0 0 0 3    0 0 0 3    1 0 0 3    1 1 1 4     0 0 4     1 0 4     1 1 4     1 0 4     1 1 5      0 5      1 5      1 5      1 5      1 6       6       6       6       6       What I noticed was that in the cases (13) where a connection did not exist, there was at least one row in which the sum of entries on the row was zero, but in cases where a full path existed all rows had a nonzero sum. Is this approach too simplisticminded (or did I just stumble upon something I should have known)? Sample code:
Output: $ ./test.pl test_1 Missing row 3 Missing row 4 Missing row 5 test_2 Missing row 3 test_3 Missing row 3 test_4 test_5 Thank you for your attention and insights. (And my apologies if I have wasted your time.) Update: 20180716 Thank you for your feedback. To answer OM and tobyink, yes, apparently what I am looking for is a Hamiltonian path through the set. (I didn't know the proper term(s) to use to search, among other things.) To answer bliako, yes, I know ants would have started from each point, but for simplicity I showed only completed paths of equal length. To apply this to the original problem, I can see two ways: a) follow the idea of an actual ant, and track each ant's actual position, or b) knowing the edges and their lengths, I would probably look to move down the list of all edges (tracking the sum total) and update the matrix form (above, or other method) to check if a complete path exists.
Back to
Seekers of Perl Wisdom

