CODEWITHSUNDEEP
algorithmgraph
artur grzesiak
artur grzesiak

Reputation: 20348

Generating a graph in which the triangle inequality holds

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:

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
        end_if
    end_for_each
    if(ok)
         i++
         add candidate to vertices, 
         for_each vertex in vertices:
             add vertex-candidate to  edges
             add (vertex-candidate, ceil(E(candidate,vertex))) to weights
         end_for_each          
     end_if
end_while

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
end_for_each
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'
         end_if
    end_for_each
end_while

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]

Upvotes: 4

Views: 3381

Answers (1)

Adam
Adam

Reputation: 17339

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.

Upvotes: 1

Related Questions