2-opt swapping

1 files changed, 43 insertions, 23 deletions

diff --git a/src/tsp_approx.rs b/src/tsp_approx.rs
index f79d0a4..7c9568d 100644
--- a/src/tsp_approx.rs
+++ b/src/tsp_approx.rs
@@ -1,8 +1,8 @@
 use ahash::{random_state::RandomState, HashMap, HashSet};
 use indicatif::{ProgressBar, ProgressStyle};
-use partitions::partition_vec::PartitionVec;
 use mset::MultiSet;
-use std::{hash::Hash, cmp::Eq};
+use partitions::partition_vec::PartitionVec;
+use std::{cmp::Eq, hash::Hash, mem::swap};
 
 use crate::{MetricElem, TspAlg};
 
@@ -37,7 +37,10 @@ fn get_hashset<V>(hash_seed: &Option<u64>, capacity: Option<usize>) -> HashSet<V
     }
 }
 
-fn get_multiset<V: Hash + Eq>(hash_seed: &Option<u64>, capacity: Option<usize>) -> MultiSet<V, RandomState> {
+fn get_multiset<V: Hash + Eq>(
+    hash_seed: &Option<u64>,
+    capacity: Option<usize>,
+) -> MultiSet<V, RandomState> {
     let hasher = match hash_seed {
         Some(s) => RandomState::with_seeds(*s, 0, 0, 0),
         None => RandomState::new(),
@@ -83,9 +86,7 @@ fn get_mst(
     mst
 }
 
-fn tsp_from_mst(
-    mst: HashMap<usize, Vec<usize>>,
-) -> Vec<usize> {
+fn tsp_from_mst(mst: HashMap<usize, Vec<usize>>) -> Vec<usize> {
     fn dfs(cur: usize, prev: usize, t: &HashMap<usize, Vec<usize>>, into: &mut Vec<usize>) {
         into.push(cur);
         t.get(&cur).unwrap().iter().for_each(|&c| {
@@ -233,7 +234,8 @@ fn christofides(
     mst: HashMap<usize, Vec<usize>>,
     hash_seed: &Option<u64>,
 ) -> Vec<usize> {
-    let mut ext_mst: HashMap<usize, MultiSet<usize, RandomState>> = get_hashmap(hash_seed, Some(mst.len()));
+    let mut ext_mst: HashMap<usize, MultiSet<usize, RandomState>> =
+        get_hashmap(hash_seed, Some(mst.len()));
     for (k, v) in mst.into_iter() {
         let mut as_mset = get_multiset(hash_seed, Some(v.len()));
         for l in v.into_iter() {
@@ -280,14 +282,10 @@ fn christofides(
         }
     }
 
-
     r
 }
 
-fn refine_2_opt(
-    dist_cache: &DistCache,
-    tour: Vec<usize>,
-) -> Vec<usize> {
+fn refine_2_opt(dist_cache: &DistCache, tour: Vec<usize>) -> Vec<usize> {
     if tour.len() < 4 {
         return tour;
     }
@@ -313,33 +311,54 @@ fn refine_2_opt(
         /* tour index */ 0,
     );
 
-    let adv = |(pi, i): (usize, usize)| {
+    let adv = |(pi, i): (usize, usize), tour: &Vec<(usize, usize, usize)>| {
         if tour[i].0 == pi {
             (i, tour[i].2) // forward
         } else {
             (i, tour[i].0) // reverse
         }
     };
+    let replace_matching = |(prev, v, next): (usize, usize, usize), old: usize, new: usize| {
+        if prev == old {
+            (new, v, next)
+        } else {
+            assert!(next == old);
+            (prev, v, new)
+        }
+    };
 
-    // TODO so nehmen wir die boundary nicht mit. NOTE: das flattening geht davon aus,
-    // das wir das nicht tuen
+    // for each combination of edges ...
     while le.0 != n - 2 {
-        let mut re = adv(le);
+        let mut re = adv(le, &tour);
         while re.0 != n - 1 {
+            // ... check whether a 2-opt swap improves the tour
+
             let le_elems = (tour[le.0].1, tour[le.1].1);
             let re_elems = (tour[re.0].1, tour[re.1].1);
-            let cur_cost  = dist_cache.dist(le_elems.0, le_elems.1) + dist_cache.dist(re_elems.0, re_elems.1);
-            let swap_cost = dist_cache.dist(le_elems.0, re_elems.0) + dist_cache.dist(le_elems.1, re_elems.1);
+            let cur_cost =
+                dist_cache.dist(le_elems.0, le_elems.1) + dist_cache.dist(re_elems.0, re_elems.1);
+            let swap_cost =
+                dist_cache.dist(le_elems.0, re_elems.0) + dist_cache.dist(le_elems.1, re_elems.1);
 
             if cur_cost <= swap_cost {
-                re = adv(re);
+                re = adv(re, &tour);
                 continue;
             }
 
-            re = adv(re);
+            // logically, to swap, we want: swap(le.1, re.0)
+            // however, changing the link in the `tour` is much more cumbersome
+            // as the tour may contain forward/backward nodes, so we use a helper.
+            tour[le.0] = replace_matching(tour[le.0], le.1, re.0);
+            tour[le.1] = replace_matching(tour[le.1], le.0, re.1);
+            tour[re.0] = replace_matching(tour[re.0], re.1, le.0);
+            tour[re.1] = replace_matching(tour[re.1], re.0, le.1);
+
+            swap(&mut le.1, &mut re.0);
+
+            re = adv(re, &tour);
         }
 
-        le = adv(le);
+        le = adv(le, &tour);
     }
 
     // calculate tour as vector from linked-list
@@ -347,9 +366,10 @@ fn refine_2_opt(
     let mut cur = (n - 1, 0);
 
     tour_flat.push(tour[0].1);
-    while cur.1 != n - 1 {
-        cur = adv(cur);
+    cur = adv(cur, &tour);
+    while cur.1 != 0 {
         tour_flat.push(tour[cur.1].1);
+        cur = adv(cur, &tour);
     }
 
     tour_flat