Hi, I want to generate a, say 10x10, transition matrix including transition times. The transition time is uniformly distributed on e.g. [10, 100] and satisfies triangular inequality.
I wonder how to generate it.
thanks i n advance.
Hi, I want to generate a, say 10x10, transition matrix including transition times. The transition time is uniformly distributed on e.g. [10, 100] and satisfies triangular inequality.
I wonder how to generate it.
thanks i n advance.
- qtbgo
- 2014-03-11T12:50:33Z
Thank you Philippe, is it possible to generate a symmetric matrix satisfying triangular inequality?
Well, you can just symmetrize your matrix before running the Floyd-Warshall algorithm. Note that there was a small typo in my previous code (j<n should read j<=n).
int n=10; int TTMin = 10; int TTMax = 100; int Matrix[i in 1..n][j in 1..n] = (i<=j)?0:TTMin+rand(TTMax-TTMin+1); execute { // Symmetrize for (i=1; i<=n; i++) { for (j=i+1; j<=n; j++) { Matrix[i][j]=Matrix[j][i]; } } // Enforce triangular inequality with Floyd-Warshall algorithm for (k=1; k<=n; k++) { for (i=1; i<=n; i++) { if (i!=k) { for (j=1; j<=n; j++) { if ((j!=k)&&(j!=i)) { if (Matrix[i][k]+Matrix[k][j] < Matrix[i][j]) { Matrix[i][j] = Matrix[i][k]+Matrix[k][j]; } } } } } } }
Philippe
Hello,
The triangular inequality property implies some dependency between the different values in the matrix so I don't think it is possible to ensure that each coefficient in the matrix is uniformly distributed over an interval of integers [TTMin,TTMax]. But if you can slightly relax the shape of the probability distribution, one thing you can easily do is to first generate a matrix with coefficients uniformly distributed in [TTMin,TTMax] and then, apply a Floyd-Warshall algorithm to decrease some coefficients in order to satisfy the triangle inequality. See the OPL code below (note that in the code I additionally assumed a 0 self-distance Matrix[i][i]). As said, in the end the coefficients won't be uniformly distributed (the probability distribution should be some non-increasing function) but maybe it is enough for what you want to do.
int n=10; int TTMin = 10; int TTMax = 100; int Matrix[i in 1..n][j in 1..n] = (i==j)?0:TTMin+rand(TTMax-TTMin+1); execute { // Enforce triangular inequality with Floyd-Warshall algorithm for (k=1; k<=n; k++) { for (i=1; i<=n; i++) { if (i!=k) { for (j=1; j<n; j++) { if ((j!=k)&&(j!=i)) { if (Matrix[i][k]+Matrix[k][j] < Matrix[i][j]) { Matrix[i][j] = Matrix[i][k]+Matrix[k][j]; } } } } } } }
Philippe
- PhilippeLaborie
- 2014-03-11T08:40:30Z
Hello,
The triangular inequality property implies some dependency between the different values in the matrix so I don't think it is possible to ensure that each coefficient in the matrix is uniformly distributed over an interval of integers [TTMin,TTMax]. But if you can slightly relax the shape of the probability distribution, one thing you can easily do is to first generate a matrix with coefficients uniformly distributed in [TTMin,TTMax] and then, apply a Floyd-Warshall algorithm to decrease some coefficients in order to satisfy the triangle inequality. See the OPL code below (note that in the code I additionally assumed a 0 self-distance Matrix[i][i]). As said, in the end the coefficients won't be uniformly distributed (the probability distribution should be some non-increasing function) but maybe it is enough for what you want to do.
<pre class="html dw" data-editor-lang="js" data-pbcklang="html" dir="ltr">int n=10; int TTMin = 10; int TTMax = 100; int Matrix[i in 1..n][j in 1..n] = (i==j)?0:TTMin+rand(TTMax-TTMin+1); execute { // Enforce triangular inequality with Floyd-Warshall algorithm for (k=1; k<=n; k++) { for (i=1; i<=n; i++) { if (i!=k) { for (j=1; j<n; j++) { if ((j!=k)&&(j!=i)) { if (Matrix[i][k]+Matrix[k][j] < Matrix[i][j]) { Matrix[i][j] = Matrix[i][k]+Matrix[k][j]; } } } } } } } </pre>Philippe
Thank you Philippe, is it possible to generate a symmetric matrix satisfying triangular inequality?
- qtbgo
- 2014-03-11T12:50:33Z
Thank you Philippe, is it possible to generate a symmetric matrix satisfying triangular inequality?
Well, you can just symmetrize your matrix before running the Floyd-Warshall algorithm. Note that there was a small typo in my previous code (j<n should read j<=n).
int n=10; int TTMin = 10; int TTMax = 100; int Matrix[i in 1..n][j in 1..n] = (i<=j)?0:TTMin+rand(TTMax-TTMin+1); execute { // Symmetrize for (i=1; i<=n; i++) { for (j=i+1; j<=n; j++) { Matrix[i][j]=Matrix[j][i]; } } // Enforce triangular inequality with Floyd-Warshall algorithm for (k=1; k<=n; k++) { for (i=1; i<=n; i++) { if (i!=k) { for (j=1; j<=n; j++) { if ((j!=k)&&(j!=i)) { if (Matrix[i][k]+Matrix[k][j] < Matrix[i][j]) { Matrix[i][j] = Matrix[i][k]+Matrix[k][j]; } } } } } } }
Philippe
- PhilippeLaborie
- 2014-03-11T14:05:42Z
Well, you can just symmetrize your matrix before running the Floyd-Warshall algorithm. Note that there was a small typo in my previous code (j<n should read j<=n).
<pre class="html dw" data-editor-lang="js" data-pbcklang="html" dir="ltr">int n=10; int TTMin = 10; int TTMax = 100; int Matrix[i in 1..n][j in 1..n] = (i<=j)?0:TTMin+rand(TTMax-TTMin+1); execute { // Symmetrize for (i=1; i<=n; i++) { for (j=i+1; j<=n; j++) { Matrix[i][j]=Matrix[j][i]; } } // Enforce triangular inequality with Floyd-Warshall algorithm for (k=1; k<=n; k++) { for (i=1; i<=n; i++) { if (i!=k) { for (j=1; j<=n; j++) { if ((j!=k)&&(j!=i)) { if (Matrix[i][k]+Matrix[k][j] < Matrix[i][j]) { Matrix[i][j] = Matrix[i][k]+Matrix[k][j]; } } } } } } } </pre>Philippe
This is great! I am trying to use this code to generate the traveling distance. Every time I run the code, it generates the same matrix. If we need to generate 10 different matrices, how can make it happen (or how to introduce "random seed")?
- AndyHam
- 2018-03-12T18:24:25Z
This is great! I am trying to use this code to generate the traveling distance. Every time I run the code, it generates the same matrix. If we need to generate 10 different matrices, how can make it happen (or how to introduce "random seed")?
Hi
you should have a look at srand
regards