Randomization only randomizes the step order, but not internally each step!
Currently turning on randomization only randomizes the order in which the steps are done, but it does not randomize the internal order of each step, which is ideally what we want. Currently we use a fixed communication matrix, in which in each step a set of connections are tests. We can permute the step order, but we cannot currently permute what connections are tested in a step. This is problem if the connection configuration within a step affects the results. We now use a very simple base configuration, which makes spotting errors associated with this obvious. We used to use a more complex base configuration, which still had the same problem, it was just not obvious from the results.
What we should ideally do is fully randomize the connections tested in a step and the order in which the steps are tested. This problem, however, at best has exponential complexity, which makes it much worse than NP-hard problems. Below is a python script that brute forces valid random connection matrices, including a random step permutation as well as accounting for the idea of having direction based testing. Please do not make the network size much greater than 16, it can otherwise with poor luck take a very long time (on the order of days) to find a valid connection matrix.
I think our best recourse to this problem is to have the user supply the connection matrix they want and let them figure out how to generate it. Better than linktest having a non-predicatable execution time. We would also have to document this feature. We should also come back to this issue in case a researcher figures out an algorithm, which exist for certain matrix sizes, but there is no general rule. Also, a fast algorithm simply may not exist. Maybe just point the user to OEIS, where there are lists of these types of matrices.
Here is the python code:
import numpy
import random
import timeit
# To randomly test all possible connections between n nodes to assign a number
# to all possible connections. If we think of this in terms of graph theory then
# every node is a vertex and every connection between two nodes is an edge. The
# process of assigning numbers to the connections is known in graph theory as
# edge colouring. Further since we are dealing with a complete graph, in which
# there is one edge between every pair of verticies, our connection matrix, a
# matrix where each row and column corresponds to a specfic vertex and the
# elments correspond to the color of the connection between the matrix-row and
# matrix-column vertices, is a transpose-symmetric Latin square with zeros
# along the diagonal. These zeros indicate connections between a vertex and
# itself and are not relevant for us.
# There are algorithms to colour such Latin squares, they only ever generate
# a countably finite trivial subset of all valid transpose-symmetric Latin squares
# with constant 0 diagonals. Finding the remaining possible Latin squares has
# at least exponential complexity. Even finding a permuting subset has exponential
# complexity.
# We will now find, for a given n-by-n matrix size, n! of these matrices with the
# help of permutation. For this we only consider normalized Latin squares, which
# are those where the first row and column are each filled with 0,1,...,n-1.
# Further we know the diagonal is zero. We start at the third element in the
# second row and then recusively randomly pick valid values for the remaining
# entries in the upper-right half of the matrix, discarding and backtracking as
# we identify invalid squares. Once all upper-right elements have been randomly
# chosen the result is transposed to arrive at the final Latin square.
# We now have a valid connection matrix, however, note that we can test
# connections in two directions. As such the upper-right and lower-left triangles
# should differ, i.e. the connections should be coloured differently. This type
# of graph is know as a complete directrional graph. We can easily generate by
# going through the upper-right triangle of our Latin suqare and either adding
# n-1 to the value in the upper-right triangle, or to its transpose. After this
# all directed connections are labeled.
# We can now randomly permute the values in the connection matrix using a global
# permutor to generate (2n-1)! different realizations without changing the 0
# diagonal.
# In terms of linktest the matrix element (edge colour) is the step number.
# The disadvantage of this brute force approach is that it can take a considerable
# amount of time to randomly brute force a solution. On modern hardware finding
# a valid set of permutations for n=32 can take an hour plus.
# FUNCTIONS - DO NOT TOUCH!
def remove(x,y):
return [z for z in x if z != y]
def fill(mat):
return fill1(mat,1,2)
def fill1(mat,i,j):
n=mat.shape[0]
choices=list(range(1,n,1))
for i1 in range(0,i,1):
choices=remove(choices,mat[i1,j])
for j1 in range(0,j,1):
choices=remove(choices,mat[i,j1])
if not choices:
return False
while choices:
mat[i,j]=random.choice(choices)
mat[j,i]=mat[i,j]
if j==n-1 and i==n-2:
return mat
else:
j1=j+1
if j1==n:
i1=i+1
j1=i1+1
else:
i1=i
tmp=fill1(mat,i1,j1)
if not isinstance(tmp, numpy.ndarray):
choices = remove(choices,mat[i,j])
else:
return tmp
# VARIABLES - YOU CAN TOUCH
n=int(6);
# CODE - DO NOT TOUCH
mat=numpy.zeros([n,n],dtype=int,order='C')
# 1. Initialize matrix
for i in range(0, n, 1):
mat[0, i] = i
mat[i, 0] = i
mat[i, i] = 0
print(mat)
# 2. Fill Matrix
print(timeit.timeit("fill(mat)",globals=globals(),number=10))
print(mat)
# 3. Add opposite directions
for i in range(0,n,1):
for j in range(i+1,n,1):
if bool(random.getrandbits(1)):
mat[i,j]+=n-1
else:
mat[j,i]+=n-1
print(mat)
# 4. Randomly permute
permutor=numpy.zeros([2*n-1,],dtype=int,order='C')
permutor[1:]=numpy.random.permutation(list(range(1,2*n-1,1)))
print(permutor)
for i in range(0,n,1):
for j in range (0,n,1):
mat[i,j]=permutor[mat[i,j]]
print(mat)
Here are two different results for a 6-by-6 matrix:
N1 | N2 | N3 | N4 | N5 | N6 | |
---|---|---|---|---|---|---|
N1 | 0 | 5 | 1 | 8 | 4 | 3 |
N2 | 6 | 0 | 7 | 9 | 1 | 8 |
N3 | 2 | 3 | 0 | 5 | 10 | 4 |
N4 | 10 | 4 | 6 | 0 | 3 | 2 |
N5 | 9 | 2 | 8 | 7 | 0 | 6 |
N6 | 7 | 10 | 9 | 1 | 5 | 0 |
N1 | N2 | N3 | N4 | N5 | N6 | |
---|---|---|---|---|---|---|
N1 | 0 | 3 | 5 | 8 | 2 | 4 |
N2 | 7 | 0 | 10 | 5 | 1 | 8 |
N3 | 6 | 2 | 0 | 4 | 8 | 7 |
N4 | 9 | 6 | 1 | 0 | 7 | 10 |
N5 | 10 | 4 | 9 | 3 | 0 | 5 |
N6 | 1 | 9 | 3 | 2 | 6 | 0 |
The nodes and columns correspond to a node, the number indicates the step in which they are tested, assuming that forward and backwards directions are not tested immediately after each other.