Adding Combinations of Numbers in a Matrix

Question

I found this link that shows you how to make a matrix with random numbers: https://www.tutorialspoint.com/how-to-create-a-matrix-with-random-values-in-r

  #random symmetric matrix with diagnoal elements as 0
 A <- matrix(runif(16), 4, 4)
A1 = A %*% t(A)

out_1 = A1 - diag(diag(A1))

         [,1]     [,2]     [,3]     [,4]
[1,]     0.00 20371.54 19136.91 18380.49
[2,] 20371.54     0.00 19392.13 19476.78
[3,] 19136.91 19392.13     0.00 16651.73
[4,] 18380.49 19476.78 16651.73     0.00

• Imagine each index corresponds to a city in this matrix (out_1) - there are 4 cities.

• Any (row , column) combination corresponds to the distance between two cities (e.g. [2][3] corresponds to the distance between city 2 and city 3).

• Logically, the distance between the same two cities is the same, e.g.. [2] [3] = [3] [2]

• Logically, the distance between a city and itself is 0, e.g. [2] [2] = 0

Using this matrix (out_1), I want to calculate all "paths" from this matrix that have the following structure:

• The path must start and end from the same city, and with the exception of the first city, no other city can be visited twice.

For example, the end goal would look something like this:

- Path 1 : [1] [2] , [2] [3], [3] [4], [4] [1] = 20371.54 + 19392.13 + 16651.73 + 18380.49 = 74795.89  
- Path 2 : [2] [4] , [4] [3], [3] [1], [1] [2] = 19476.78 + 16651.73 + 19136.91 + 20371.54 =   75636.96
- ....
- Path n: [3] [4] , [4] [1], [1] [2], [2] [3] =  16651.73 + 18380.49 + 20371.54 + 19392.13 =   74795.89 

I tried to find some library in R to do this (note: I think what I am trying to do is called a "Hamiltonian Cycle of a Graph") : https://www.rdocumentation.org/packages/adagio/versions/0.8.4/topics/hamiltonian

But this did not work:

    c = c(out_1)
 hamiltonian(c, cycle = TRUE)

    Error in graph_vect2list(edges) : 
      Argument 'edges' is not a correct edge list.

How can I get a list of all such "paths" that shows the order of the cities and the total distance for each path?

Thanks!

Answer 1

There are factorial(n-1) Hamiltonian cycles on a complete graph of order n—or half as many if you exclude reverse cycles, e.g., if you keep only one of (123) and (132) when n = 3. In some contexts, the distance from A to B is not the same as the distance from B to A, so it can be useful to include reverse cycles.

Here is an approach that counts all factorial(n-1) cycles, relying on function permutations from package gtools to do the "path-finding". There are several alternatives to gtools, which you are free to use instead.

mkX <- function(n) {
    X <- abs(crossprod(matrix(rnorm(n * n), n, n)))
    diag(X) <- 0
    X
}

roundtrips <- function(X) {
    n <- nrow(X)
    if (n < 2L) {
        trips <- matrix(integer(0L), 0L, 0L)
        distances <- double(0L)
    } else {
        trips <- cbind(1L, gtools::permutations(n - 1L, n - 1L, seq.int(2L, n)))
        distances <- apply(trips, 1L, function(i) sum(X[cbind(i, c(i[-1L], 1L))]))
    }
    list(X = X, trips = trips, distances = distances)
}

set.seed(1L)
X <- mkX(4L)
roundtrips(X)

$X
          [,1]      [,2]     [,3]     [,4]
[1,] 0.0000000 0.4134306 1.058161 1.029243
[2,] 0.4134306 0.0000000 1.465003 2.127536
[3,] 1.0581611 1.4650029 0.000000 2.001777
[4,] 1.0292425 2.1275361 2.001777 0.000000

$trips
     [,1] [,2] [,3] [,4]
[1,]    1    2    3    4
[2,]    1    2    4    3
[3,]    1    3    2    4
[4,]    1    3    4    2
[5,]    1    4    2    3
[6,]    1    4    3    2

$distances
[1] 4.909453 5.600905 5.679943 5.600905 5.679943 4.909453

Here, X is a distance matrix; it need not be symmetric, but in this example it is. trips is an integer matrix whose rows define distinct Hamiltonian cycles of the graph. distances is a double vector listing the distances traversed over those cycles. When X is symmetric, the distances come in pairs corresponding to cycles and their reverses.

Choose n carefully: factorial(n-1) grows quite fast.