There's more than one way to do things PerlMonks

### Re^3: Data visualisation.

by roboticus (Chancellor)
 on Jan 02, 2014 at 15:14 UTC ( #1068970=note: print w/replies, xml ) Need Help??

in reply to Re^2: Data visualisation.

LanX:

No, I didn't think to do that. It's a trivial check, so when I get home, I'll try to remember to add that. (Unfortunately, the security restrictions at work make it extremely difficult to actually do any coding.)

Update: I've now added the triangle inequality check in the version at Re: Data visualisation..

Update 2: There was an error in my triangle inequality check (it didn't affect my original results, because my code didn't use any of the invalid triangles--by luck, not design). The error was that I only made one of the three checks required. The new check function is:

```sub chk_triangle_inequality {
# Get the points
my (\$A, \$B, \$C) = @_;

# Calc the distances
my (\$AB, \$AC, \$BC) = (dist_2(\$A, \$B), dist_2(\$A, \$C), dist_2(\$B, \$
+C));

if (\$AB > \$AC + \$BC) {
print "ERROR: Triangle inequality fails for points (\$A, \$B, \$C
+) (\$AB > \$AC+\$BC)\n";
}
elsif (\$AC > \$AB + \$BC) {
print "ERROR: Triangle inequality fails for points (\$A, \$B, \$C
+) (\$AC > \$AB+\$BC)\n";
}
elsif (\$BC > \$AB + \$AC) {
print "ERROR: Triangle inequality fails for points (\$A, \$B, \$C
+) (\$BC > \$AB+\$AC)\n";
}
}

I also added an exhaustive check at the end:

```print <<EOHDR;
#####
# Exhaustive triangle inequality check
#####
EOHDR
for my \$A (0 .. (\$#LOCs-2) ) {
for my \$B ( (\$A+1) .. (\$#LOCs-1) ) {
for my \$C ( (\$B+1) .. \$#LOCs ) {
chk_triangle_inequality(\$A, \$B, \$C);
}
}
}

The exhaustive check gives the following misses:

```#####
# Exhaustive triangle inequality check
#####
ERROR: Triangle inequality fails for points (0, 5, 6) (150 > 80+63)
ERROR: Triangle inequality fails for points (0, 6, 7) (134 > 80+29)
ERROR: Triangle inequality fails for points (0, 6, 15) (332 > 80+246)
ERROR: Triangle inequality fails for points (0, 6, 16) (121 > 80+29)
ERROR: Triangle inequality fails for points (1, 2, 3) (661 > 390+228)
ERROR: Triangle inequality fails for points (1, 2, 13) (466 > 390+74)
ERROR: Triangle inequality fails for points (1, 3, 4) (661 > 227+383)
ERROR: Triangle inequality fails for points (1, 3, 5) (661 > 488+120)
ERROR: Triangle inequality fails for points (1, 3, 6) (661 > 572+77)
ERROR: Triangle inequality fails for points (1, 3, 7) (661 > 530+105)
ERROR: Triangle inequality fails for points (1, 3, 10) (661 > 282+324)
ERROR: Triangle inequality fails for points (1, 3, 12) (661 > 567+27)
ERROR: Triangle inequality fails for points (1, 3, 13) (661 > 466+182)
ERROR: Triangle inequality fails for points (1, 3, 14) (661 > 420+239)
ERROR: Triangle inequality fails for points (1, 3, 16) (661 > 518+84)
ERROR: Triangle inequality fails for points (1, 5, 6) (572 > 488+63)
ERROR: Triangle inequality fails for points (1, 5, 7) (530 > 488+34)
ERROR: Triangle inequality fails for points (1, 6, 7) (572 > 530+29)
ERROR: Triangle inequality fails for points (1, 6, 16) (572 > 518+29)
ERROR: Triangle inequality fails for points (2, 3, 12) (228 > 191+27)
ERROR: Triangle inequality fails for points (2, 3, 15) (472 > 228+237)
ERROR: Triangle inequality fails for points (2, 3, 16) (228 > 142+84)
ERROR: Triangle inequality fails for points (2, 5, 6) (196 > 112+63)
ERROR: Triangle inequality fails for points (2, 5, 7) (154 > 112+34)
ERROR: Triangle inequality fails for points (2, 6, 7) (196 > 154+29)
ERROR: Triangle inequality fails for points (2, 6, 16) (196 > 142+29)
ERROR: Triangle inequality fails for points (3, 4, 12) (383 > 27+346)
ERROR: Triangle inequality fails for points (3, 4, 16) (383 > 84+297)
ERROR: Triangle inequality fails for points (3, 5, 12) (120 > 27+83)
ERROR: Triangle inequality fails for points (3, 5, 15) (364 > 120+237)
ERROR: Triangle inequality fails for points (3, 5, 16) (120 > 84+35)
ERROR: Triangle inequality fails for points (3, 6, 12) (77 > 27+47)
ERROR: Triangle inequality fails for points (3, 6, 15) (332 > 77+237)
ERROR: Triangle inequality fails for points (3, 7, 12) (105 > 27+68)
ERROR: Triangle inequality fails for points (3, 7, 15) (349 > 105+237)
ERROR: Triangle inequality fails for points (3, 9, 12) (476 > 27+439)
ERROR: Triangle inequality fails for points (3, 9, 16) (476 > 84+390)
ERROR: Triangle inequality fails for points (3, 10, 12) (324 > 27+287)
ERROR: Triangle inequality fails for points (3, 10, 16) (324 > 84+238)
ERROR: Triangle inequality fails for points (3, 12, 13) (182 > 27+145)
ERROR: Triangle inequality fails for points (3, 12, 14) (239 > 27+202)
ERROR: Triangle inequality fails for points (3, 12, 15) (289 > 27+237)
ERROR: Triangle inequality fails for points (3, 12, 16) (84 > 27+55)
ERROR: Triangle inequality fails for points (3, 13, 15) (426 > 182+237
+)
ERROR: Triangle inequality fails for points (3, 13, 16) (182 > 84+96)
ERROR: Triangle inequality fails for points (3, 14, 15) (483 > 239+237
+)
ERROR: Triangle inequality fails for points (3, 14, 16) (239 > 84+153)
ERROR: Triangle inequality fails for points (3, 15, 16) (336 > 237+84)
ERROR: Triangle inequality fails for points (4, 5, 6) (351 > 267+63)
ERROR: Triangle inequality fails for points (4, 5, 7) (309 > 267+34)
ERROR: Triangle inequality fails for points (4, 6, 7) (351 > 309+29)
ERROR: Triangle inequality fails for points (4, 6, 16) (351 > 297+29)
ERROR: Triangle inequality fails for points (5, 6, 9) (444 > 63+360)
ERROR: Triangle inequality fails for points (5, 6, 10) (292 > 63+208)
ERROR: Triangle inequality fails for points (5, 6, 14) (207 > 63+123)
ERROR: Triangle inequality fails for points (5, 7, 9) (402 > 34+360)
ERROR: Triangle inequality fails for points (5, 7, 10) (250 > 34+208)
ERROR: Triangle inequality fails for points (5, 7, 14) (165 > 34+123)
ERROR: Triangle inequality fails for points (6, 7, 9) (444 > 29+402)
ERROR: Triangle inequality fails for points (6, 7, 10) (292 > 29+250)
ERROR: Triangle inequality fails for points (6, 7, 13) (150 > 29+108)
ERROR: Triangle inequality fails for points (6, 7, 14) (207 > 29+165)
ERROR: Triangle inequality fails for points (6, 9, 16) (444 > 29+390)
ERROR: Triangle inequality fails for points (6, 10, 16) (292 > 29+238)
ERROR: Triangle inequality fails for points (6, 13, 16) (150 > 29+96)
ERROR: Triangle inequality fails for points (6, 14, 16) (207 > 29+153)
ERROR: Triangle inequality fails for points (9, 13, 14) (336 > 240+57)

...roboticus

When your only tool is a hammer, all problems look like your thumb.

Replies are listed 'Best First'.
Re^4: Data visualisation.
by LanX (Chancellor) on Jan 04, 2014 at 09:38 UTC
Hi roboticus

> triangle inequality check

Already a visual test reveals that projecting the data into 2D wouldn't make sense:

```      M
/ \
27 /   \ 47
/     \
D ----- G
77

27 + 47 = 74 < 77

```     A    B    C    D    E    F    G

G:  80  572  196  *77  351   63    0 ...
...
M:  70  567  191  *27  346   83  *47 ...

Cheers Rolf

( addicted to the Perl Programming Language)

• improved wording

LanX:

Yeah, my original triangle check was faulty. I only checked one case, rather than all three. Using your data, I had only a 1/3 chance of detecting that particular triangle as failing the inequality:

47 < 27 + 77 : Passes

27 < 47 + 77 : Passes

77 !< 27 + 47 : Fails...

Since I only checked one case, I'd've missed a bad triangle. But my code didn't check all that many triangles, either, so it missed anyway. So I added an exhaustive check just for the helluvit. I've updated the node above accordingly.

...roboticus

When your only tool is a hammer, all problems look like your thumb.

So I added an exhaustive check just for the helluvit.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Already a visual test shows the data doesn't make sense:

The data makes perfect sense; only you don't.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
> The data makes perfect sense; only you don't.

For completeness, since others may be interested:

According to the documentation (which someone didn't care to read or even to kindly provide for his fellow monks) is "gr17" of edge-weight-type EXPLICIT and not EUC_2D or GEO, so no indication that a geometrical visualization was ever possible.

TSP is a general problem class for all kind of metrics (e.g. routing in network clusters), not restricted to printable graphs of real cities.

If someone needs problems with visualization he can easily refer to other EUC_2D examples like eil51 which are euclidean and provide the necessary coordinates. (for trivial distance function see aforementioned documentation).

Smaller examples (i.e. less "cities") can be found in the GEO group, planar projections of spherical data shouldn't be a problem for a mechanical engineer of certain ego.

##### udpate

mailed author of webpage.

Re^4: Data visualisation.
by LanX (Chancellor) on Jan 06, 2014 at 10:22 UTC
Hi roboticus,

> Update 2... The exhaustive check gives the following misses:

wow ...indeed "a mess of bad triangles".

TSP publications reach back to before the 1950s and IIRC the data was mostly taken from German or Swiss cities.

17 cities is a rather small and surely old example and I think at that time they just copied the kilometers from a tourist guide or train schedule or similar, w/o taking much care.

So my theory was that just reaching the city limits naturally causes an error for large communities like Berlin or Zürich.

But I don't think it's worth to try to correct this now with something like a fuzzy surface in the visualization, better try starting from the beginning with real coordinates.

At least I think questioning the quality in my first reply was justified, it's worth checking data before trying to work with it.

Cheers Rolf

( addicted to the Perl Programming Language)

Create A New User
Node Status?
node history
Node Type: note [id://1068970]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (3)
As of 2017-08-22 04:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (328 votes). Check out past polls.

Notices?