In-place double-bridge or 4-opt move

double_bridge.md

I've implemented a double-bridge (or 4-opt) move in place, i.e. without any additional containers than the original. I'm sharing it with you first because I would like to know if it's correct or if I can improve it and second because I thought it could be helpful to someone else (since I have not found anything on the web).

/*
 * DOUBLE-BRIDGE-COMPUTE-GAIN
 *
 * Computes and returns the gain of a random double-bridge move.
 * The indices of the vertices used are also returnd as 2nd, 3rd and 4th parametrs of the array returned.
 * */
std::array<int, 4> double_bridge_in_place_compute_gain(const MatrixGraph &m, const VectorTour &t) {

   std::uniform_int_distribution<int> n_dist(0, t.size() / 4 - 1);


   // pick 3 split points randomly
   int pos1 = 1 + n_dist(gen);
   int pos1_p = t.previous(pos1);

   int pos2 = 1 + pos1 + n_dist(gen);
   int pos2_p = t.previous(pos2);

   int pos3 = 1 + pos2 + n_dist(gen);
   int pos3_p = t.previous(pos3);

   int last = t.size() - 1;
   int first = 0;

   int d = m(t[0], t[pos2_p]) + 
           m(t[pos1_p], t[pos3]) + 
           m(t[last], t[pos2]) + 
           m(t[pos3_p], t[pos1]) -
           m(t[first], t[last]) - 
           m(t[pos1_p], t[pos1]) - 
           m(t[pos2_p], t[pos2]) - 
           m(t[pos3_p], t[pos3]);

   return {d, pos1, pos2, pos3};
}

Now the actual function:

/*
 * DOUBLE-BRIDGE
 *
 * Uses the output of DOUBLE-BRIDGE-COMPUTE-GAIN and applies the corresponding double bridge move.
 * */
void double_bridge_in_place(VectorTour &s, const int pos1, const int pos2, const int pos3) {

   int last = s.size() - 1;

   int pos3_p = s.previous(pos3);

   s.shift_range(pos3, last, s.previous(pos1));

   // a's position has not changed
   s.shift_range(pos2, pos3_p, s.previous(pos1));
}

where shift_range(a, b, c) is a function which puts one after the other the elements from the range [a, b] after element c in the tour. So, for example, if we had a tour similar to a y x b h c the resulting tour after calling shift_range(a, b, c) would be h c a y x b.

Note I'm assuming that VectorTour is a circular tour, i.e., e.g., h c a y x b is the same as c a y x b h or a y x b h c.

Another thing to note is that the VectorTour container contains the ids of the nodes/elements and therefore I'm assuming that nodes are initially numbered from $0$ (or $1$) to $N - 1$ (or $N$).

The function previous(a) simply returns the index in the TourVector of the previous element of a. For example, if a is the index $3$ in the container, then previous(a) $2$ and if $a = 0$, then $previous(a) = N - 1$.

For those of you who don't know anything about C++, n_dist(0, t.size() / 4 - 1) means that I'm creating an object to generate random numbers in the range [0, t.size() / 4 - 1] and when I call n_dist(gen) I'm actually generating the random number.

Note that the integer parameters to the both functions are not the ids of the nodes/elements in the TourVector but the indices of the nodes.

Think of m as a distance matrix.

Note: feel free to edit the question to improve its clarity and maybe make it more language agnostic.