0
$\begingroup$

The double bridge move is a specific type of swap between 4 edges of a graph, also called 4-opt. It consists of removing 2 pairs of edges. Let`s call them (I, I+1), (J, J+1) and (P, P+1), (Q, Q+1). The edges are removed and reconnected in this way (I, J+1), (J, I+1), (P, Q+1) and (Q, P+1), like in the first image below. In this way, the graph that could be seem like circular now has 2 "bridges"(pair of edges) crossing each other.

I need this for the Travelling Salesman Problem. I want to know the best way to do the Double bridging, in pseudocode. I have coded the 2-opt already, but this type of 4-opt cannot be reproduced by any sequence of 2-opts. Not unless some sort of reversal is also made in some edges of the graph, and i don't know how to do this.

I searched the entire internet including several papers for any explanation regarding double bridge but none have helped me.

enter image description here enter image description here

$\endgroup$
3
  • $\begingroup$ Thank you for your edits. I don't understand your question. What do you mean by the "best" way? "Best" by what criteria? It looks like this can be implemented in a totally straightforward way, with $O(1)$ time. What are the criteria you will use to evaluate which is "best", and that you will use to evaluate answers? What's the best approach you've been able to come up with so far, and why have you rejected it? $\endgroup$
    – D.W.
    Jan 16 at 0:49
  • $\begingroup$ @D.W. By best answer i mean mostly time complexity, if possible considering space complexity aswell. O(1) would be perfect but i dont know if its possible the way i coded it. I'm using C language and an array with a start and a finish node in each position, representing an edge. My approach uses a copy for the path and 2 array of succesors, to indicate what is the next node, since this isn't a linked list. I update one of them according to what changes i made in the path when double bridging. Then i use the other in conjunction to order the nodes in the new array that represents the path $\endgroup$ Jan 17 at 12:42
  • $\begingroup$ I'm not confident i can do O(1) using an array, but even if it's possible to use less variables than i'm using it would be great already. By variables i mean the copy of the path and the 2 arrays of succesors(i tried with one but couldn't quite figure out how to do it). $\endgroup$ Jan 17 at 12:46
0
$\begingroup$

If the path is stored as a doubly-linked list, you can do it in $O(1)$ time in a straightforward way: you have to change around 4 edges, and each change can be done in $O(1)$ time. With an array it takes $O(n)$ time but is also straightforward to implement.

$\endgroup$
3
  • $\begingroup$ With array i'm stuck with O(n) right? $\endgroup$ Jan 17 at 16:33
  • $\begingroup$ @MatheusSoares, see updated answer. $\endgroup$
    – D.W.
    Jan 17 at 17:23
  • $\begingroup$ Thanks, but what is the straightforward way? Would you need the same additional variables i have mentioned? $\endgroup$ Jan 17 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.