As discussed in the comments to the question, it’s not very clear exactly what epitaph‘s setup is, and for some reason s/he seems unwilling to clarify. But let’s suppose that the “graph” is actually simply represented by a distance matrix (which may possibly be what the mess of numbers and Xs in the question is supposed to show), with an actual numeric distance for each pair of vertices.
In that case, there’s nothing very graph-ish going on here; there’s an edge for every pair of vertices without exception; and all we can do is to enumerate every single triple of vertices.
For each set of three vertices a,b,c we need to check that d(a,b) <= d(a,c)+d(c,b), and that d(a,c) <= d(a,b)+d(b,c), and that d(b,c) <= d(b,a)+d(a,c). So let’s do that. The following is pseudocode because if I try to write it in PHP (which I use as seldom as possible) I’ll make mistakes.
for i from 0 to n_vertices-3
for j from i+1 to n_vertices-2
for k from j+1 to n_vertices-1
# now i,j,k are three distinct vertices, and every set of three vertices
# will occur once as we run through the loops.
a = distances[i,j]
b = distances[i,k]
c = distances[j,k]
if a>b+c or b>a+c or c>a+b
triangle inequality is violated; complain
If your graph is represented in some way other than as a distance matrix, or if lots of edges might fail to exist, then you’d want to do something different.
(Note: if your graph is supposed to satisfy the triangle inequality, then arguably it shouldn’t be missing any edges unless it’s actually disconnected. It depends on whether the distances are intended to be “overall shortest distance from x to y” (in which case if the triangle inequality fails then something is broken, and there should be no absent edges in a connected graph) or “distance of direct path from x to y” (in which case if the triangle inequality fails it merely indicates that an allegedly direct path isn’t worth using).)
0
solved Generating all triples from a graph?