Take the 2-minute tour ×

I would like to generate a set of rather big (~10,000-50,000) complete graphs G=(V,E) with weighted edges in which the sharp triangle inequality holds -- so for every v,u,w from V: weight(vu) + weight(uw) > weight(vw); weights are positive integers.

EDIT The vertices are points in N-dim euclidean space and each weight of an edge uv has to be greater or equally than euclidean distance between u and v (so if the distance is e.g. 2.753 then the minimal, allowed weight is 3, but it may 4, 5, ...).

Up to now I came up with two naive approaches. Both of these methods are based on random generating points in N-dimensional Euclidean space.

Some notation:

  • vu or vertex1-vertex2 denotes an edge
  • E(v,u) -- euclidean distance between v and u
  • for a double / real number r, ceil(r) is an integer n such that n - 1 < r <= n (e.g. ceil(10.5) = 11, ceil(0.000000000001) = 1, ceil(172) = 172.
  • (vu,c) -- edge vu has weight c

Method 1 -- local

vertices = {v,u} -- v, u generated randomly
edges = {vu} 
weights = {(vu,ceil(E(v,u))} 
i = 0
while(i < total_number_of_vertices)
    candidate = generate_new_point()
    ok = true
    foreach (vertex in vertices):
        integer_distance = ceil(E(candidate,vertex))
        if adding (candidate-vertex, integer_distance) to weights
           violates the triangle inequality:
               ok = false \\ this candidate is wrong
               break \\ breaking for-each; start with new candidate
         add candidate to vertices, 
         for_each vertex in vertices:
             add vertex-candidate to  edges
             add (vertex-candidate, ceil(E(candidate,vertex))) to weights

Method 2 -- global

vertices = generate_points(total_number_of_vertices)
edges = complete Graph induced by vertices
weights = {}
for_each edge uv:
    add (uv, ceil(E(u,v))) to weights
all_good = false
while (!all_good):
    all_good = true
    for_each edge in edges:
         \\ this one has to be check in all triangles that edge belongs to
         if edge violates triangle inequality:
             \\ by appropriate I mean directly involved
             update appropriate weights to satisfy triangle inequality
             all_good = false \\ 'updating one edge may disturb other'

I am highly skeptical, if these methods will be efficient enough, so any help -- in improving them or suggesting completely different approaches -- would be appreciated.

If anything above is not clear enough I will provide more information.

If it will turn out, that keeping weights as positive integers is too difficult I could consider having them as positive doubles, but in such a case the floating-point precision would be potentially a problem to deal with [as I really need to have sharp triangle inequality]

share|improve this question
Why not just give all of the edges the same weight? –  Alex Reinking Nov 15 '13 at 19:07
Sorry, i should be more precisely about that (edited the question). –  artur grzesiak Nov 15 '13 at 19:13
Wait a second, do you want a map from the vertices to the points in the N-dimensional Euclidean space to exist? You just mention this space as a way to generate those weights. It's not required in the description of the problem as far as I see. So I think that your edit is kinda undefined. –  lnwvr Nov 15 '13 at 19:25
A little confused by your constraint "for every v,u,w from V: weight(vu) + weight(uw) > weight(vw)"... If we simply call weight(xy) == distance(x, y), then can you draw a non-degenerate triangle that does not exhibit the required property? I'm not sure such a triangle exists, except for the degenerate case where weight(vu) + weight(uw) == weight(vw) (i.e. one vertex is on the line defined by the other two). –  twalberg Nov 15 '13 at 20:18
@twalberg the problem is that in general the distance is real / double and I would like to have the weight integer. –  artur grzesiak Nov 15 '13 at 21:44

1 Answer 1

I'll propose another naive method, albeit an O(E) one. Choose a range R = [A, B) where 2A > B. This means that if the weights are in R then the triangle inequality is guaranteed to hold.

For example, B = 100. Therefore A = B/2 = 50. For every edge pick a random number between 50 and 99.

You can meet your Euclidean space requirement by adding the random number to your Euclidean distance.

share|improve this answer
Sorry I cannot get it, You mean instead of rounding the distance up -- just add a random number to it? –  artur grzesiak Nov 15 '13 at 23:45
I'm assuming you want some degree of randomness in your generated graph, because otherwise you'd just use the distances. But yes, you could use this scheme to eliminate the problem of rounding possibly affecting the triangle inequality. I think you just need to set A = B/2 + 1 and that should be ok. –  Adam Nov 16 '13 at 0:39

Your Answer


