CODEWITHSUNDEEP
algorithmgraph
jteb
jteb

Reputation: 9

Ensuring edges of graph obey triangle inequality

I am generating graphs with edges being assigned random weights. How can I guarantee that the weights of edges obey the triangle inequality? I saw a similar question that has been asked but couldn't really follow the answer

Upvotes: 0

Views: 450

Answers (2)

pegah
pegah

Reputation: 859

In the supplementary material of The geometric nature of weights in real complex networks paper, you find a section called TEST OF THE TRIANGLE INEQUALITY in which they explain in detail how to perform the test. You can find the paper and the supplementary file from the author's website. I also agree with @David Conrad that this question belongs to the algorithm tag.

Upvotes: 0

btilly
btilly

Reputation: 46408

@Tau is right, there are a lot of ways to solve this problem.

  1. Assign random coordinates and take distances using any metric that satisfies the triangle inequality.
  2. Assign random weights, test whether the triangle inequality is satisfied, increase the weights of any edges that fail it.
  3. Assign random weights, test whether the triangle inequality is satisfied, redo if any edges fail it.

I can come up with more strategies as well. But the real question is why you are doing this, and whether there are any hidden requirements that make one solution better than another.

Upvotes: 1

Related Questions