title: Generating a graph in which the triangle inequality holds
body: <p>I would like to generate a set of rather big (~10,000-50,000) complete graphs <code>G=(V,E)</code> with weighted edges in which the <strong>sharp</strong> triangle inequality holds -- so for every <code>v,u,w from V</code>: <em>weight</em>(vu) + <em>weight(uw)</em> &gt; <em>weight</em>(vw); weights are positive integers.</p>
  <p><strong>EDIT</strong>
  The vertices are points in N-dim euclidean space and each weight of an edge <em>uv</em> has to be greater or equally than euclidean distance between <em>u</em> and <em>v</em> (so if the distance is e.g. 2.753 then the minimal, allowed weight is 3, but it may 4, 5, ...).</p>
  <hr />
  <p>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.</p>
  <p>Some notation:</p>
  <ul>
  <li>vu or vertex1-vertex2 denotes an edge</li>
  <li><em>E(v,u)</em> -- euclidean distance between v and u</li>
  <li>for a double / real  number <em>r</em>, <em>ceil(r)</em> is an integer n such that n - 1 &lt; r &lt;= n (e.g.
  ceil(10.5) = 11, ceil(0.000000000001) = 1, ceil(172) = 172.</li>
  <li><em>(vu,c)</em> -- edge vu has weight c</li>
  </ul>
  <h2>Method 1 -- <em>local</em></h2>
  <pre><code>vertices = {v,u} -- v, u generated randomly
  edges = {vu} 
  weights = {(vu,ceil(E(v,u))} 
  i = 0
  while(i &lt; 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            
  </code></pre>
  <h2>Method 2 -- <em>global</em></h2>
  <pre><code>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
  </code></pre>
  <p>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.</p>
  <p>If anything above is not clear enough I will provide more information.</p>
  <hr />
  <p>If it will turn out, that keeping weights as positive <code>integers</code> is too difficult I could consider having them as positive <code>doubles</code>, but in such a case the floating-point precision would be potentially a problem to deal with [as I really need to have <em>sharp</em> triangle inequality]</p>